Конспект по методам кластеризации 1

Это мои рабочие записи по методам кластеризации. К сожалению, у меня пока нет времени привести конспект в пристойный вид, но вдруг это кому-то окажется полезным. С удовольствием отвечу на любые вопросы в комментариях или на форуме . Часть 1

Общие вопросы

Расстояния

Расстояния между бинарными переменными

Расстояния между ordinal переменными (теми, которые могут быть упорядочены)

Расстояния между вещественными переменными

расстояние Махаланобиса:

Расстояния между смешанными переменными

Dissimilarity matrices

Пропущенные значения

Критерии для разбиений

Меры гетерогенности:

Меры изолированности

Методы кластеризации

Иерархические аггломеративные

Single Linkage

Complete Linkage

Average Linkage

Centroid Linkage

Median

Ward

Иерархические дивизивные

Diana

Density-based

Partitioning

K-means

Mona

Кластеризация с использованием графов

Kohonen network

SOM

SOTA

Biclustering

Fuzzy clustering

Model-based clustering

Общие вопросы

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

Лучше выбирать побольше объектов из малочисленных классов.

Процедура кластеризации должна быть инвариантна при аффинных преобразованиях данных (т.е. масштабирование и поворот, y> Cy + a)

число разбиений t объектов на k классов (при любых возможных объемах классов) – число Стирлинга второго рода

(делим на k! т.к. порядок классов не важен)

Clustering algorithm should be able to identify genes that are not relevant for any clusters and leave them as they are.

Расстояния

distance measure если :

  • dij > 0 для i<>j
  • dij = 0 для i=j
  • dij = dji

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

В pattern recognition лучше применять именно метрики (??)

Расстояния между бинарными переменными

Zhang, Srihari

Jaccard:
Недостаток Jaccarda: возвращает большое расстояние если первый вектор >> второго, даже если второй полностью содержится в первом.

=> use Kulczynski

Но: Kulczynski - не метрика (т.е. иногда неравенство треугольника может нарушаться)

Расстояния между ordinal переменными (теми, которые могут быть упорядочены)

обычно определяется как abs(l-m) ^r, где l<m - состояния, r обычно =1.

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

Spearman rank correlation:

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

Kendall rank correlation

ties – объекты имеют одинаковые ранги по обеим переменным, и следовательно мы не можем различить эти два объекта.

Расстояния между вещественными переменными

Расстояние Минковского, city-block, Евклид.

НО! При использовании Евклида как расстояния в многомерном варианте все переменные желательно должны быть одной scale, поэтому ВСЕГДА лучше делать

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

Часто в качестве веса можно использовать , где R- разброс, p – число переменных.

Коэффициент корреляции косинус угла между векторами (учитывая смещение относительно начала координат)

возможно, имеет смысл строить корреляцию между переменными и рисовать такие графики:

расстояние Махаланобиса:

, где Scovariance matrix.

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

Вообще лучше не использовать расстояние Махаланобиса если есть структура (т.е. кластеры) – тем самым в S будут внесены искажения. Вот внутри каждого кластера – пожалуйста.

Расстояния между смешанными переменными

, где wijk =1 или 0 в зависимости от того, возможно ли сравнение между переменными

Расстояния между группами объектов

Две популяции имеющие распределения fi и fj по сравниваемой переменной nu.

для набора категориальных(categorical) переменных (не могут быть упорядочены) вводится новая переменная как комбинации всех возможных состояний. Вероятности этих комбинаций состояний (новой переменной) оцениваются по выборке.

Dissimilarity matrices

Матрица расстояний – метрика, если для всех троек расстояний выполняется неравенство треугольника. Бывают асимметричные матрицы расстояний

Любая матрица расстояний может быть трансформирована в евклидову (если нет пропущенных/imputed значений)



daisy -Compared to dist whose input must be numeric variables, the main feature of daisy is its ability to handle other variable types as well (e.g. nominal, ordinal, (a)symmetric binary) even when different types occur in the same data set.

The handling of nominal, ordinal, and (a)symmetric binary data is achieved by using the general dissimilarity coefficient of Gower (1971). If x contains any columns of these data-types, both arguments metric and stand will be ignored and Gower's coefficient will be used as the metric

library ade4:

is.euclidпроверяет dist matrix по Gower theorem

cailliez - computes the smallest positive constant that makes Euclidean a distance matrix and applies it.

Пропущенные значения

Little&Rubin

Иногда количественную переменную лучше использовать как порядковую

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

Для вещественных переменных – важнее абсолютное значение или относительная величина (тогда лучше использовать коэффициент корреляции)

Критерии для разбиений

  • гетерогенность
  • изоляция от остальных объектов

Меры гетерогенности:

  • сумма квадратов

можно разбить на внутриклассовую(первый член, мера гетерогенности) и межклассовую(второй член, мера изолированности) компоненты

=> минимизация гетерогенности в этом случае эквивалентна максимизации изолированности.

Есть тенденция к образованию сферических кластеров

  • L1-мера , m – медиана

  • диаметр

  • сумма нижнетреугольной матрицы расстояний

Меры изолированности

  • split - min расстояние между объектом из класса и любым объектом извне

  • cut – сумма расстояний между объектами внутри класса и объектами вне класса

Методы кластеризации

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

Иерархические аггломеративные

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

при формировании кластеров пространство расстояний может изменяться:

  • space-contracting – если вновь образованные кластеры являются более близкими к отдельным наблюдениям. Поэтому новый объект с большей вероятностью будет приписан этому кластеру, чем будет формировать новый кластер. Это называется chaining.
  • space-dilating – новые объекты скорее будут сами формировать кластер, чем сливаться с существующими
  • space-conserving

Single Linkage

страдает от chaining (т.е. space-contracting)

