Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Представлення результатів



Результатом кластерного аналізу є набір кластерів, що містять елементи вихідної множини. Кластерна модель повинна описувати як самі кластери, так і належність кожного об'єкта до одного з них.

Для невеликого числа об'єктів, що характеризуються двома змінними, результати кластерного аналізу зображують графічно. Елементи представляються точками, кластери розділяються прямими, які описуються лінійними функціями. Якщо кластери не можна розділити прямими, то малюються ламані лінії, які описуються нелінійними функціями.

Ряд алгоритмів кластеризації будують ієрархічні структури кластерів. У таких структурах найвищий рівень відповідає всій множини об'єктів, тобто одному-єдиному кластеру. На наступному рівні він ділиться на декілька підкластерів. Кожен з них ділиться ще на декілька і так далі. Побудова такої ієрархії може відбуватися до тих пір, поки кластери не відповідатимуть окремим об'єктам. Такі діаграми називаються дендрограмами (dendrograms).

Базові алгоритми кластеризації

Класифікація алгоритмів

При виконанні кластеризації важливо, скільки у результаті має бути побудовано кластерів. Передбачається, що число кластерів являється параметром, що часто істотно ускладнює вид алгоритму. Якщо число кластерів не відоме, то це суттєво впливає на якість результату.

Проблема вибору числа кластерів нетривіальна. Але про які припущеннях може йти мова, коли на початку дослідження, про дані практично ні чого невідомо? Тому алгоритми кластеризації, зазвичай, будуються як деякий спосіб перебору числа кластерів, і визначення його оптимального значення в процесі перебору.

Число методів розбиття множини на кластери досить велике. Всі їх можна підрозділити на ієрархічні та неієрархічні.

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

З іншого боку, коли проекти характеризуються великим числом ознак (параметрів), то набуває важливого значення задача угруповання ознак. Вихідна інформація міститься в квадратній матриці ознак, зокрема в кореляційній матриці.

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

Ієрархічні алгоритми пов'язані з побудовою дендрограм і діляться:

· на агломеративні,

· на подільні, в яких число кластерів зростає, починаючи з одного, в результаті чого утворюється послідовність розщеплюють груп (побудова кластерів зверху вниз).

Плоска кластеризація ефективна і проста, але, має багато недоліків. Плоскі алгоритми кластеризації створюють просту неструктуровану множину кластерів, використовуючи кількість кластерів як вхідний параметр. Крім того, ці алгоритми є не детермінованими. Ієрархічна кластеризація (hierarchical clustering) створює ієрархію, тобто структуровану множину, яка є більш інформативною, ніж неструктурована множина кластерів, що створюється в ході плоскої кластеризації. Для ієрархічної кластеризації не потрібно заздалегідь задавати кількість кластерів, і більшість ієрархічних алгоритмів, використовуваних для інформаційного пошуку є детермінованими. Проте за ці переваги алгоритмів ієрархічної кластеризації доводиться розплачуватися нижчою продуктивністю. Складність найбільш поширених алгоритмів ієрархічної кластеризації є як мінімум квадратичною по відношенню до кількості документів, тоді як алгоритм k-середніх і ЕМ-алгоритм мають лінійну складність рис 1

Рис. 1. Показник якості як зовнішній критерій кластеризації. Основний клас і кількість елементів основного класу в трьох кластерах такі: х, 5 (кластер 1), о, 4 (кластер 2) та ◊, 3 (кластер 3). Показник якості дорівнює (1/17) * (5 + 4 + 3) ≈ 0,71

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

Алгоритми ієрархічної кластеризації є або низхідними, або висхідними. Висхідні алгоритми на початковому етапі розглядають кожен документ як окремий кластер, а потім послідовно об'єднують (або агломерують) пари кластерів, поки вони не зіллються в один кластер, що містить всі документи. З цієї причини висхідна ієрархічна кластеризація називається агломеративною ієрархічною кластеризацією (Hierarchical Agglomerative Clustering — НАС). Низхідна ієрархічна кластеризація ґрунтується на розділенні кластера. В ході низхідної кластеризації кластери рекурсивно розділяються до тих пір, поки не будуть розщеплені на окремі документи. Висхідна ієрархічна кластеризація використовується для інформаційного пошуку частіше, ніж низхідна.

