Львів
C
» » Метод кластеризації: опис, основні поняття, особливості застосування

Метод кластеризації: опис, основні поняття, особливості застосування

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

Завдання оптимізації

Метод кластеризації: опис, основні поняття, особливості застосування
Сам метод кластеризації — це не один конкретний алгоритм, а загальна завдання, яку потрібно вирішити. Це може бути досягнуто за допомогою різних алгоритмів, які суттєво різняться в розумінні того, що складає група і як її ефективно знаходити. Використання методу кластеризації для формування метапредметных включають в себе застосування групи з невеликими відстанями між членами, щільними областями простору, інтервалами або певними статистичними розподілами. Тому кластеризацію можна сформулювати як багатоцільову задачу оптимізації.


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


Кластерний аналіз був заснований по численним роботам Кребера в 1932 році. І введений в психологію Зубиным в 1938 і Робертом Трионом в 1939 році. І дані використовувалися праці Кеттелом починаючи з 1943 р. для позначення ознаки класифікація методів кластеризації в теорії.

Термін

Метод кластеризації: опис, основні поняття, особливості застосування
Поняття «кластер» не може бути точно визначено. Це є однією з причин, по якій є так багато методів кластеризації. Існує загальний знаменник: група об'єктів даних. Проте різні дослідники використовують різні моделі. І кожне з цих використання методів кластеризації включає в себе різні дані. Поняття знайденого всілякими алгоритмами істотно розрізняється за його властивостями. Використання методу кластеризації є ключем до розуміння відмінностей між інструкціями. Типові кластерні моделі включають в себе:
  • Центроїд s. Це, наприклад, коли кластеризація методом к-середніх представляє кожен кластер з одним середнім вектором.
  • Модель зв'язності s. Це вже, наприклад, ієрархічна кластеризація, яка будує моделі на основі дистанційної зв'язності.
  • Модель розподілу s. В даному випадку кластери моделюються з використанням методу кластеризації для формування метапредметных статистичних розподілів. Таких як багатовимірний нормальний розподіл, який застосовується для алгоритму максимізації очікування.
  • Модель щільності s. Це, наприклад, DBSCAN (алгоритм просторової кластеризації з присутністю шуму) і OPTICS (точки замовлення для визначення структури), які визначають групи як пов'язані щільні області в просторі даних.
  • Модель підпростору с. В biclustering (також відомий як кластеризація або два режими) групи моделюються з обома елементами і з відповідними атрибутами.
  • Модель s. Деякі алгоритми не дають уточнену зв'язок для їхнього методу кластеризації для формування метапредметных результатів і просто забезпечують групування інформації.
  • Модель на основі графа s. Клік, тобто підмножина вузлів, такий, що кожні два з'єднання в реберної частини можна розглядати як прототип форми кластера. Ослаблення повного вимоги відомі як квазиклики. Точно таку ж назву представлено алгоритм кластеризації HCS.
  • Нейронні моделі s. Найбільш відомою мережею без нагляду є самоорганізована карта. І саме ці моделі зазвичай можна охарактеризувати як аналогічні одному або декількох з вищевказаних методів кластеризації для формування метапредметных результатів. Він включає в себе подпространственные системи тоді, коли нейронні мережі реалізують необхідну форму аналізу головних або незалежних компонентів.
  • Даний термін – це, по суті, комплект таких груп, які зазвичай містять всі об'єкти в наборі методів кластеризації даних. Крім того, він може вказувати відносини кластерів один до одного, наприклад, ієрархію систем, вбудованих один в одного. Угруповання може бути розділена на наступні аспекти:
  • Жорсткий центроїдне метод кластеризації. Тут кожен об'єкт належить групі або перебуває за її межами.
  • М'яка або нечітка система. В даному пункті вже кожен об'єкт певною мірою належить кожному кластеру. Називається він також методом нечіткої кластеризації c-середніх.
  • І також можливі більш тонкі відмінності. Наприклад:
  • Сувора секционирующая кластеризація. Тут кожен об'єкт належить рівно одній групі.
  • Сувора секционирующая кластеризація з викидами. В даному випадку, об'єкти також можуть не належати до одного кластера і вважатися непотрібними.
  • Перекриваються кластеризація (також альтернативна, з кількома поданнями). Тут об'єкти можуть належати більш ніж до одного відгалуження. Як правило, з участю твердих кластерів.
  • Ієрархічні методи кластеризації. Об'єкти, що належать дочірньої групі, також належать батьківської підсистеми.
  • Формування підпростору. Хоча вони і схожі на кластери з перекриттям, всередині унікально певної системи взаємні групи не повинні загораживаться.
  • Інструкція

    Метод кластеризації: опис, основні поняття, особливості застосування
    Як зазначено вище, алгоритми кластеризації можна класифікувати на основі кластерної моделі. В наступному огляді будуть перераховані лише найбільш яскраві приклади даних інструкцій. Оскільки, можливо, існує понад 100 опублікованих алгоритмів, не всі надають моделі для своїх кластерів, і тому не можуть бути легко класифіковані.
    Не існує об'єктивно правильного алгоритму кластеризації. Але, як було зазначено вище, інструкція завжди знаходиться в полі зору спостерігача. Найбільш відповідний алгоритм кластеризації для конкретної задачі часто доводиться вибирати експериментально, якщо тільки немає математичної причини для переваги однієї моделі іншою. Слід зазначити, що алгоритм, розроблений для єдиного типу, зазвичай не працює з набором даних, який містить радикально інший суб'єкт. Наприклад, k-means не може знайти невыпуклые групи.

    Кластеризація на основі сполук

    Метод кластеризації: опис, основні поняття, особливості застосування
    Це об'єднання також відомо за такої назви, як ієрархічна модель. Вона заснована на типової ідеї про те, що об'єкти в більшій мірі пов'язані з сусідніми частинами, ніж з тими, які знаходяться набагато далі. Ці алгоритми з'єднують предмети, утворюючи різні кластери, в залежності від їх відстані. Група може бути описана в основному максимальної дистанцією, яка необхідна для з'єднання різних частин кластера. На різних відстанях утворюватимуться інші групи, які можна представити за допомогою дендрограми. Це пояснює, звідки походить загальну назву «ієрархічна кластеризація». Тобто ці алгоритми не забезпечують єдиного поділу набору даних, а замість цього надають великий порядок підпорядкування. Саме завдяки йому відбувається злив один з одним на певних відстанях. У дендрограмі вісь Y позначає дистанцію, на якій кластери об'єднуються. А об'єкти розташовуються вздовж прямої X так, що групи не змішуються.

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

    Розподілена кластеризація

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

    Модель гауссових суміші

    Даний спосіб використовують різні алгоритми максимізації очікування. Тут набір даних зазвичай моделюється з фіксованим (щоб уникнути перевизначення) числом гаусівських розподілів, які ініціалізуються випадковим чином і параметри яких ітеративне оптимізуються для кращої відповідності набору даних. Ця система буде сходитися до локального оптимуму. Саме тому кілька прогонів можуть давати різні результати. Щоб отримати саму жорстку кластеризацію, об'єкти часто присвоюються гауссовскому розподілу, до якого вони належать. А для більш м'яких груп це не обов'язково. Кластеризація на основі розподілу створює складні моделі, які в кінцевому рахунку можуть фіксувати кореляцію і залежність між атрибутами. Однак ці алгоритми накладають додатковий тягар на користувача. Для багатьох реальних наборів даних може не бути коротко певної математичної моделі (наприклад, якщо припускати, що гаусівських розподілу розподіл є досить сильним допущенням).

    Кластеризація на основі щільності

    Метод кластеризації: опис, основні поняття, особливості застосування
    В даному прикладі групи в основному визначаються як галузі з більш високою непроникністю, ніж інша частина набору даних. Об'єкти в цих рідкісних частинах, які необхідні для поділу всіх компонентів, зазвичай вважаються шумом і прикордонними пунктами. Найбільш популярним методом кластеризації на основі щільності є DBSCAN (алгоритм просторової кластеризації з присутністю шуму). На відміну від багатьох нових способів він має чітко визначену кластерну складову, звану «досяжність щільності». Подібно кластеризації на основі зв'язків, вона заснована на крапках з'єднання в межах визначених порогів відстані. Однак такий метод збирає лише ті пункти, які задовольняють критерієм щільності. У вихідному варіанті, визначеному як мінімальна кількість інших об'єктів в цьому радіусі, кластер складається з усіх предметів, пов'язаних щільністю (які можуть утворювати групу довільної форми, на відміну від багатьох інших методів), а також всіх об'єктів, які знаходяться в межах допустимого діапазону. Іншим цікавим властивістю DBSCAN є те, що його складність досить низька — він вимагає лінійного кількості запитів до діапазону базі даних. А також незвичайність полягає в тому, що він виявить, по суті, ті ж самі результати (це є детермінованим для основних і шумових точок, але не для граничних елементів) у кожному прогоні. Тому немає ніякої необхідності запускати його кілька разів. Основний недолік DBSCAN і OPTICS полягає в тому, що вони очікують деякого падіння щільності для виявлення меж кластера. Наприклад, в наборах даних з перекриваються розподілами Гаусса — поширений випадок використання штучних об'єктів — межі кластерів, створювані цими алгоритмами, часто виглядають довільно. Відбувається це, оскільки щільність груп безперервно зменшується. А в наборі даних, що складається із сумішей гауссианов, ці алгоритми майже завжди перевершують такі методи, як EM-кластеризація, які здатні точно моделювати системи такого типу. Середнє зміщення — це кластерний підхід, при якому кожний об'єкт переміщається в саму щільну область в околиці на основі оцінки всього ядра. Зрештою, об'єкти сходяться до локальних максимумів непроникності. Подібно кластеризації методом к-середніх, ці «атрактори щільності» можуть служити представниками для набору даних. Але середнє зміщення може виявляти кластери довільної форми, аналогічні DBSCAN. Через дорогий ітеративної процедури та оцінки щільності середнє переміщення зазвичай повільніше, ніж DBSCAN або k-Means. Крім того, застосування алгоритму типового зсуву до багатовимірних даних утруднена через нерівномірного поведінки оцінки щільності ядра, що призводить до надмірної фрагментації хвостів кластерів.

    Оцінка

    Метод кластеризації: опис, основні поняття, особливості застосування
    Перевірка результатів кластеризації так само складна, як і сама угруповання. Популярні підходи включають «внутрішню» оцінку (де система зводиться до одного показника якості) і, звичайно ж, «зовнішню» позначку (де кластеризацію порівнюють з існуючою класифікацією «основоположною правди»). А ручну оцінку експерта-людини і непрямий бал знаходять шляхом вивчення корисності кластеризації в передбачуваному додатку. Внутрішні заходи позначки страждають від проблеми, яка полягає в тому, що вони представляють функції, які самі по собі можна розглядати як цілі кластеризації. Наприклад, можна групувати дані, задані коефіцієнтом Силует, за винятком того, що не існує відомого ефективного алгоритму для цього. Використовуючи таку внутрішню міру для оцінки, краще порівнювати схожість задач оптимізації. Зовнішня оцінка має аналогічні проблеми. Якщо є такі ярлики «наземної правди», то не потрібно кластеризоваться. І в практичних додатках зазвичай немає таких понять. З іншого боку, мітки відображають лише одне можливе розбиття набору даних, що не означає, що не існує іншого (а, може, навіть краще) кластеризації. Тому ні один з цих підходів не може у кінцевому підсумку судити про фактичне якості. Але це потребує людської оцінки, яка є досить суб'єктивною. Тим не менше така статистика може бути інформативною при виявленні поганих кластерів. Але не слід скидати з рахунків суб'єктивну оцінку людини.

    Внутрішня відмітка

    Коли результат кластеризації оцінюється на основі даних, які були самі кластеризованы, це називається даним терміном. Ці методи зазвичай присвоюють кращий результат алгоритмом, який створює групи з високою схожістю всередині і низьким між групами. Одним з недоліків використання внутрішніх критеріїв в оцінці кластера є те, що високі позначки необов'язково призводять до ефективних додатків для пошуку інформації. Крім того, цей бал зміщений у бік алгоритмів, які використовують ту ж модель. Наприклад, кластеризація k-середніх природним чином оптимізує відстані до об'єктів, а внутрішній критерій, заснований на ньому, ймовірно, буде переоцінювати результуючу угруповання. Тому заходи такої оцінки найкраще підходять для того, щоб отримати уявлення про ситуації, коли один алгоритм працює краще, ніж інший. Але це не означає, що кожна інформація дає більш достовірні результати, ніж інша. Термін дії, вимірюваний таким індексом, залежить від твердження про те, що структура існує в наборі даних. Алгоритм, розроблений для деяких типів, не має шансів, якщо комплект містить радикально інший склад, або якщо оцінка вимірює різні критерій. Наприклад, кластеризація k-середніх може знайти тільки опуклі кластери, а багато індекси оцінки припускають той самий формат. У наборі даних з невыпуклыми моделями недоцільно використання k-середніх і типових критеріїв оцінки.

    Зовнішня оцінка

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