Оценка кластеров

Null hypothesis

Способы представления кластеризаций

matching(confusion) matrix)

membership matrix

Расстояния между двумя разбиениями (external indexes)

Евклид

Rand index

Cophenetic correlation

Internal indexes

Average scattering

Connectivity

Dunn index

Davies-Bouldin index

Hubert Г-statistic

wb ratio

Silhouettes

Stability

Soft (R packages)

Unsorted

Upper tail rule

Gap statistic

Cluster ensembles

Clustering categorical data

Пакет clue

Литература

 

 

Бессмысленно использовать стандартные методы (F-test, t-test, непараметрику) для сравнения кластеров (т.е. для выявления, есть ли кластеры вообще в данных), поскольку алгоритм и так нацелен на макс. разделение данных. Например, если взять данные из норм. распределения, откластеризовать и сравнить, то различия будут очень сильно значимыми.

 

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

 

основные критерии хорошей кластеризации:

• compactness
• separation

 

There are three different techniques for evaluating the result of the clustering algorithms

• External Criteria

• Internal Criteria

• Relative Criteria

 

Null hypothesis

 

• random graph – All n x n rank order proximity matrices are equally likely и имеет вероятность 1/[n(n-1)/2]! Но: неравенство треугольника не позволяет реализоваться всем вариантам. Appropriate for ordinal proximities between pairs of data objects
• random label – all permutations of n labels are equally likely. For all data types.
• random position – all sets of n locations in some region of a d-dimensional space are equally likely. Область – гиперкуб, гиперсфера. Appropriate for ratio data

 

Способы представления кластеризаций

matching(confusion) matrix)

N (размера g1 x g2), n_ij is the number of objects in group i of partition G1 that are also in group j of partition G2.

Q: можно ли так представить случаи когда один объект принадлежит нескольким кластерам?

 

membership matrix

матрица M , число строк= числу объектов, число колонок = числу кластеров

>0 -- “belongingness" or membership of object i to class j .

Сумма по строке =1,

M₁^TM₂ – получаем confusion matrix, где M₁ и M₂ - матрицы для разных кластеризаций.

 

MM^T - получаем co-membership matrix

 

Разбиение (partitioning) может быть:

• soft - объект может принадлежать нескольким кластерам
• hard - объект принадлежит только одному кластеру. => Только одно в строке ненулевое и равно 1.

 

Расстояния между двумя разбиениями (external indexes)

Евклид

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

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: на вход только квадратную матрицу (добавить строки с нулями если нужно).

Rand index

для жестких разбиений, нет взвешивания точек

Для двух точек 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

Cophenetic correlation

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

 

Это линейный коэффициент корреляции между расстояниями, полученными по дереву и исходной матрицей расстояний. Строится корреляция между соответствующими элементами двух 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

 

Internal indexes

оценить качество кластеризации только по самим кластерам

Average scattering

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').

 

Connectivity

- 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 – число переменных

 

Dunn index

чем больше тем лучше (т.к. нам хорошо большие расстояния между кластерами и маленькие диаметры самих кластеров)

 

min разделение / max диаметр

 

очень чувствителен к выбросам

 

Davies-Bouldin index

измеряет среднее расстояние между каждым кластером и наиболее близким к нему кластером.

R_ij – мера сходства кластеров, основанная на дисперсии кластеров s_i

,

Тогда сам индекс это

Чем меньше, тем лучше

Hubert Г-statistic

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

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

отношение среднего внутрикластерного расстояния к среднему междукластерному расстоянию: wb.ratio=average.within/average.between,

Чем меньше, тем лучше

 

Silhouettes

оценивает насколько кластеризация соответствует расстояниям между точками

Для i-ой точки:

• a_i – среднее расстояние относительно от всех других точек в своем кластере
• d(i,c) – среднее расстояние относительно всех других точек в кластере с
• b_i – min d(i,c)

silhouette width для i-ой точки =

 

average silhouette= если >0.5 то имеется осмысленное разбиение данных

<0.2 –данные не имеют кластерной структуры

Можно использовать для определения числа кластеров

3 кластера (слева) лучше чем 4 (справа)

 

Stability

аналог кросс-валидации

удалять поочередно по одной переменной и смотреть как изменяется состав кластеров

 

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. чем меньше тем лучше

C^i,0 – i-ый кластер без удаленных переменных

 

Average Distance (AD):

 

Average Distance between Means (ADM):

 

 

Soft (R packages)

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

 

Unsorted

Upper tail rule

для определения числа групп в иерархической кластеризации. Mojena (1977)

a_i – уровень иерархии (т.е. когда произошло слияние кластеров) при наличии n-i объектов

предлагается использовать число групп тогда, когда будет , где с- константа (1.25 до 3.5), - среднее по первым использованным уровням, - ст отклонение величины альфа для этих первых уровней.

Также полезно строить график в зависимости от числа кластеров. Излом графика – число групп.

 

излом при 3 кластерах, также интересны точки 5 и 7

Gap statistic

Tibshirani(2001)

сравнивать внутрикластерную дисперсию с той, которая была бы при reference null distribution.

 

равномерное распределение по диапазону значений для конкретной переменной

равномерное распределение вдоль box aligned with the principal components

 

 

Cluster ensembles

 

Clustering categorical data

 

Пакет clue

cl_class_ids – получаем метки классов (можно и из soft clustering)

cl_consensus – получить консенсусную кластеризацию из ансамбля кластеризаций

 

 

Литература

1. A. Gordon, Classification, 1999
2. Martinez&Martinez, Exploratory Data Analysis with MATLAB, 2005
3. Rencher Methods of Multivariate Analysis

 

посмотреть Gordon, p 62 – это вычисляет cluster.stats{fpc}

 

 

Поискать:

Everitt, Landau, Leese 2001

Milligan Cooper (1985) – review of methods for estimating number of clusters