Агломеративна ієрархічна кластеризація зазвичай зображується за допомогою дендрограмм (dendrogram), показаних на рис. 2. Кожне об'єднання представлене горизонтальною лінією. Ордината цієї горизонтальної лінії є мірою схожості між двома об'єднуваними кластерами (окремі документи розглядаються як одноелементні кластери). Ця схожість називається комбінаційною мірою схожості (combination similarity) об'єднаного кластера. Наприклад, комбінаційна міра схожості кластера, що складається з документів Lloyds CEO questioned і Lloyd's chief / U.S. grilling на рис. 2, приблизно рівна 0,56. Комбінаційна міра схожості одноелементного кластера трактується як схожість документа з самим собою, або самоподібність (при використанні косинусної міри схожості вона дорівнює одиниці).

Переходячи по дендрограммі від низу до верху, можна прослідкувати процес кластеризації. Наприклад, як показано на рис. 2, два документи із заголовками War hero Colin Powell були об'єднані першими, а останнє об'єднання сталося, коли до кластера, що складається з 29 документів, був доданий документ Ag trade reform.

Основне припущення агломеративної ієрархічної кластеризації полягає в тому, що операція об'єднання є монотонною. Це означає, що якщо, s1, s2, …, sk-1 — комбінаційні заходи схожості послідовних об'єднань в агломеративній ієрархічній кластеризації, то виконуються нерівності s1 ≥ s2 ≥ … ≥ sk-1. Немонотонна ієрархічна кластеризація містить хоч би одну інверсію (inversion) si ≤ si+1, яка перечить основному припущенню, що на кожному етапі вибирається найкраще об'єднання.

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

Рис. 2. Дендрограмма кластеризації з одиночним зв'язком 30 документів з колекції Reuters-RCVI. Показані два можливих перетину дендрограмми: на рівні 0.4 - на 24 кластеру і на рівні 0,1 - на 12 кластерів

• Відсікання на заздалегідь вказаному рівні схожості. Наприклад, щоб мінімальна комбінаційна схожість кластерів була рівною 0,4, слід провести перетин дендрограмми на цьому рівні. На рис. 2 показано, що перетин дендрограмми на рівні 0,4 породжує 24 кластери (групуються лише документи з високою схожістю), а перетин дендрограмми на рівні 0,1 породжує 12 кластерів (один крупний кластер фінансових новин і одинадцять дрібніших кластерів).

• Перетин дендрограмми в точці максимальної різниці між двома послідовними комбінаційними заходами схожості. Такі перепади є ознакою "природної" кластеризації. Додавання ще одного кластера в цьому випадку значно погіршує якість кластеризації, тому бажано робити відсікання до того, як це станеться. Дана стратегія нагадує пошук точки перегину на графіці К - середніх.

