Comments 10
Сейчас-то всё проще, в яндекс.новостях кластер по сути один
Предположим, пользователь изучает конкретный документ внутри новостного сюжета. Какова доля документов этого сюжета, относящихся к той же теме, что и изучаемый документ? А какую долю документы по этой теме в сюжете составляют от числа всех документов по теме?
Моя матрица зависла и сломалась.
Пусть у меня имеется множество и некоторое его разбиение на классы, которое я назову стандартным. По сути, принадлежность к тому или иному классу стандартного разбиения — это некоторое свойство, назовем его классовым. Если случайно из этого множества выбрать элемент x и настолько же случайно — какой-нибудь элемент y из содержащего x класса, то их классовые свойства будут совпадать. Иначе говоря, при такой схеме выбора будут отсутствовать ошибки классового соответствия.
Пусть теперь на том же множестве как-то выделено еще одно разбиение, называемое кластерным. Снова выберем из всего множества случайный элемент x, а затем из кластера, которому принадлежит x, не менее случайно вберем элемент y. Если кластеры не точно совпадают с классами, то имеется некоторая вероятность p, что классовые свойства x и y не совпадают. Эту вероятность p я и хочу считать метрикой качества для приближения кластерным разбиением исходного разбиения на классы.
То что вы предлагаете описано в п 2.2. но там используется Precision и Recall, а вы предлагаете использовать Accuracy.
Практика показывает, что не смотря на кажущуюся интуитивность этой метрики, она плохо работает в случае дисбаланса классов.
Поэтому в ML не принято использовать Accuracy.
То что вы предлагаете описано в п 2.2.
Возможно я не до конца понял, что именно описано в пункте 2.2, но мне кажется, там речь идет о сопоставлении кластеров и эталонных классов. Тот метод, который я описал выше, совершенно не требует, чтобы такое сопоставление осуществлялось: все что нужно — это однородность классовых свойств в каждом кластере.
У P-метода, давайте его так называть, есть правда детская болезнь: метрика обнулится, если каждый элемент считать отдельным кластером. Однако ответить внутри чистой теории множеств, почему одноэлементные кластеры — это плохо, мне не представляется возможный. Универсальный методом здесь могла быть оценка симметричной взаимной информации, но опять же: почему необходимо считать задачу симметричной (почему классы должны стремиться состоять из элементов одного кластера) — не понятно.
Если излишняя дискретизация на практике приводит к каким-то потерям, то наверное модель этих потерь должна быть добавлены к обоснованию, почему та или иная метрика кластеризации плоха или хороша, иначе «плохо» и «хорошо» остаются неопределенными эмоциональными суждениями.
Если я всё правильно понял, это BCubed Precision. Для отдельного элемента BCP равняется в точности вероятности того, что другой случайный элемент из того же кластера относится к тому же эталону, что и выбранный элемент, а интегральный показатель — простое усреднение, эквивалентное равновероятному выбору элементов.
Эта метрика очень хорошая, но учитывает только точность соответствий, но не полноту, так что не может использоваться изолированно.
Предлагаю рассмотреть такую метрику на основе взаимной информации. В статье предполагается, что модельное разбиение соотносит кластеры "истиным" в предлагаемой метрике это не требуется и она симметрична.
Разбиение на кластеры подражает некоторое распределение. Можно считать (но не обязательно), что это распределение порождено некоторой случайной величиной.
Это означает, что мы можем посчитать взаимную информацию распределений.
Итак. Пусть X — истинное распределение, порождаемое С.В. x, а Y — модельное, порождаемое соответственно y.
Тогда мы можем посчитать их взаимную информацию по формуле
(Hx +Hy - Hxy) / HxyЗдесь Hx — энтропия x, Hy — энтропия y, а Hxy — энтропия совместного распределения x и y.
Энтропия — это размерная величина (измеряется в битах или натах), зависит от основания логарифма, поэтому если нам нужна безразмерная метрика, то нужно нормировать.
Предложенный способ нормировки стандартный, но не единственный.
Можно показать, что определённое таким образом число всегда будет в интервале [0, 1]
| | a | b | c | d | e | f | g | h | i |
|---|---|---|---|---|---|---|---|---|---|
| x | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| y | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 2 | 2 |Px(1)=Py(1)=5/9 Px(2)=Py(2)=4/9
Pxy(1,1)=4/9 Pxy(1,2)=1/9 Pxy(2,1)=1/9 Pxy(2,2)=3/9
Hx = Hy = -5/9*ln(5/9) - 4/9*ln(4/9) = 0.687
Hxy = -4/9*ln(4/9) - 2/9*ln(1/9) - 3/9*ln(3/9) = 1.215
i_xy = (2*0.687-1.215)/1.215 = 0.13
Если бы точек было 90 и 2 различались, то i_xy = 0.73, а если 900, то i_xy = 0.95
В примере видно, что получаемые значения оказываются, на первый взгляд, ниже ожидаемых. Не знаю хорошо это или плохо.
Есть два важных класса метрик, которые я не рассматривал :) При этом они упоминаются в цитирующейся статье.
Это информационные метрики на основе энтропии (к этому классу относится описанная вами) и метрики на основе edit distance. В цитируемой статье оба класса коротко рассматриваются, основной проблемой является то, что для них не выполнено условие Rag Bag.
У этих метрик хорошие аналитические свойства, поэтому многие их, действительно, используют. Я в свою очередь их не люблю за то, что не вижу ясного соответствия между физическим смыслом происходящего на сервисе и физическим смыслом метрики. Из-за этого никогда их и не использовал =)
Оценка качества кластеризации: свойства, метрики, код на GitHub