лучше выявляет кластеры изогнутой структуры (а не эллиптические) и относительно robust.

Complete Linkage

очень space-dilating

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

Average Linkage

тенденция к слиянию кластеров с приблизительно равными и малыми дисперсиями

largely space-conserving. относительно robust.

Centroid Linkage

расстояние – евклидово между центрами тяжести двух кластеров.

после объединения центроид пересчитывается:

Не является monotonic! (т.е. могут быть объединены кластеры с меньшим расстоянием. чем это было на предыдущем шаге. Это же касается и median(их не рекомендуют применять). Все остальные методы – monotonic (ultrametric)

Median

если один кластер имеет много больше объектов чем другой, то при пересчете по centroid получит преимущество.

median(NB: это не медиана из статистики, а медиана из геометрии, т.к. новый центр лежит на середине прямой, соединяющей центры кластеров):

Не является monotonic!

Ward

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

Но: минимизация уменьшения в SSE эквивалента уменьшению between-cluster distance.

Очень похоже на centroid, только здесь еще учитываются размеры кластеров:

Поэтому ward будет с большей вероятностью чем centroid объединять маленькие кластеры одинакового размера (т.е. сферические). Space-contracting. Относительно robust.

Иерархические дивизивные

Дивизивные методы должны быть лучше, т.к. обычно кластеров мало, и структура будет видна сразу, а не в конце процесса (как с аггломеративными методами).

бывают

  • monothetic (делят на группы по одной переменной,

если бинарной, то все понятно. Пример – MONA. Эта переменная выбирается таковой, чтобы максимизировать хи-квадрат или информационную статистику. Если quantative переменная, то нужно мах для всех возможных n1 и n2

  • polythetic пример - DIANA

Diana

На каждом шаге делится кластер С с наибольшим диаметром. Кластер С состоит из кластеров A и B. Первоначально B пустой. Объекты x последовательно переносятся из A в B пока выполняется: >0

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

diana() in package cluster. Можно передавать произвольную матрицу расстояний

Density-based

могут создавать кластеры произвольной формы

Partitioning

K-means

также известен как ISODATA, Generalized Lloyd Algorithm

вариант – PAM (Partitioning around medoids) - то же самое, но используются medoids вмето средних

Imposes structure on the data, being sensitive to the clusters dimensions, eventually decomposing the data into comparable sized hyper-spherically shaped clusters.

Лучше задавать k побольше - пусть будет много фрагментов которые объединим, чем сформируются ложные кластеры

Mona

для бинарных данных. Дивизивный.

The basic idea is to select one of the variables and to divide the set of objects into those objects with and those without the corresponding attribute. In each of the two subsets, one of the remaining variables is selected and used in the same way to divide this subset into two smaller

groups. (Note that it is not necessary to use the same second variable in both subsets.) The process is continued until either the subset contains a single object (it is then called a singleton) or until the remaining variables cannot separate the subset any further. This last situation only occurs when each variable remains constant for all objects of this subset.

Как выбирать переменную по которой будет разделение

abs(a*d - b*c)

Кластеризация с использованием графов

  1. искать максимальные клики
  2. строить MST (minimal spanning tree, built on minimum cut) и удалять ребра с наибольшей длинной для получения кластеров

MCODE???

Kohonen network

SOM

есть n объектов и есть сетка с координатами ячеек w(1,j),w(2,j),...,w(i,j),...,w(n,j)

hlearning coefficient

выбрать очередную точку xi

найти ближайшую ячейку на сетке с координатами w(i,j)

для каждой ячейки соседней с выбранной:

пересчитать ее координаты w(i,k) = w(i,k) + h *( xiw(i,j))

Похоже на k-means : winner-takes-all approach to updating centroids.

Произвол – структура сетки (число ячеек и геометрия), размер neighborhood

лучше не пытаться проводить аналогию с нейронными сетями

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

som() function in package kohonen.

SOTA

The Self-Organizing Tree Algorithm – посмотреть!

Biclustering

Fuzzy clustering

ex: fanny () in the cluster package

Model-based clustering

function Mclust() in package mclust

Комментарии   

 
0 #1 Anatoly.Saveliev@ksu.ru 22.02.2010 12:09
По поводу SOM. Это на самом деле гибрид ординации и кластеризации.

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

При ординации (например NMDS, PCA, ...) мы знаем как соотносятся (в терминах выбранной метрики) объекты, но не знаем, куда поместить на ординационной плоскости новые.

Можно считать, что SOM есть в некотором смысле ординация классов, полученных к-средними (есть метод Generative Topographic Mapping с похожим результатом, который примерно так и работает, являясь расширение fuzzy c-means), однако оба метода являются моделями многомерной плотности данных, и не стремятся выделить "плотные скопления" (в них, наоборот, попадет много классов, в отличие от к-средних).

Таким образом, SOM позволяет анализировать наборы данных, в которых нет четких (разделимых) классов, но есть непрерывные переходы (градиенты), их много и они нелинейные.

Это метод разведочного анализа данных и построения непараметрическ их регрессий.

В связи с этим рекомендованный размер 3х3 является совершенно бессмысленным, поскольку ничего выделить не удастся. Размер порядка 15х15 - "рабочий", а для сходимости (устойчивости) нужно правильно задавать параметры, или пользоваться GTM.

Смысл - не получить кластеры, а выделить градиенты.

Достоинство - возможность анализировать огромные наборы данных (миллионы записей) большой размерности (тысячи).

P.S. Алгоритм у Вас прописан неверно, работать не будет.

P.P.S. На сайте www.scanex.ru в разделе програмного обеспечения есть демо-версия программы ImageProcessor с документацией, там для модуля NeRIS расписаны и формулы, и идеология.
Цитировать
 

Добавить комментарий


Защитный код
Обновить