• Вживання формули (16.11) К = argk-1min[RSS (К') +λK' ], де К' — рівень відсікання ієрархії, що породжує К' кластерів, RSS — залишкова сума квадратів, а λ — штраф за кожен додатковий кластер. Замість показника RSS можна використовувати інший показник спотворення.

• Як і в плоскій кластеризації, в ієрархічній кластеризації можна заздалегідь задавати кількість кластерів K і вибирати точку відсікання так, щоб у результаті отримати K кластерів.

Спочатку розглянемо простий “наївний” алгоритм агломеративної ієрархічної кластеризації. У ньому спочатку обчислюється матриця схожості з розмірності N x N, а потім виконуються N - 1 етапів, на яких об'єднуються найбільш схожі один на одного у даний момент кластери. На кожній ітерації два найбільш схожих кластера об'єднуються, а рядки і стовпці, відповідні об'єднаному кластеру i в матриці, обчислюються заново. Розбиття зберігається у вигляді списку об'єднань А. У масиві I зберігається список кластерів, доступних для об'єднання. Функція Sim(i, m, j) обчислює схожість кластера j з об'єднанням кластерів i та m. У деяких алгоритмах агломеративної ієрархічної кластеризації функція Sim(i, m, j) — це просто функція, залежна від C[j][i] і C[j][m], наприклад максимум серед цих двох значень в методі одиночного зв'язку.

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

 

Рис. 3, а. Одиночний зв'язок: максимальна подібність.

Рис. 3, б. Повний зв'язок: мінімальна подібність.

 

Рис. 3, в. Центроїд: середня перехресна подібність.

 

Рис. 3, г. Групове усереднення: усереднення всі показників подібності.


Кластеризація методами одиночного і повного зв'язку

В кластеризації методом одиночного зв'язку (single-link clustering, single-linkage clustering) схожістю двох кластерів є схожість між їх найбільш схожими елементами (див. рис. 3, а). Критерій об'єднання в методі одиночного зв'язку носить локальний характер. У цьому алгоритмі увага приділяється виключно області, в якій два кластери найбільш близькі один до одного. Інші, більш віддалені, частини кластера і його структура не враховується

У кластеризації методом повного зв'язку (complete-link clustering, complete-linkage clustering) схожістю двох кластерів є схожість між їх найбільш несхожими елементами (див. рис. 3, б). Це еквівалентно вибору пари кластерів, об'єднання яких має найменший діаметр. Критерій об'єднання в методі повного зв'язку носить нелокальний характер: рішення про об'єднання кластерів може впливати вся структура кластеризації. Це приводить до переважання компактних кластерів з маленькими діаметрами над довгими розтягнутими кластерами, але одночасно підвищує чутливість до викидів. Окремий документ, що знаходиться далеко від центру, може різко збільшити діаметр можливого об'єднання і повністю змінити остаточне розбиття.

 

Рис. 4. Кластеризація восьми документів методами одиночної зв'язку (ліворуч) і повною зв'язку (праворуч). Еліпси відповідають послідовним етапам кластеризації. Зліва: схожість на основі одиночної зв'язку між двома двоточковими кластерами вгорі дорівнює показнику подібності між документами d2 і d3 (суцільна лінія), яке перевищує схожість на основі одиночної зв'язку між двоточковими кластерами зліва (пунктирна лінія). Праворуч: схожість на основі повної зв'язку двох двоточкових кластерів вгорі дорівнює показнику подібності між документами d1 і d4 (пунктирна лінія), яка менше, ніж подібність на основі повної зв'язки між двома лівими двоточковими кластерами (суцільна лінія)

На рис. 4 продемонстрований процес кластеризації восьми документів методами одиночного і повного зв'язку. На перших етапах обидва методи формують по чотири ідентичні кластери, кожен з двох документів. Потім алгоритм методу одиночного зв'язку об'єднує верхні дві пари (а після — і нижні). Оскільки як міра схожості в даному алгоритмі використовується максимальна схожість між елементами, ці кластери вважаються найближчими. Алгоритм методу повного зв'язку об'єднує дві ліві пари (а потім і дві праві), оскільки ці пари ближче один до одного відповідно до визначення схожості кластерів як мінімальної схожості їх елементів. Приклад кластеризації множини документів за допомогою методу одиночного зв'язку наведений на рис. 2, а приклад кластеризації за допомогою методу повного зв'язку та сама множина — на рис. 5. Провівши відсікання останнього об'єднання на рис. 6, ми отримаємо два кластери однакового розміру (документи 1-16 від NYSE closing averages до Lloyds chief / U.S. grilling і документи 17-30 від Ohio Blue Cross до Clinton signs law). На рис. 2 не існує такого перетину дендрограми, яке приводило до розбиття на кластери приблизно однакового розміру.

Як кластеризацію методом одиночного зв'язку, так і кластеризацію методом повного зв'язку можна інтерпретувати за допомогою теорії графів. Хай sk комбінаційна міра схожості між двома кластерами, об'єднаними на етапі k, а G(sk) — граф, що зв'язує всі крапки, схожість між якими не менша, ніж sk. Тоді кластери після етапу k в процесі кластеризації методом одиночного зв'язку є зв'язними компоненти графа G(sk), а кластери після етапу k в процесі кластеризації методом повного зв'язку є максимальними кліками (cliques) графа G(sk). Компонент зв’язності (connected component) — це максимальна множина вершин, сполучених між собою так, що для кожної пари існує ребро, що сполучає їх. Клік (clique) — це множина крапок, які створюють повний граф (тобто будь-які дві суміжні крапки).

Рис. 5. Дендрограма кластеризації за методом повної зв'язку. Тут показані ті ж 30 документів, які були кластеризовані за допомогою методу одиночної зв'язку на рис. 2

Ці інтерпретації пояснюють назви методів: одиночного зв'язку і повного зв'язку. Кластери, отримані методом одиночного зв'язку на етапі k, — це максимальна множина крапок, між якими існує хоч би один зв'язок по схожості: s ≥ sk. Кластери, отримані методом повного зв'язку на етапі k, — це максимальна множина крапок, в кожної з яких є зв'язок у міру схожості зі всіма іншими: s ≥ sk.

Алгоритми кластеризації методами одиночного і повного зв'язку зводять завдання оцінки якості кластера до оцінки міри схожості між двома документами: двома найбільш схожими документами в алгоритмі методу одиночного зв'язку і двома найбільш несхожими документами в алгоритмі методу повного зв'язку. Оцінки схожості між двома документами не відображають властивості розподілу документів в кластері. З цієї причини не дивно, що обидва алгоритми часто породжують небажані кластери.

Кластеризація методом одиночного зв'язку може створити розкидані кластери, як показано на рис. 6. Оскільки критерій об'єднання в цьому алгоритмі носить строго локальний характер, ланцюжок пар може розтягнутися на велику відстань без врахування форми виникаючого кластера. Цей ефект називається зчепленням (chaining).

Ефект зчеплення видно і на рис. 2. Останні одинадцять об'єднань в алгоритмі кластеризації методом одиночного зв'язку (що знаходяться над лінією в = 0,1), які добавляють одиничний документ, або пару документів, утворюють ланцюжок. Кластеризація методом повного зв'язку, продемонстрована на рис. 6, дозволяє уникнути цього ефекту. Коли дендрограма розтинається на етапі останнього об'єднання, документи розділяються на дві групи приблизно однакового об'єму. Загалом, це корисніша організація даних ніж зчеплені кластери.

Проте кластеризація методом повного зв'язку має інший недолік. Вона надає велику вагу викидам, тобто крапкам, що не вписуються в загальну структуру кластера. У прикладі, показаному на рис. 7, чотири документи, d2, d3, d4, d5 не попали в один кластер із-за викиду d1. Кластеризація методом повного зв'язку в даному випадку не здатна створити найбільш природну структуру кластерів.

 

Рис. 6. Зчеплення, що виникає при кластеризації методом одиночної зв'язку. Локальний критерій у кластеризації методом одиночної зв'язку може породити не бажано витягнуті кластери

Рис. 7. Викиди в кластеризації методом повної зв'язку. П'ять документів мають координати х, рівні 1 +2 е 4, 5 +2 е, 6 і 7е. Кластеризація методом повної зв'язку створює два кластери, показаних як еліпси. Найбільш правильним з інтуїтивною точки зору було б розбиття {{d1}, {d2, d3, d4, d5}}, але при кластеризації методом повної зв'язку викид d1 розбиває майстер {d2, d3, d4, d5} так; як показано на малюнку

 

Часова складність

Складність “наївного” алгоритму агломеративної ієрархічної кластеризації, показаного на рис. 2, становить Θ (N3), оскільки, щоб знайти елементи з найбільшою подібністю на кожній з N - 1 ітерацій необхідно здійснити повний перебір елементів матриці С, що має розмірність N x N.

Для чотирьох методів, розглянутих у цій роботі, більш ефективним є алгоритм (EfficientHAC), що використовує черги з пріоритетом. Його часова складність - Θ (N2logN). Рядки С[k] матриці подібності С, має розмірність N x N, сортуються в порядку убування схожості в чергах з пріоритетами Р. Після цього функція P [k]. Max () повертає кластер в елементі Р [k], який в даний момент більше всіх схожий на кластер ωk, де кластер ωk - це k-й кластер. Після об'єднання кластерів ωk1, і ωk2, кластер ωi, використовується в якості представника об'єднаного кластера. Функція Sim обчислює міру подібності між потенційними парами, що підлягають об'єднанню: в методі одиночної зв'язку - найбільшу, в методі повної зв'язку - найменшу, в методі GAAC - середню.

Часова складність обох циклів верхнього рівня дорівнює Θ (N2log N) для реалізації черги з пріоритетом, яка підтримує видалення і вставку за час Θ (logN). Отже, загальна складність алгоритму дорівнює Θ (N2log N). У визначенні функції Sim вектори vm і vi - це вектори сум ωk1k2, a Nm і N - кількість документів у множині зі, ωk1 U ωk2 і ωi відповідно.

Аргументом функції EfficientHAC є множина векторів (на відміну від множини типових документів), оскільки агломеративна кластеризація на основі усереднення по групі, і кластеризації за допомогою порівняння центроїдів в якості вхідної інформації вимагають векторів. Версію алгоритму EfficientHAC для методу повного зв'язку також можна застосувати до документів, які не представляються у вигляді векторів.

У версію кластеризації з одиночним зв'язком, з метою його оптимізації можна ввести масив найкращих кандидатів на об'єднання (next-best-merge array - NBM). Масив NBM відстежує найкраще об'єднання для кожного кластера. Кожен з двох циклів верхнього рівня, що показано нижче, має часову складність Θ (N2), тому загальна складність кластеризації методом одиночного зв'язку становить Θ (N2).

Чи можна прискорити за допомогою масиву NBM три інших методи агломеративної неієрархічної кластеризації? Не можна, так як тільки кластеризація методом одиночної зв'язку є стійкою по відношенню до найкращого об'єднання. Припустимо, що в кластеризації методом одиночної зв'язку найкращим кандидатом на об'єднання з кластером ωk є кластер ωj. Тоді після об'єднання кластера ωj з третім кластером ωi ≠ ωj об'єднання кластерів ωi і ωj) буде найкращим кандидатом на об'єднання з кластером ωk. Інакше кажучи, в кластеризації методом одиночної зв’язку, найкращим кандидатом на об'єднання з уже об'єднаним кластером є один з двох найкращих кандидатів на об'єднання з його компонент. Це означає, що масив С на кожній ітерації можна оновити за час Θ (N), просто обчисливши максимум серед двох чисел у рядку 14 для кожного з решти кластерів, кількість яких не перевищує N.

