Формальна постановка завдання кластеризації

Нехай існує безліч об'єктів, безліч номерів (імен) кластерів. Є задана функція відстані між об'єктами, є наявна кінцева скінченна вибірка об'єктів. Потрібно розбити вибірку на непересічні підмножини, звані кластерами, так, щоб кожен кластер складався з об'єктів, близьких по метриці, а об'єкти різних кластерів істотно відрізняються. При цьому кожному об'єкту приписується номер кластера.

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

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

Розв’язок задачі кластеризації принципово неоднозначний, і тому є декілька причин:

· не існує однозначно найкращого критерію якості кластеризації. Відомий цілий ряд, низка евристичних критеріїв, а також низка алгоритмів, що не мають чітко вираженого висловлюваного критерію. Всі вони можуть давати різні результати;

· число кластерів, як правило, невідоме заздалегідь наперед і встановлюється відповідно до деякого суб'єктивного критерію;

· результат кластеризації істотно суттєво залежить від метрики, вибір якої, як правило, також суб'єктивний і визначається експертом;

· групування результатів пошуку: Кластеризація використовується для «інтелектуального» групування результатів при пошуку файлів, веб-сайтів, інших об'єктів, надаючи користувачеві можливість спроможність швидкої навігації, вибору свідомо більш релевантної підмножини і виключення винятку свідомо менш ревалентного — що може підвищити «юзабіліті» інтерфейсу в порівнянні з висновком, виведенням у вигляді простого сортованого по релевантнтності списку;

· Clusty — кластеризуюча пошукова машина компанії Vivisimo;

· Nigma — російська пошукова система із автоматичною кластеризацією результатів;

· Quintura — візуальна кластеризація у вигляді хмари ключових джерельних слів;

· сегментація зображень (image segmentation): Кластеризація може бути використана для розбиття цифрового зображення на окремі області з ціллю знаходження меж кордонів (edge detection), або розпізнавання об'єктів.

Завдання кластерного аналізу може бути сформульовано виходячи з наступних розміркувань. Нехай сукупність, що складається з n об'єктів, кожний з яких описується за допомогою m чинників-симптомів, задана у вигляді матриці вихідних (Х) або стандартизованих даних (Z), розміру n * m.

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

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

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

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

Після визначення матриці вихідних даних X, стандартизації чинників-симптомів і утворення матриці Z, розрахунку матриці відстаней D між усіма об’єктами (підприємствами)переходять до безпосереднього застосування алгоритмів кластерного аналізу, яких у теперішній час у математико-статистичній літературі налічується більше ста. Всі вони можуть бути згруповані у три основних напрямки:

а) процедури прямої класифікації;

б) оптимізаційні алгоритми;

в) апроксимаційні підходи.

Процедури прямої класифікації – це історично найбільш ранній напрямок кластерного аналізу, пов'язаний з іменами німецького біолога Ф. Гейнке, польського антрополога К. Чекановського, які на початку ХХ століття висунули ідеї пошуку компактних груп об'єктів у просторі множини ознак.

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