Обновлено 24.03.2009 Автор: Administrator
Это мои рабочие записи по методам кластеризации. К сожалению, у меня пока нет времени привести конспект в пристойный вид, но вдруг это кому-то окажется полезным. С удовольствием отвечу на любые вопросы в комментариях или на форуме . Часть 2Способы представления кластеризаций
Расстояния между двумя разбиениями (external indexes)
Бессмысленно использовать стандартные методы (F-test, t-test, непараметрику) для сравнения кластеров (т.е. для выявления, есть ли кластеры вообще в данных), поскольку алгоритм и так нацелен на макс. разделение данных. Например, если взять данные из норм. распределения, откластеризовать и сравнить, то различия будут очень сильно значимыми.
По этой же причине нельзя использовать нулевую гипотезу, когда объекты распределены случайным образом по кластерам. ???
основные критерии хорошей кластеризации:
There are three different techniques for evaluating the result of the clustering algorithms
• External Criteria
• Internal Criteria
• Relative Criteria
N (размера g1 x g2), nij is the number of objects in group i of partition G1 that are also in group j of partition G2.
Q: можно ли так представить случаи когда один объект принадлежит нескольким кластерам?
матрица M , число строк= числу объектов, число колонок = числу кластеров
>0 -- “belongingness" or membership of object i to class j .
Сумма по строке =1,
M1TM2 – получаем confusion matrix, где M1 и M2 - матрицы для разных кластеризаций.
MMT - получаем co-membership matrix
Разбиение (partitioning) может быть:
метки классов могут быть перепутаны, при этом разбиения останутся одинаковыми.
M – membership matrix. Т.е. может быть и soft -partitioning
For hard partitions, both Manhattan and squared Euclidean dissimilarity give twice the transfer distance, which is the minimum number of objects that must be removed so that the implied partitions (restrictions to the remaining objects) are identical. This is also known as the R-metric, i.e., the number of augmentations and removals of single objects needed to transform one partition into the other, and the partition-distance in Gusfield (2002).
Евклид – эквивалентно максимизации trace of cluster crosstable
Грубый подход – k! вариантов (k – число кластеров)
Hungarian method – k^3/ Задача о назначениях (linear sum assignment problem or weighted bipartite matching)
Soft: пакет lpSolve, функция lp.assign, решает задачу о назначениях. NB: на вход только квадратную матрицу (добавить строки с нулями если нужно).
для жестких разбиений, нет взвешивания точек
Для двух точек xi и xj может быть 4 варианта:
группировки совпадают, если
1. xi and xj are put in the same cluster in G1 and G2. = a
2. xi and xj are in different clusters in G1 and in different clusters in G2. = b
группировки не совпадают, если
1. xi and xj are in the same cluster in G1 and different clusters in G2. = c
2. xi and xj are in different clusters in G1 and the same cluster in G2.= d
вычисляется пропорция совпадающих группировок из общего числа возможных группировок :
растет с числом кластеров, очень узкий интервал значений.
Поэтому используют только adjusted Rand index
SS | #pairs where both points belongs to the same cluster in both partitionings |
SD | #pairs where both points belongs to the same cluster in partitioning P but in P' do not, |
DS | #pairs where in partitioning P both point belongs to different clusters but in P' do not, |
DD | #pairs where both objects belongs to different clusters in both partitionings. |
M | SS + SD + DS +DD |
m1 | SS+SD |
m2 | SS+DS |
Rand statistic | R = (SS + DD)/M |
Jaccard coefficient | J = SS/(SS + SD + DS). Тоже самое, что Rand, но не учитывает DD |
Folkes and Mallows index | FM = sqrt(SS/(SS + SD))*sqrt(SS/(SS + DS)) |
Russel and Rao index | RR = SS/M |
Phi index | Ph = (SS*DD - SD*DS)/((SS+SD)(SS+DS)(SD+DD)(DS+DD)). |
Г-statistics | Г=M*SS-m1*m2/sqrt(m1*m2*(M-m1)*(M-m2)) |
Обычно эти индексы нормализуют: , где E() =mean
можно использовать как для сравнения двух деревьев (или двух матриц расстояний), так и для сравнения насколько хорошо дерево представляет расстояния между объектами (т.е. проверка качества кластеризации, не требующее экспертной кластеризации)
Это линейный коэффициент корреляции между расстояниями, полученными по дереву и исходной матрицей расстояний. Строится корреляция между соответствующими элементами двух distance matrix. Для оценки значимости – permute rows/columns и строим null-distribution. Др. названия: Mantel test (R: mantel.randtest, пакет ade4)
Сophenetic distance между двумя объектами – уровень intergroup dissimilarity на котором объекты были впервые объединены в один кластер. This distance has many ties and restrictions.
в MATLAB cophenet, в R cophenetic
оценить качество кластеризации только по самим кластерам
Let scatter for set X assigned as sigma(X) be defined as vector of variances computed for particular dimensions. Average scattering for clusters is defined as:
Scatt = (1/|C|) * sum{forall i in 1:|C|} ||sigma(Ci)||/||sigma(X)|| , where:
|C| | - number of clusters, |
i | - cluster id, |
Ci | - cluster with id 'i', |
X | - set with all objects, |
||x|| | - sqrt(x*x'). |
- jth nearest neighbor of observation i.
= 0 if i and j are in the same cluster and 1/j otherwise.
connectivity is defined as (between 0 and infinity, should be minimized)
N- общее число объектов, M – число переменных
чем больше тем лучше (т.к. нам хорошо большие расстояния между кластерами и маленькие диаметры самих кластеров)
min разделение / max диаметр
очень чувствителен к выбросам
измеряет среднее расстояние между каждым кластером и наиболее близким к нему кластером.
Rij – мера сходства кластеров, основанная на дисперсии кластеров si
,
Тогда сам индекс это
Чем меньше, тем лучше
проверять гипотезу о корреляции между матрицей расстояний и матрицей, показывающей принадлежат ли объекты одному классу.
Q: это тоже самое что Goodman-Kruskal index?
correlation between distances and a 0-1-vector where 0 means same cluster, 1 means different clusters. See Haldiki et al. (2002).
отношение среднего внутрикластерного расстояния к среднему междукластерному расстоянию: wb.ratio=average.within/average.between,
оценивает насколько кластеризация соответствует расстояниям между точками
Для i-ой точки:
silhouette width для i-ой точки =
average silhouette= если >0.5 то имеется осмысленное разбиение данных
<0.2 –данные не имеют кластерной структуры
Можно использовать для определения числа кластеров
3 кластера (слева) лучше чем 4 (справа)
аналог кросс-валидации
удалять поочередно по одной переменной и смотреть как изменяется состав кластеров
Average Proportion of Non-overlap (APN)
average proportion of observations not placed in the same cluster by clustering based on the full data and clustering based on the data with a single variable removed. чем меньше тем лучше
Ci,0 – i-ый кластер без удаленных переменных
Average Distance (AD):
Average Distance between Means (ADM):
clv - misc external and internal indexes for cluster validity : within and between-cluster scatter measures, Davies-Bouldin, Dunn,Rand, Russel-Rao, Folkes-Mallows, confusion matrices, etc.
similarity index – optimal assignment
Nice package, easy to use.
clValid – internal and stability measures. Also can use data from GO
clusterSim - поиск оптимального расстояния, нормализации и метода кластеризации. Не использовать.
unsorted
There are several R packages that also perform cluster validation and are available from CRAN or Bioconductor. Examples include the clustIndex() function in package cclust (Dimitriadou, 2006), which performs different validation measures in three classes, cluster.stats() and clusterboot() in package fpc (Hennig, 2006), the clusterRepro (Kapp and Tibshirani, 2006) and packages, and the clusterStab (MacDonald et al., 2006) package from Bioconductor. The cl_validity() function in package clue (Hornik, September 2005b) does validation for both paritioning methods (“dissimilarity accounted for”) and hierarchical methods (“variance accounted for”), and function fclustIndex() in package e1071
для определения числа групп в иерархической кластеризации. Mojena (1977)
ai – уровень иерархии (т.е. когда произошло слияние кластеров) при наличии n-i объектов
предлагается использовать число групп тогда, когда будет , где с- константа (1.25 до 3.5),
- среднее по первым использованным уровням,
- ст отклонение величины альфа для этих первых уровней.
Также полезно строить график в зависимости от числа кластеров. Излом графика – число групп.
излом при 3 кластерах, также интересны точки 5 и 7
Tibshirani(2001)
сравнивать внутрикластерную дисперсию с той, которая была бы при reference null distribution.
равномерное распределение по диапазону значений для конкретной переменной
равномерное распределение вдоль box aligned with the principal components
cl_class_ids – получаем метки классов (можно и из soft clustering)
cl_consensus – получить консенсусную кластеризацию из ансамбля кластеризаций
посмотреть Gordon, p 62 – это вычисляет cluster.stats{fpc}
Поискать:
Everitt, Landau, Leese 2001
Milligan Cooper (1985) – review of methods for estimating number of clusters
< Предыдущая | Следующая > |
---|