На рис. 8 показано, що стійкість по відношенню до найкращого об'єднання не зберігається в алгоритмі кластеризації методом повного зв'язку. Це означає, що ми не можемо використовувати масив NBM для прискорення кластеризації. Після об'єднання кластера d2, найкращого кандидата на об'єднання з кластером з кластером d3 окремий кластер d1 стає найкращим кандидатом на об'єднання з кластером d3. Це пояснюється тим, що критерій повного зв'язку є нелокальним і залежить від точок, що знаходяться на великій відстані від області дотику двох кандидатів на об'єднання.

Рис. 8. Кластеризація методом повної зв'язку не є стійкою по відношенню до найкращого об'єднання. Спочатку найкращим кандидатом на об'єднання з кластером d3 є документ d2. Однак після об'єднання кластерів d1 до d2 найкращим кандидатом на об'єднання є кластер d4. У стійкому алгоритмі, такому як алгоритм методу одиночної зв'язку, найкращим кандидатом на об'єднання з d3 був би кластер {d1, d2}

На практиці зниження ефективності алгоритму зі складністю Θ(N2logN) порівняно з алгоритмом методу одиночного зв'язку, що має складність Θ(N2), невелика, оскільки обчислення міри подібності між двома документами виконується на порядок повільніше, ніж порівняння двох чисел при сортуванні. Всі чотири алгоритми в цій главі мають складність Θ(N2) з урахуванням обчислення міри подібності. Отже, відмінності по складності на практиці рідко беруться до уваги при виборі алгоритму.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.