Перейдем к изучению оценок качества кластеризации. Меры качества кластеризации можно разделить на две группы. Первая группа - это качество по отношению к некоторому эталонному разбиению. Для некоторых наборов данных уже известно истинное разбиение на кластеры и мы хотим просто сравнить полученную кластеризацию с этим истинным разбиением. Такие методы оценок называются External measures и по-русски я их буду называть мерой качества разбиения. Вторая группа мер - это меры качества по отношению к некоторым нашим представлениям о том, что такое хорошая кластеризация. По-русски я буду их называть мера валидности разбиения. А по-английски они называются Internal measures. Первая мера качества по отношению к эталонному разбиению - это Rand Index. Обозначим через π с крышкой полученное разбиение после кластеризации, и через π со звездочкой эталонным разбиением. Тогда индекс Рэнда будет считаться по такой незамысловатой формуле. a - это количество пар объектов, которые находятся в одинаковых кластерах и в π со звездочкой, и в π с крышкой. d - это количество пар объектов, которые находятся в разных кластерах и в π со звездочкой и в π с крышкой. b и с - это количество пар объектов в одном и том же кластере, в π со звездочкой, но в разных π с крышкой, и наоборот. Но если переобозначить немножко индекс Рэнда через true positive, false positive, true negative и false negative, то получится такая же формула. Почему мы рассматриваем именно пары объектов. Дело в том, что сама метка кластера не играет никакой роли. Вот, например, на этом слайде у нас есть 8 объектов, разделенных на три кластера. В данном случае π1 и π2 задают абсолютно одинаковые разбиения. Значит, попросту сравнивать метки нам не имеет смысла. Поэтому нужно рассматривать пары объектов. Давайте рассчитаем индекс Рэнда для какого нибудь примера. У нас есть эталонное разбиение π со звездочкой на три кластера и полученное нами разбиение π с крышкой, уже на четыре кластера. Первым делом нужно построить матрицу с сопряжением. По строкам отложены метки полученного разбиения, а по столбцам - метки эталонного разбиения. Соответственно, на пересечение столбов и строк отложено количество объектов, которые попали в ту или иную метку того или иного разбиения. В самом нижнем, в самой нижней строке и в самом правом столбце указаны просто суммы по строкам и столбцам. Для начала посчитаем величину true positive плюс false positive. Для этого нам нужно взять сумму элементов по строкам и от каждого из них взять сочетание по два. У нас там везде двойки. Поэтому, сумма true positive плюс false positive будет равна четырем. Аналогично считается сумма true positive плюс false negative - это уже сумма по столбцам и она будет равна 9. Для того, чтобы просто посчитать true positive, можно взять элементы внутри этой матрицы перемешивания и взять от каждого из них сочетания по два. Потом просуммировать - получится 3. И для того чтобы посчитать сумму всех true postive, false posititve, false negative и true negative - нужно посчитать просто общее количество пар среди наших объектов. Их будет 28. Соответственно, теперь индекс Рэнда будет равен 21 делить на 28 или 0,75. Однако, индекс Рэнда не лишен недостатков и одним из таких недостатков является то, что для случайных разбиений мы можем получить довольно высокое значение индекса Рэнда. Искоренить этот недостаток призвана корректировка. Выглядит она следующим образом где e от индекса Рэнда - это некоторое ожидаемое значение между разбиением π со звездочкой и π с крышкой. Максимум - это максимальное значение. Также, для измерения качества разбиение можно считать уже известные вами меры вида Precision, Recall и F-меры. В данном случае формулы их совершенно не меняется. Меняется просто способ по расчету true positive, false positive и так далее. Теперь изучим меры валидности кластеров. Как я уже сказал, мера валидности кластеров измеряется по отношению к нашему представлению о том, что такое хорошая кластеризация. Что такое хорошая кластеризация? Во-первых, объекты внутри одного кластера должны быть компактными, то есть очень похожи друг на друга, и, при этом, разные кластеры должны располагаться далеко друг от друга, то есть быть максимально не похожими. И разные меры качества считают вот эти критерии по-разному и поэтому их очень много. Эти меры можно использовать для, например, подбора параметров алгоритмов, то есть вы прогоняете один и тот же алгоритм кластеризации с разными параметрами, смотрите на меры и выбираете наилучшую настройку алгоритма по отношению к этой мере. Первая мера - это силуэт. Пусть дана кластеризация на К кластеров и объект Xi попал в кластер Ck. Тогда для этого объекта мы можем посчитать следующие величины. Во-первых, это среднее расстояние от объекта до всех остальных объектов его же кластера. Вторая величина B(i) - это минимальное среднее расстояние от этого объекта до объекта какого-то кластера C(j). Таким образом, как раз компактность у нас выражается величиной A(i), а разделимость B(i). Мы считаем просто разность B(i) и А(i) деленная на максимальные из этих двух величин. Получаем некоторое число от минус единицы до единицы. На этом слайде изображён пример расчета силуэта для следующей кластеризации на четыре кластера. Слева вы видите величину силуэта для каждого объекта, каждого кластера, упорядоченные по убыванию. Получаются такие лезвия. А красной линией отложено среднее значение силуэта по всей выборке. Это как раз и будет наша мера качества разбиения в целом. Вторая мера - это индекс данных. Для того чтобы ее получить, нам нужно научиться считать расстояние между кластерами и мы его определим как минимальное расстояние между объектами из двух разных кластеров. И вторая величина - это диаметр кластеров, то есть мы будем считать уже максимальное расстояние между всеми парами объектов, но уже внутри одного кластера. И тогда индекс будет равен просто отношению минимального расстояния между кластерами, деленное на максимальный диаметр кластера. И последний индекс на сегодня - это Index Davies-Bouldin. Для того, чтобы его посчитать, нам нужно научиться считать разброс данных внутри кластера. Но это будет просто среднее расстояние между объектами внутри кластера и центроидом этого кластера. Тогда для того, чтобы посчитать индекс, для каждого кластера нам нужно найти другой кластер, для которого максимальна величина сумма разброса этих кластеров, деленная на расстояние между центроидами этих двух кластеров. Ну, и потом мы это просто усредняем. Таким образом, мы с вами разобрали две группы расчетов мер качества кластеризации. Первая, это расчет качества по отношению к некоторому эталонному разбиению. И вторая группа, это расчет качества по отношению к некоторым представлениям о том, что такое хорошая кластеризация.
