company_banner

Оценка качества кластеризации: свойства, метрики, код на GitHub

    Кластеризация — это такая магическая штука: она превращает большой объём неструктурированных данных в потенциально обозримый набор кластеров, анализ которых позволяет делать выводы о содержании этих данных.


    Приложений у методов кластеризации огромное количество. Например, мы кластеризуем поисковые запросы для того, чтобы повышать обобщающую способность алгоритмов ранжирования: любая статистика, вычисленная по группе похожих запросов, надёжнее той же статистики, вычисленной для одного отдельного запроса. Кластеризация позволяет повышать качество на запросах с редко встречающимися формулировками. Другой понятный пример — Яндекс.Новости, которые автоматически формируют сюжеты из новостных сообщений.


    В далёком 2013 году мне повезло поучаствовать в разработке очень сложного алгоритма кластеризации. Требовалось с очень высоким качеством кластеризовать сотни тысяч объектов и делать это быстро: за десятки секунд на одной машине. Первым делом нужно было построить систему оценки качества, и в этой статье я расскажу именно о ней.




    Когда речь заходит об оценке качества, начинать нужно, конечно же, с метрик.


    Алгоритм кластеризации можно и нужно оценивать с позиции сервиса, частью которого этот алгоритм является: рост качества кластеризации должен приводить к росту числа пользователей, конверсий, возвращаемости и так далее, так что классическое А/Б-тестирование вполне уместно. Вместе с тем любой большой системе нужны метрики, специфичные для каждого из её компонентов. Кластеризация — не исключение.


    1. Метрики и их свойства


    Обычно задано образцовое разбиение на кластеры и разбиение, построенное алгоритмически. Метрика качества должна оценить степень соответствия между ними.



    Обсуждение метрик стоит предварить обсуждением принципов, которым эти метрики должны удовлетворять. В статье Amigo et. al, 2009. A comparison of Extrinsic Clustering Evaluation Metrics based on Formal Constraints очень подробно разбирается ряд принципов, их корректность и то, как различные классы метрик удовлетворяют этим принципам.


    1.1. Cluster Homogeneity, однородность кластеров



    Значение метрики качества должно уменьшаться при объединении в один кластер двух эталонных.


    1.2. Cluster Completeness, полнота кластеров



    Это свойство, двойственное свойству однородности. Значение метрики качества должно уменьшаться при разделении эталонного кластера на части.


    1.3. Rag Bag



    Пусть есть два кластера: чистый, содержащий элементы из одного эталонного кластера, и шумный («лоскутный»), где собраны элементы из большого числа различных эталонных кластеров. Тогда значение метрики качества должно быть выше у той версии кластеризации, которая помещает новый нерелевантный обоим кластерам элемент в шумный кластер, по сравнению с версией, которая помещает этот элемент в чистый кластер.


    Это свойство может показаться очень естественным, но обязательно нужно принимать во внимание специфику приложения. Скажем, в Яндекс.Новостях большие «лоскутные» кластеры очень вредны: их невозможно адекватно проаннотировать, а благодаря своему размеру и разнообразию источников они могут ранжироваться очень высоко.


    1.4. Size vs Quantity



    Значительное ухудшение кластеризации большого числа небольших кластеров должно обходиться дороже небольшого ухудшения кластеризации в крупном кластере.


    2. Метрики качества кластеризации


    Теперь обсудим несколько важных классов метрик качества кластеризации.


    Будем считать заданным конечное множество объектов $D=\{d_1,...,d_N\}$. Множеством кластеров будем называть всякую совокупность его непересекающихся непустых подмножеств. Таким образом, $E \subseteq 2^D$ — множество кластеров, если


    $\forall e_1, e_2 \in E:(e_1 \cap e_2 \ne \emptyset) \Leftrightarrow (e_1 = e_2)$


    При этом множество кластеров не обязательно является покрытием множества объектов: допускается неполная кластеризация. Впрочем, иногда удобно считать каждый некластеризованный элемент тривиальным одноэлементным кластером.


    Будем считать, что определены два множества кластеров: эталонное $T=\{t_1,...,t_n\}$ и построенное алгоритмом $C=\{c_1,...,c_m\}$. Через $t(d)$ и $c(d)$ будем обозначать, соответственно, эталонный и алгоритмический кластеры, которым принадлежит объект $d$.


    2.1. Метрики, основанные на подсчёте пар (классификационные)


    В этом подходе задача кластеризации сводится к бинарной классификации на множестве пар объектов. Пара объектов считается относящейся к положительному классу тогда и только тогда, когда оба объекта относятся к одному и тому же эталонному кластеру. Предсказание считается положительным тогда и только тогда, когда эти объекты относятся к одному и тому же алгоритмическому кластеру.


    Иллюстрация ниже поясняет это определение. Восемь объектов разбиты на три эталонных кластера размеров 3 («жёлтый»), 3 («фиолетовый») и 2 («синий»). Эти же объекты кластеризованы алгоритмом так: «синий» кластер собран абсолютно верно, а вот один из «фиолетовых» объектов ошибочно отнесён в кластер к «жёлтым».



    Тогда здесь суммарно $8 \cdot 8 = 64$ пар объектов, из них:
    $3 \cdot 3 + 3 \cdot 3 + 2 \cdot 2 = 22$ положительных;
    $64 - 22 = 42$ отрицательных.


    Построенная алгоритмом матрица содержит шесть лишних положительных элементов за счёт создания связей между «жёлтыми» объектами и одним из «фиолетовых» объектов, а также теряет четыре элемента из-за потери связей между «фиолетовыми» элементами.


    В терминах качества бинарной классификации получается, что:
    $TP = 18$ пар определены как положительные и при этом являются положительными;
    $FP = 6$ пар определены как положительные, но ими не являются;
    $TN = 36$ пар определены как отрицательные и при этом являются отрицательными;
    $FN = 4$ пары определены как отрицательные, но ими не являются.


    Теперь можно вычислить точность, полноту и любые другие метрики:


    $P = TP / (TP + FP) = 0.75$


    $R = TP / (TP + FN) = 0.82$


    $F_1 = \frac{2PR}{P + R} = 0.78$


    В процессе вычислений можно учитывать тот факт, что матрица симметрична: это вносит изменения в получаемые значения.


    Описанный способ интуитивно очень понятен и прост в реализации. Другая его замечательная особенность в том, что получение оценок не требует построения эталонного разбиения на кластеры: достаточно разметить репрезентативное множество пар объектов.


    Главный недостаток pairwise-метрик — квадратичная зависимость числа порождаемых пар от размера кластера. Из-за этого значение pairwise-метрик может быть обусловлено качеством кластеризации буквально нескольких самых крупных кластеров.


    2.2. Метрики, основанные на сопоставлении множеств


    Для определения метрик этого класса вначале вводятся метрики точности и полноты соответствия между кластером и эталоном:


    $P(c, t) = \frac{ | c \cap t | }{| c |}$


    $R(c, t) = \frac{ | c \cap t | }{| t |}$


    Пример ниже содержит два эталонных кластера: «жёлтый» (y) и «фиолетовый» (v). Единственный алгоритмический кластер содержит 25 жёлтых точек и 10 фиолетовых. Точность соответствия этого кластера жёлтому кластеру составляет 25/35, а фиолетовому — 10/35. Вне кластера находятся ещё пять жёлтых и две фиолетовых точки. Значит, всего имеется 30 жёлтых и 12 фиолетовых точек, поэтому полнота соответствия жёлтому кластеру равна 25/30, фиолетовому — 10/12.



    Физический смысл введённых величин прост: точность равна вероятности выбрать элемент эталонного кластера при выборе случайного элемента из алгоритмического кластера, полнота равна вероятности выбрать элемент алгоритмического кластера при выборе случайного элемента из эталонного кластера. Показатели двойственны:


    $P(c, t) = R(t, c)$


    Далее можно определить и F-меру:


    $F_1(c, t) = \frac{2\cdot P(c, t) \cdot R(c,t)}{ P(c, t) + R(c,t) }$


    Теперь необходимо определить интегральный показатель. Самый известный способ определить его через показатели отдельных соответствий приводит к метрике «чистоты» кластеров, Purity:


    $Purity = \sum_{i=1}^{m}{\frac{|c_i|}{m}{\max_{1 \le j \le n}{P(c_i, t_j)}}}$


    Вводится и двойственная метрика, в которой суммирование и нормировка производятся по эталонным кластерам:


    $IversePurity = \sum_{j=1}^{n}{\frac{|t_j|}{n}{\max_{1 \le i \le m}{P(c_i, t_j)}}}$


    Высокое значение $Purity$ означает, что для кластера найдётся хорошо соответствующий ему эталон. Высокое значение $IversePurity$ — что для эталона найдётся хорошо соответствующий ему алгоритмический кластер. Значит ли это, что близость обеих метрик к единице гарантирует очень хорошее качество кластеризации? К сожалению, нет. Рассмотрим следующий пример:


    $|c_2| \approx |t_2| \gg |t_1| \gg |c_1|$



    Для примера можно взять $|c_2| = 1000$, $|c_1| = 2$, $|t_1| = 20$, $|t_2| = 982$. Кластер $c_1$ полностью находится внутри $t_1$, поэтому:


    $|c_1 \cap t_1| = 2, |c_1 \cap t_2| = 0,$


    $|c_2 \cap t_1| = 18, |c_2 \cap t_2| = 982$


    Отсюда можно вычислить метрики точности для соответствий:


    $P(c_1, t_1) = |c_1 \cap t_1| / |c_1| = 2/2 = 1$


    $P(c_2, t_2) = |c_2 \cap t_2| / |c_2| = 982/1000 = 0.982$


    $P(t_1, c_2) = |t_1 \cap c_2| / |t_1| = 18/20 = 0.9$


    $P(t_2, c_2) = |c_2 \cap t_2| / |t_2| = 982/982 = 1$


    Из этого уже ясно, что показатели Purity и InversePurity высоки для каждого из алгоритмических и эталонных кластеров соответственно. Аккуратное вычисление даёт:


    $Purity =0.9982$


    $IversePurity = 0.9823$


    Обе величины близки к единице, хотя для кластера $t_1$ в действительности нет ни одного хорошего представителя из числа алгоритмических кластеров. Метрики не заметили этого, т. к. при подсчёте Purity кластеру $t_1$ соответствовал кластер $c_1$, а при подсчёте InversePurity — кластер $c_2$. При вычислении двух различных показателей в качестве оптимальных были выбраны различные соответствия!


    Отчасти с этой проблемой помогает справиться F-мера:


    $F = \sum_{j=1}^{n}{\frac{|t_j|}{n}{\max_{1 \le i \le m}{F(c_i, t_j)}}}$


    Использование такого показателя может быть оправданным в некоторых ситуациях, но стоит иметь в виду, что один и тот же кластер может сопоставиться сразу нескольким эталонам. Кроме того, кластеризация элементов из кластеров, не сопоставленных ни одному из эталонов, не оказывает влияния на значение метрики.


    2.3. BCubed-метрики


    Этот класс метрик предлагает взглянуть на кластеризацию с точки зрения одного отдельного элемента. Предположим, пользователь изучает конкретный документ внутри новостного сюжета. Какова доля документов этого сюжета, относящихся к той же теме, что и изучаемый документ? А какую долю документы по этой теме в сюжете составляют от числа всех документов по теме?



    Вполне законные вопросы, и ответ на них приводит к BCubed-метрикам точности и полноты. Они определены для конкретного объекта:


    $BCP(d) = \frac{|c(d) \cap t(d)|}{|c(d)|}$


    $BCR(d) = \frac{|c(d) \cap t(d)|}{|t(d)|}$


    Интегральные показатели определяются усреднением по элементам:


    $BCP = \frac{1}{N}\sum_{d \in D}{BCP(d)}$


    $BCR = \frac{1}{N}\sum_{d \in D}{BCR(d)}$


    BCubed Precision удовлетворяет свойствам Cluster Homogeneity и Rag Bag, а BCubed Recall — свойствам Cluster Completeness и Size vs Quantity. Сводный показатель — F-мера — удовлетворяет всем четырём свойствам:


    $BCF = \frac{2 \cdot BCP \cdot BCR}{BCP + BCR}$


    3. Метрики эталонных кластеров


    В некоторых приложениях полезно оценивать не только интегральные показатели качества, но и качество кластеризации отдельных эталонных кластеров. Поэтому в нашей системе оценки качества все метрики определялись для эталонных кластеров, которые затем агрегировались путём усреднения.


    Рассмотрим, как это работает, на следующем примере. Пусть множество объектов $D=\{a,b,c,d,e,f,g,h,i\}$ состоит из девяти элементов, образующих два эталонных кластера $t_1 = \{a,b,c,d,e\}$ и $t_2=\{f,g,h,i\}$ («зелёный» и «жёлтый» соответственно).


    Алгоритмические кластеры не повторяют эталонные в точности: $c_1 = \{a,b,c,d,g\}$, $c_2=\{e,f,h,i\}$.



    3.1. BCubed


    Введём BCubed-метрики для отдельных эталонных кластеров:


    $BCP(t_i)=\frac{1}{|t_i|} \sum_{d \in t_i}{BCP(d)}$


    $BCR(t_i)=\frac{1}{|t_i|} \sum_{d \in t_i}{BCR(d)}$


    Для рассмотренного примера получим следующие значения метрики точности кластеризации отдельных элементов:


    $BCP(a)=BCP(b)=BCP(c)=BCP(d)=\frac{|t_1 \cap c_1|}{|c_1|}=0.8, BCP(e)=\frac{|t_1 \cap c_2|}{|c_2|}=0.25$


    $BCP(f)=BCP(h)=BCP(i)=\frac{|t_2 \cap c_2|}{|c_2|}=0.75, BCP(g)=\frac{|t_2 \cap c_1|}{|c_1|}=0.2$


    Отсюда метрики точности эталонных кластеров:


    $BCP(t_1)=\frac{BCP(a)+BCP(b)+BCP(c)+BCP(d)+BCP(e)}{5}=\frac{4\cdot 0.8 + 0.25}{5}=0.69$


    $BCP(t_2)=\frac{BCP(f)+BCP(g)+BCP(h)+BCP(i)}{4}=\frac{3\cdot 0.75 + 0.2}{4}=0.6125$


    Аналогично для полноты:


    $BCR(a)=BCR(b)=BCR(c)=BCR(d)=\frac{|t_1 \cap c_1|}{|t_1|}=0.8, BCR(e)=\frac{|t_1 \cap c_2|}{|t_1|}=0.2$


    $BCR(f)=BCR(h)=BCR(i)=\frac{|t_2 \cap c_2|}{|t_2|}=0.75, BCP(g)=\frac{|t_2 \cap c_1|}{|t_2|}=0.25$


    $BCR(t_1)=\frac{BCR(a)+BCR(b)+BCR(c)+BCR(d)+BCR(e)}{5}=\frac{4\cdot 0.8 + 0.2}{5}=0.68$


    $BCR(t_2)=\frac{BCR(f)+BCR(g)+BCR(h)+BCR(i)}{4}=\frac{3\cdot 0.75 + 0.25}{4}=0.625$


    Средневзвешенные по всем эталонным кластерам значения BCP и BCR будут такими:


    $BCP=\frac{BCP(t_1) + BCP(t_2)}{2}=0.65125$


    $BCR=\frac{BCR(t_1) + BCR(t_2)}{2}=0.6525$


    Именно эти характеристики мы и использовали при оценке качества кластеризации.


    3.2. Expected Cluster Completeness


    Разложение качества кластеризации на характеристики точности и полноты бывает очень полезным для анализа и дальнейшего совершенствования алгоритма. Для принятия решений о том, какой из алгоритмов лучше, требуется, впрочем, выработать один-единственный показатель.


    Стандартный способ — F-мера — подходит лишь в ограниченном смысле. Это действительно один показатель, но является ли его значение подходящим для принятия решений? Вовсе не факт.


    В конечном счёте требование к алгоритму заключается в том, чтобы каждому эталонному кластеру сопоставить некоторый уникальный алгоритмический кластер, который служил бы для эталона «представителем». Алгоритмический кластер может представлять только один эталонный кластер. При этом из всех сопоставлений важно лишь одно — самое удачное. Такой ход рассуждений является естественным для многих приложений: например, при анализе поисковых запросов судить о содержании кластера проще всего по тексту типичного представителя, то есть единственного запроса.


    Сопоставление — функция из множества алгоритмических кластеров в множество эталонных кластеров:


    $f:C \rightarrow T$


    Тогда для конкретного эталона и сопоставления $f$ можно вычислить характеристику полноты (cluster completeness):


    ${CC}_f(t) = \max_{c \in f^{-1}(t)}{\frac{|c \cap t|}{|t|}}$


    Среднее значение полноты:


    ${CC}_f(T) = \frac{1}{T} \sum_{t \in T} {CC}_f(t)$


    Теперь возникает вопрос — как именно построить сопоставление, то есть функцию $f$. В действительности никакой конкретный алгоритм не будет работать хорошо: незначительные изменения в кластеризации могут существенно повлиять на сопоставление и сильно изменить значение метрики.


    Поэтому придётся ввести на множестве всех возможных сопоставлений вероятностную меру и затем вычислить математическое ожидание. Пусть вероятность того, что $f(c)=t$, равна


    $P\Big(f(c)=t\Big) = P(c, t) = \frac{|c \cap t|}{|c|}$


    Теперь вероятность выбора функции $f$ определяется через произведение вероятностей выбора всех её значений:


    $P(f) = \prod_{c \in C}{\frac{|c \cap f(c)|}{|c|}} $


    Теперь можно вычислить ожидаемое покрытие для эталонного кластера:


    $ECC(t) = \sum_{f: C \rightarrow T}{P(f) \cdot CC_f(t)}$


    Интегральный показатель можно определить так:


    $ECC = \frac{1}{|T|} \sum_{t \in T}{ECC(t)}$


    Либо эквивалентно:


    $ECC = \sum_{f: C \rightarrow T}{P(f) \cdot {CC}_f(T)}$


    Опишу и другой способ понять эту метрику. Пусть с эталоном $t$ пересекаются кластеры $c_1$, $c_2$, ..., $c_k$, пронумерованные в порядке невозрастания размера пересечения:


    $|t \cap c_1| \ge |t \cap c_2| \ge ... \ge |t \cap c_k| $


    Кластер $c_1$ выбирается в соответствие эталону $t$ с вероятностью


    $P\Big(f(c_1) = t\Big) = \frac{|c_1 \cap t|}{|c_1|}$


    При этом покрытие будет равно


    $R(c_1, t) = \frac{ | c_1 \cap t | }{| t |}$


    Поскольку это максимально возможное покрытие, которое может обеспечить один из кластеров, то выбранные для других кластеров сопоставления не играют роли. Так что в этом случае покрытие окажется равным $R(c_1, t)$.


    Если же для кластера $c_1$ выбрано другое сопоставление, то с вероятностью $p(c_2, t)$ эталону $t$ будет сопоставлен кластер $c_2$. Тогда покрытие окажется равным $R(c_2, t)$. Это рассуждение можно продолжить, и в конце концов мы получим, что математическое ожидание покрытия равняется


    $P(c_1, t) \cdot R(c_1, t) + P(c_2, t) \cdot R (c_2, t) \cdot \Big(1 - P(c_1,t)\Big) + ...$


    Код для вычисления метрики ECC для конкретного эталонного кластера получается очень простым. Вектор sortedMatchings состоит из всех кластеров, которые пересекаются с эталоном, он отсортирован по неубыванию полноты. Точность и полноту каждого соответствия эталону можно вычислить при помощи методов Precision() и Recall() соответственно. Тогда:


    double ExpectedClusterCompleteness(const TMatchings& sortedMatchings) {
        double expectedClusterCompleteness = 0.;
        double probability = 1.;
        for (const TMatching& matching : sortedMatchings) {
            expectedClusterCompleteness += matching.Recall() * matching.Precision() * probability;
            probability *= 1. - matching.Precision();
        }
        return expectedClusterCompleteness;
    }

    Интересно, что в этой метрике агрегирующей функцией для точности и полноты в итоге оказалась не $F_1$-мера, а простое произведение!


    Вычислим теперь ECC для эталонных кластеров, с которых начался пункт 3. Максимальное покрытие эталону $t_1$ обеспечивает кластер $c_1$, а эталону $t_2$$c_2$. Поэтому:


    $ECC(t_1) = R(c_1, t_2) \cdot P(c_1, t_1) + R(c_2, t_1) \cdot P(c_2, t_1) \cdot \Big(1 - P(c_1, t_1)\Big) $
    $ECC(t_1) = {0.8}^2 + 0.2 \cdot 0.25 \cdot (1 - 0.8) = 0.65$


    $ECC(t_2) = R(c_2, t_2) \cdot P(c_2, t_2) + R(c_1, t_2) \cdot P(c_1, t_2) \cdot \Big(1 - P(c_2, t_2)\Big)$
    $ECC(t_2) = {0.75}^2 + 0.25 \cdot 0.2 \cdot (1 - 0.75) = 0.575$


    Интегральное значение вычисляется как среднее значение по всем эталонам, поэтому:


    $ECC = \frac{ECC(t_1) + ECC(t_2)}{2} = 0.6125$


    4. Реализация


    Метрики, описанные в пункте 3, реализованы на C++ и выложены под лицензией MIT на GitHub. Реализация компилируется и запускается как на Linux, так и на Windows.


    Программу легко собрать:


    git clone https://github.com/yandex/cluster_metrics/ .
    cmake .
    cmake --build .

    После этого её можно запустить для того же примера, что разбирался в пункте 3. Расчёты из статьи совпадают с показаниями программы!


    ./cluster_metrics samples/sample_markup.tsv samples/sample_clusters.tsv
    ECC   0.61250 (0.61250)
    BCP   0.65125 (0.65125)
    BCR   0.65250 (0.65250)
    BCF1  0.65187 (0.65187)

    В скобках указываются значения метрик для «оптимистичного» сценария, когда все неразмеченные элементы в действительности относятся к тем эталонам, с которыми пересекаются содержащие их кластеры. На практике это даже слишком оптимистичная оценка, так как каждый объект может относиться только к одной конкретной теме, но не ко всем сразу. Тем не менее, эта оценка полезна для случаев, когда алгоритм уж очень сильно меняет множество кластеризованных элементов. Если значение метрики существенно меньше оптимистичной оценки — стоит расширить разметку.


    5. Как понять, что метрики работают


    После того, как метрики придуманы, нужно аккуратно убедиться в том, что они действительно позволяют принимать правильные решения.


    Мы построили систему экспертного сравнения алгоритмов кластеризации. Всякий раз, как алгоритм претерпевал существенные изменения, асессоры размечали изменения. Интерфейс, если изображать схематично, выглядел так:



    В центре экрана находился эталонный кластер: были перечислены все документы, отнесённые к нему в процессе разметки. С двух сторон от него отображались кластеры, построенные двумя соревнующимися алгоритмами, имеющие непустое пересечение с эталоном. Стороны для алгоритмов выбирались случайным образом, чтобы асессор не знал, с какой стороны находится старый алгоритм, а с какой — новый. Порядок кластеров для каждого алгоритма определялся сортировкой по произведению точности на полноту соответствия — совсем как в метрике ECC!


    Зелёным помечались документы, относящиеся к выбранному эталонному кластеру, красным — относящиеся к другому эталонному кластеру. Серым обозначались неразмеченные документы.


    Асессор смотрел на этот экран, изучал документы, при необходимости определял правильные эталонные кластеры для неразмеченных документов и в конце концов принимал решение о том, какой из алгоритмов сработал лучше. После разметки нескольких сотен эталонных кластеров можно было получить статистически значимый вывод о превосходстве того или иного алгоритма.


    Такую процедуру мы использовали в течение нескольких месяцев, пока не обнаружили, что асессоры всегда выбирают тот алгоритм, для которого выше значение метрики ECC! Если показатели ECC различались хотя бы сколько-то существенно, асессоры всегда выбирали тот же вариант, что и метрика, это происходило буквально в 100% случаев. Поэтому со временем мы отказались от процедуры ручной приёмки и принимали решения просто по метрикам.


    Интересно рассказать, что свойства метрик кластеризации из пункта 1 также исследовались на соответствие интуитивным представлениям о качестве кластеризации. В уже цитировавшейся статье описывается следующий эксперимент: для каждого правила формулировался пример — эталонное разбиение некоторого множества объектов и два альтернативных способа кластеризовать эти же объекты.



    Пример сравнения двух разбиений на кластеры для свойства Cluster Completeness


    Далее сорок асессоров выносили вердикты о том, какой из двух способов лучше, и их ответы сравнивались с вердиктами правил. Оказалось, что с каждым из правил Cluster Homogeneity, Cluster Completeness, Rag Bag не согласился только один из сорока асессоров, а свойству Size vs Quantity не противоречил никто.


    Это очень интересное исследование, хотя оно и обладает очевидными недостатками: пример для каждого правила был только один, а восприятие качества кластеризации, очевидно, сильно связано с геометрической интерпретацией.


    Уверенности в метриках, описанных в пункте 3, намного больше, так как мы исследовали их на многих сотнях или даже тысячах примеров.


    Закончить, однако, хочу предостережением: в каждой новой задаче применимость тех или иных метрик нужно изучать заново. Мне лишь остаётся надеяться, что статья поможет всем, кто будет заниматься этой нелёгкой работой в будущем.

    Яндекс
    Как мы делаем Яндекс

    Comments 10

      –2
      Дела давно минувших дней
      Сейчас-то всё проще, в яндекс.новостях кластер по сути один
        0
        Предположим, пользователь изучает конкретный документ внутри новостного сюжета. Какова доля документов этого сюжета, относящихся к той же теме, что и изучаемый документ? А какую долю документы по этой теме в сюжете составляют от числа всех документов по теме?


        Моя матрица зависла и сломалась.
          0
          Позвольте мне предложить еще одну метрику и попросить Вас ответить, насколько она хороша.

          Пусть у меня имеется множество и некоторое его разбиение на классы, которое я назову стандартным. По сути, принадлежность к тому или иному классу стандартного разбиения — это некоторое свойство, назовем его классовым. Если случайно из этого множества выбрать элемент x и настолько же случайно — какой-нибудь элемент y из содержащего x класса, то их классовые свойства будут совпадать. Иначе говоря, при такой схеме выбора будут отсутствовать ошибки классового соответствия.

          Пусть теперь на том же множестве как-то выделено еще одно разбиение, называемое кластерным. Снова выберем из всего множества случайный элемент x, а затем из кластера, которому принадлежит x, не менее случайно вберем элемент y. Если кластеры не точно совпадают с классами, то имеется некоторая вероятность p, что классовые свойства x и y не совпадают. Эту вероятность p я и хочу считать метрикой качества для приближения кластерным разбиением исходного разбиения на классы.
            0

            То что вы предлагаете описано в п 2.2. но там используется Precision и Recall, а вы предлагаете использовать Accuracy.
            Практика показывает, что не смотря на кажущуюся интуитивность этой метрики, она плохо работает в случае дисбаланса классов.
            Поэтому в ML не принято использовать Accuracy.

              0
              То что вы предлагаете описано в п 2.2.

              Возможно я не до конца понял, что именно описано в пункте 2.2, но мне кажется, там речь идет о сопоставлении кластеров и эталонных классов. Тот метод, который я описал выше, совершенно не требует, чтобы такое сопоставление осуществлялось: все что нужно — это однородность классовых свойств в каждом кластере.

              У P-метода, давайте его так называть, есть правда детская болезнь: метрика обнулится, если каждый элемент считать отдельным кластером. Однако ответить внутри чистой теории множеств, почему одноэлементные кластеры — это плохо, мне не представляется возможный. Универсальный методом здесь могла быть оценка симметричной взаимной информации, но опять же: почему необходимо считать задачу симметричной (почему классы должны стремиться состоять из элементов одного кластера) — не понятно.

              Если излишняя дискретизация на практике приводит к каким-то потерям, то наверное модель этих потерь должна быть добавлены к обоснованию, почему та или иная метрика кластеризации плоха или хороша, иначе «плохо» и «хорошо» остаются неопределенными эмоциональными суждениями.
                0

                Я как раз хотел предложить метрику на основе взаимной информации, но вы меня опередили :) сейчас ниже напишу что я придумал.

              0

              Если я всё правильно понял, это BCubed Precision. Для отдельного элемента BCP равняется в точности вероятности того, что другой случайный элемент из того же кластера относится к тому же эталону, что и выбранный элемент, а интегральный показатель — простое усреднение, эквивалентное равновероятному выбору элементов.


              Эта метрика очень хорошая, но учитывает только точность соответствий, но не полноту, так что не может использоваться изолированно.

                +1
                Спасибо за ответ, теперь я вижу, что моя метрика действительно похожа на усреднение BCubed Precision по некоторой мере.
              0

              Предлагаю рассмотреть такую метрику на основе взаимной информации. В статье предполагается, что модельное разбиение соотносит кластеры "истиным" в предлагаемой метрике это не требуется и она симметрична.


              Разбиение на кластеры подражает некоторое распределение. Можно считать (но не обязательно), что это распределение порождено некоторой случайной величиной.


              Это означает, что мы можем посчитать взаимную информацию распределений.
              Итак. Пусть X — истинное распределение, порождаемое С.В. x, а Y — модельное, порождаемое соответственно y.
              Тогда мы можем посчитать их взаимную информацию по формуле


              (Hx +Hy - Hxy) / Hxy

              Здесь Hx — энтропия x, Hy — энтропия y, а Hxy — энтропия совместного распределения x и y.
              Энтропия — это размерная величина (измеряется в битах или натах), зависит от основания логарифма, поэтому если нам нужна безразмерная метрика, то нужно нормировать.
              Предложенный способ нормировки стандартный, но не единственный.
              Можно показать, что определённое таким образом число всегда будет в интервале [0, 1]


              Пример

              imageddd


              |   | 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


              В примере видно, что получаемые значения оказываются, на первый взгляд, ниже ожидаемых. Не знаю хорошо это или плохо.

                0

                Есть два важных класса метрик, которые я не рассматривал :) При этом они упоминаются в цитирующейся статье.


                Это информационные метрики на основе энтропии (к этому классу относится описанная вами) и метрики на основе edit distance. В цитируемой статье оба класса коротко рассматриваются, основной проблемой является то, что для них не выполнено условие Rag Bag.


                У этих метрик хорошие аналитические свойства, поэтому многие их, действительно, используют. Я в свою очередь их не люблю за то, что не вижу ясного соответствия между физическим смыслом происходящего на сервисе и физическим смыслом метрики. Из-за этого никогда их и не использовал =)

              Only users with full accounts can post comments. Log in, please.