Ієрархічна кластеризація

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Ієрархічна кластеризація (також «графові алгоритми кластеризації») — сукупність алгоритмів впорядкування даних, візуалізація яких забезпечується за допомогою графів.

Алгоритми сортування даних зазначеного типу виходять з того, що якась безліч об'єктів характеризується певним ступенем connectivity. Передбачається наявність вкладених груп (кластерів різного порядку). Алгоритми в свою чергу поділяються на агломеративные (об'єднувальні) і дивизивные (поділ). По кількості ознак іноді виділяють монотетические і политетические методи класифікації. Як і більшість візуальних способів подання залежностей графи швидко втрачають наочність при збільшенні числа об'єктів. Існує ряд спеціалізованих програм для побудови графів.

Дендрограма[ред.ред. код]

Дендрограмма

Під дендрограмою зазвичай розуміється дерево, тобто граф без циклів побудований за матриці заходів близькості. Дендрограма дозволяє зобразити взаємні зв'язки між об'єктами з заданого переліку[1]. Для створення дендрограми потрібно матриця подібності (відмінності), яка визначає рівень подібності між парами об'єктів. Частіше використовуються агломеративні методи.

Далі необхідно вибрати метод побудови дендрограми, який визначає метод візуалізації матриці подібності (відмінності) після об'єднання (або поділу) чергових двох об'єктів в кластер.

У роботах по кластерному аналізу описаний досить значний ряд способів побудови (англ. sorting strategies) дендрограмм[2]:

  1. Метод одиночної зв'язку (англ. single linkage). Також відомий як «метод найближчого сусіда».
  2. Метод повної зв'язку (англ. complete linkage). Також відомий як «метод далекого сусіда».
  3. Метод середньої зв'язку (англ. pair-group method using arithmetic averages).
  1. Центроидный метод (англ. pair-group method using the centroid average).
  • Незважений.
  • Зважений (медианый).
  1. Метод Уорда (англ. Ward's method).

Для перших трьох методів існує загальна формула, запропонована А. Н. Колмогоровым для заходів подібності[3]:

 K_\eta([i,j],k) =  \left [ \frac{(n_iK(i,k)^\eta + (n_jK(j,k)^\eta)}{n_i + n_j} \right ]^\frac{1}{\eta}, - \mathcal {1} \leqslant \eta \leqslant + \mathcal {1}

де [i, j] — група з двох об'єктів (кластерів) і j; k — об'єкт (кластер), з яким шукається схожість зазначеної групи; n_i — кількість елементів у кластері ; n_j — кількість елементів у кластері j. Для відстаней є аналогічна формула Ланса — Вільямса[4].

Центроидный метод використовує для перерахунку матриці відстаней[5]. Як відстані між двома кластерами у цьому методі береться відстань між центрами тяжіння.

У методі Уорда як відстані між кластерами береться приріст суми квадратів відстаней об'єктів до центрів кластерів, що отримується в результаті їх об'єднання[6]. На відміну від інших методів кластерного аналізу для оцінки відстаней між кластерами, тут використовуються методи дисперсійного аналізу. На кожному кроці алгоритму об'єднуються такі два кластери, які призводять до мінімального збільшення цільової функції, тобто внутрішньогрупової суми квадратів. Цей метод спрямований на об'єднання близько розташованих кластерів.

Кореляційні плеяди[ред.ред. код]

Широко застосовуються в геоботаніки флористики. Їх часто називають «'кореляційними плеядами»'[7][8][9][10].

Окремим випадком є метод, відомий як метод побудови «оптимальних дерев (дендритів)», який був запропонований математиком львівської школи Гуго Штейнгаузом[11], згодом метод був розвинений математиками вроцлавської таксономічної школи[12]. Дендрити також не повинні утворювати циклів. Можна частково використовувати спрямовані дуги графів при використанні додатково заходів включення (несиметричних заходів подібності).

Діаграма Чекановского[ред.ред. код]

Метод «диагонализации» матриці відмінності і графічне зображення кластерів уздовж головної діагоналі матриці відмінності (діаграма Чекановского) вперше запропонований Яном Чекановським у 1909 році[13]. Наведемо опис методики:

Суть цього методу полягає в тому, що всю амплітуду отриманих величин подібності розбивають на ряд класів, а потім в матриці величин подібності замінюють ці величини штрихуванням, різної для кожного класу, причому зазвичай для більш високих класів подібності застосовують більш темну штрихування. Потім, змінюючи порядок описів в таблиці, домагаються того, щоб більше схожі описания виявилися поруч[14]

Наведемо гіпотетичний приклад отримання такої діаграми. Основою методу є побудова матриці транзитивного замикання[15].

Приклад розрахунку діаграми Чекановского

Для побудови матриці транзитивного замикання візьмемо просту матрицю подібності і помножимо її на саму себе:

 K^{(2)}(i,j) = max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q,j))),

де K(i, j) — елемент, що стоїть на перетині -ой рядка j-го стовпця в новій (другий) матриці, отриманої після першої ітерації; - загальна кількість рядків (стовпчиків) матриці подібності. Дану процедуру необхідно продовжувати поки матриця не стане идемпотентной (тобто самоподобной):  K^{(n)}(i,j) = K^{(n-1)}(i,j) , де n — кількість ітерацій.

Далі перетворюємо матрицю таким чином, щоб близькі числові значення знаходилися поряд. Якщо кожному числовим значенням присвоїти будь-який колір або відтінок кольору (як у нашому випадку), то отримаємо класичну діаграму Чекановского. Традиційно більш темний колір відповідає більшої схожості, а більш світлий — меншого. В цьому вона схожа з теплокартой матриці відстаней.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. «Жамбю М.» Ієрархічний кластер-аналіз та відповідності. — М.: Финансы и статистика, 1988. — 345 с.
  2. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  3. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  4. «Lance G.N., Willams W.T.» A general theory classification of sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373–380.
  5. «Sneath P.H.A., Sokal R.R.» Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
  6. «Ward J.H.» Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
  7. «von Terentjev P.V.» Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. № 23(1-2). P. 23-51.
  8. «Терентьєв П. У.» Метод кореляційних плеяд // Вісн. ЛДУ. № 9. 1959. С. 35-43.
  9. «Терентьєв П. У.» Подальший розвиток методу кореляційних плеяд // Застосування математичних методів в біології. Т. 1. Л.: 1960. С. 42-58.
  10. «Выханду Л. К.» Про дослідженні многопризнаковых біологічних систем // Застосування математичних методів в біології. Л.: вып. 3. 1964. С. 19-22.
  11. «Штейнгауз Р.» Математичний калейдоскоп. — М.: Наука, 1981. — 160 с.
  12. «Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S.» Taksonomia Wroclawska // Przegl. antropol. 1951. T. 17. S. 193–211.
  13. «Czekanowski J.» Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
  14. Василевич В. И. Статистические методы в геоботанике. — Л.: Наука, 1969. — 232 с.
  15. «Tamura S., Hiquchi S., Tanaka K.» Pattern classification based on fuzzy relation // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.