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
Uppertailrule
для определения числа групп в иерархической кластеризации. Mojena (1977)
ai – уровень иерархии (т.е. когда произошло слияние кластеров) при наличии n-iобъектов
предлагается использовать число групп тогда, когда будет , где с- константа (1.25 до 3.5), – среднее по первым использованным уровням, – ст отклонение величины альфа для этих первых уровней.
Также полезно строить график в зависимости от числа кластеров. Излом графика – число групп.
излом при 3 кластерах, также интересны точки 5 и 7
Gapstatistic
Tibshirani(2001)
сравнивать внутрикластерную дисперсию с той, которая была бы при referencenulldistribution.
равномерное распределение по диапазону значений для конкретной переменной
равномерноераспределениевдоль box aligned with the principal components
Расстояния между двумя разбиениями (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: на вход только квадратную матрицу (добавить строки с нулями если нужно).
Randindex
для жестких разбиений, нет взвешивания точек
Для двух точек xi и xj может быть 4 варианта:
группировкисовпадают,если
1. xiand xjare put in the same cluster in G1 and G2.= a
2. xiand xjare in different clusters in G1 and in different clusters in G2. = b
группировкинесовпадают, если
1. xiand xjare in the same cluster in G1 and different clusters in G2. = c
2. xiand xjare in different clusters in G1 and the same cluster in G2.= d
вычисляется пропорция совпадающих группировок из общего числа возможных группировок
растет с числом кластеров, очень узкий интервал значений.
Поэтому используют только adjustedRandindex
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
Copheneticcorrelation
можно использовать как для сравнения двух деревьев (или двух матриц расстояний), так и для сравнения насколько хорошо дерево представляет расстояния между объектами (т.е. проверка качества кластеризации, не требующее экспертной кластеризации)
Это линейный коэффициент корреляции между расстояниями, полученными по дереву и исходной матрицей расстояний. Строится корреляция между соответствующими элементами двух distancematrix. Для оценки значимости – permuterows/columnsи строим null-distribution. Др. названия: Manteltest (R: mantel.randtest, пакет ade4)
Сopheneticdistance между двумя объектами – уровень intergroupdissimilarity на котором объекты были впервые объединены в один кластер. This distance has many ties and restrictions.
в MATLAB cophenet, в R cophenetic
Способы представления кластеризаций
matching(confusion) matrix)
N (размера g1 x g2), nijis the number of objects in group i of partition G1 that are also in group j of partition G2.
Q: можно ли так представить случаи когда один объект принадлежит нескольким кластерам?
membershipmatrix
матрица M , число строк= числу объектов, число колонок = числу кластеров
>0–“belongingness” or membership of object ito class j .
Сумма по строке =1,
M1TM2 – получаем confusionmatrix, где M1 иM2 – матрицы для разных кластеризаций.
MMT – получаем co-membership matrix
Разбиение (partitioning) можетбыть
- soft – объект может принадлежать нескольким кластерам
- hard – объект принадлежит только одному кластеру. => Только одно в строке ненулевое и равно 1.
Список источников
- bioinformatics.ru