Обновлено 10.09.2012 Автор: Administrator
Это мои рабочие записи по методам кластеризации. К сожалению, у меня пока нет времени привести конспект в пристойный вид, но вдруг это кому-то окажется полезным. С удовольствием отвечу на любые вопросы в комментариях или на форуме . Часть 1
Расстояния между бинарными переменными
Расстояния между ordinal переменными (теми, которые могут быть упорядочены)
Расстояния между вещественными переменными
Расстояния между смешанными переменными
Кластеризация с использованием графов
Важно понимать: нужно ли классифицировать конкретный набор объектов, или этот набор пришел из генеральной совокупности, свойства которой нас на самом деле интересуют.
Лучше выбирать побольше объектов из малочисленных классов.
Процедура кластеризации должна быть инвариантна при аффинных преобразованиях данных (т.е. масштабирование и поворот, 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 если :
если еще удовлетворяется неравенство треугольника, то это метрика.
В pattern recognition лучше применять именно метрики (??)
Zhang, Srihari
Jaccard:
Недостаток Jaccard’a: возвращает большое расстояние если первый вектор >> второго, даже если второй полностью содержится в первом.
=> use Kulczynski
Но: Kulczynski - не метрика (т.е. иногда неравенство треугольника может нарушаться)
обычно определяется как abs(l-m) ^r, где l<m - состояния, r обычно =1.
Если ординальная(порядковая) переменная получена путем разбиения количественной переменной, то учитывая распределение этой переменной можно получать более осмысленные меры расстояний.
Spearman rank correlation:
осторожно применять если шкала количественная, потому что при этом происходит ее понижение до порядковой, т.е. учитывается только ранг.
Kendall rank correlation
ties – объекты имеют одинаковые ранги по обеим переменным, и следовательно мы не можем различить эти два объекта.
Расстояние Минковского, city-block, Евклид.
НО! При использовании Евклида как расстояния в многомерном варианте все переменные желательно должны быть одной scale, поэтому ВСЕГДА лучше делать
C другой стороны, при вычислении дисперсии используются все данные (в том чиcле принадлежащие разным кластерам), поэтому она чрезмерно завышается, и разделение по масштабированным переменным м.б. хуже чем по исходным. Так что это трудный вопрос.
Часто в качестве веса можно использовать , где R- разброс, p – число переменных.
Коэффициент корреляции косинус угла между векторами (учитывая смещение относительно начала координат)
возможно, имеет смысл строить корреляцию между переменными и рисовать такие графики:
, где S – covariance matrix.
это расстояние учитывает корреляции между переменными
Вообще лучше не использовать расстояние Махаланобиса если есть структура (т.е. кластеры) – тем самым в S будут внесены искажения. Вот внутри каждого кластера – пожалуйста.
, где wijk =1 или 0 в зависимости от того, возможно ли сравнение между переменными
Расстояния между группами объектов
Две популяции имеющие распределения fi и fj по сравниваемой переменной nu.
для набора категориальных(categorical) переменных (не могут быть упорядочены) вводится новая переменная как комбинации всех возможных состояний. Вероятности этих комбинаций состояний (новой переменной) оцениваются по выборке.
Матрица расстояний – метрика, если для всех троек расстояний выполняется неравенство треугольника. Бывают асимметричные матрицы расстояний
Любая матрица расстояний может быть трансформирована в евклидову (если нет пропущенных/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, должно ли это увеличивать сходство между объектами.
Для вещественных переменных – важнее абсолютное значение или относительная величина (тогда лучше использовать коэффициент корреляции)
можно разбить на внутриклассовую(первый член, мера гетерогенности) и межклассовую(второй член, мера изолированности) компоненты
=> минимизация гетерогенности в этом случае эквивалентна максимизации изолированности.
Есть тенденция к образованию сферических кластеров
все иерархические нехороши тем, что после того как объект приписан к кластеру, он уже не может быть изменен.
Получение иерархии – это преобразование расстояний (которые обычно не удовлетворяют условиям ультраметрики) между объектами в ультраметрику.
при формировании кластеров пространство расстояний может изменяться:
страдает от chaining (т.е. space-contracting)
лучше выявляет кластеры изогнутой структуры (а не эллиптические) и относительно robust.
очень space-dilating
чувствителен к выбросам
тенденция к слиянию кластеров с приблизительно равными и малыми дисперсиями
largely space-conserving. относительно robust.
расстояние – евклидово между центрами тяжести двух кластеров.
после объединения центроид пересчитывается:
Не является monotonic! (т.е. могут быть объединены кластеры с меньшим расстоянием. чем это было на предыдущем шаге. Это же касается и median(их не рекомендуют применять). Все остальные методы – monotonic (ultrametric)
если один кластер имеет много больше объектов чем другой, то при пересчете по centroid получит преимущество.
median(NB: это не медиана из статистики, а медиана из геометрии, т.к. новый центр лежит на середине прямой, соединяющей центры кластеров):
Не является monotonic!
минимизирует увеличение в сумме квадратов после объединения кластеров
Но: минимизация уменьшения в SSE эквивалента уменьшению between-cluster distance.
Очень похоже на centroid, только здесь еще учитываются размеры кластеров:
Поэтому ward будет с большей вероятностью чем centroid объединять маленькие кластеры одинакового размера (т.е. сферические). Space-contracting. Относительно robust.
Дивизивные методы должны быть лучше, т.к. обычно кластеров мало, и структура будет видна сразу, а не в конце процесса (как с аггломеративными методами).
бывают
если бинарной, то все понятно. Пример – MONA. Эта переменная выбирается таковой, чтобы максимизировать хи-квадрат или информационную статистику. Если quantative переменная, то нужно мах для всех возможных n1 и n2
На каждом шаге делится кластер С с наибольшим диаметром. Кластер С состоит из кластеров A и B. Первоначально B пустой. Объекты x последовательно переносятся из A в B пока выполняется: >0
Чувствителен к выбросам, т.к. использует понятие диаметра!
diana() in package cluster. Можно передавать произвольную матрицу расстояний
могут создавать кластеры произвольной формы
также известен как 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 побольше - пусть будет много фрагментов которые объединим, чем сформируются ложные кластеры
для бинарных данных. Дивизивный.
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)
MCODE???
есть n объектов и есть сетка с координатами ячеек w(1,j),w(2,j),...,w(i,j),...,w(n,j)
h – learning coefficient
выбрать очередную точку xi
найти ближайшую ячейку на сетке с координатами w(i,j)
для каждой ячейки соседней с выбранной:
пересчитать ее координаты w(i,k) = w(i,k) + h *( xi – w(i,j))
Похоже на k-means : winner-takes-all approach to updating centroids.
Произвол – структура сетки (число ячеек и геометрия), размер neighborhood
лучше не пытаться проводить аналогию с нейронными сетями
большие сетки могут давать другие результаты при изменении параметров. Обычно стабильны размером 3х3.
som() function in package kohonen.
The Self-Organizing Tree Algorithm – посмотреть!
ex: fanny () in the cluster package
function Mclust() in package mclust
< Предыдущая | Следующая > |
---|
Комментарии
При кластеризации мы знаем, что (какие сущности, "отличные от других") выделены, но не знаем, как они соотносятся друг с другом (по "похожести"; отчасти это возможно лишь для иерархических кластеризаций).
При ординации (например 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 расписаны и формулы, и идеология.