Відмінності між версіями «Кластерний аналіз»
Mike (обговорення • внесок) м (rollback vandalism) |
|||
| (Не показані 19 проміжних версій 6 користувачів) | |||
| Рядок 1: | Рядок 1: | ||
| − | |||
'''Кластерний аналіз''' (англ. Data clustering) - задача розбиття заданої вибірки об'єктів (ситуацій) на підмножини, що називаються кластерами, так, щоб кожен кластер складався з схожих об'єктів, а об'єкти різних кластерів істотно відрізнялися. Задача кластеризації відноситься до статистичної обробки, а також до широкого класу задач навчання без учителя. | '''Кластерний аналіз''' (англ. Data clustering) - задача розбиття заданої вибірки об'єктів (ситуацій) на підмножини, що називаються кластерами, так, щоб кожен кластер складався з схожих об'єктів, а об'єкти різних кластерів істотно відрізнялися. Задача кластеризації відноситься до статистичної обробки, а також до широкого класу задач навчання без учителя. | ||
| Рядок 6: | Рядок 5: | ||
'''Кластер''' - група елементів, якi характеризуються загальною властивістю, головна мета кластерного аналізу - знаходження груп схожих об'єктів у вибірці. Спектр застосування кластерного аналізу дуже широкий: його використовують в археології, медицині, психології, хімії, біології, державному управлінні, філології, антропології, маркетингу, соціології та інших дисциплінах. «Тематика досліджень варіює від аналізу морфології муміфікованих гризунів у Новій Гвінеї до вивчення результатів голосування сенаторів США Однак універсальність застосування призвела до появи великої кількості несумісних термінів, методів і підходів, що ускладнюють однозначне використання і несуперечливу інтерпретацію кластерного аналізу. | '''Кластер''' - група елементів, якi характеризуються загальною властивістю, головна мета кластерного аналізу - знаходження груп схожих об'єктів у вибірці. Спектр застосування кластерного аналізу дуже широкий: його використовують в археології, медицині, психології, хімії, біології, державному управлінні, філології, антропології, маркетингу, соціології та інших дисциплінах. «Тематика досліджень варіює від аналізу морфології муміфікованих гризунів у Новій Гвінеї до вивчення результатів голосування сенаторів США Однак універсальність застосування призвела до появи великої кількості несумісних термінів, методів і підходів, що ускладнюють однозначне використання і несуперечливу інтерпретацію кластерного аналізу. | ||
| − | =Задачі і умови= | + | ==Задачі і умови== |
Кластерний аналіз виконує такі основні завдання: | Кластерний аналіз виконує такі основні завдання: | ||
| Рядок 29: | Рядок 28: | ||
# Показники повинні відповідати вимогу «стійкості», під якою розуміється відсутність впливу на їх значення випадкових факторів; | # Показники повинні відповідати вимогу «стійкості», під якою розуміється відсутність впливу на їх значення випадкових факторів; | ||
# Вибірка повинна бути однорідна, не містити «викидів». Якщо кластерного аналізу передує факторний аналіз, то вибірка не потребує «ремонту» - викладені вимоги виконуються автоматично самою процедурою факторного моделювання (є ще одна перевага - z-стандартизація без негативних наслідків для вибірки; якщо її проводити безпосередньо для кластерного аналізу, вона може спричинити за собою зменшення чіткості поділу груп). В іншому випадку вибірку потрібно коригувати. | # Вибірка повинна бути однорідна, не містити «викидів». Якщо кластерного аналізу передує факторний аналіз, то вибірка не потребує «ремонту» - викладені вимоги виконуються автоматично самою процедурою факторного моделювання (є ще одна перевага - z-стандартизація без негативних наслідків для вибірки; якщо її проводити безпосередньо для кластерного аналізу, вона може спричинити за собою зменшення чіткості поділу груп). В іншому випадку вибірку потрібно коригувати. | ||
| + | =Типи задач кластеризації= | ||
==Типи вхідних даних== | ==Типи вхідних даних== | ||
*Опис об'єктів за ознаками. Кожен об'єкт описується набором своїх характеристик, які називаються ознаками. Ознаки можуть бути числовими або нечислових. | *Опис об'єктів за ознаками. Кожен об'єкт описується набором своїх характеристик, які називаються ознаками. Ознаки можуть бути числовими або нечислових. | ||
| Рядок 34: | Рядок 34: | ||
==Цілі кластеризації== | ==Цілі кластеризації== | ||
| − | Розуміння даних шляхом виявлення кластерної структури. Розбиття вибірки на групи схожих об'єктів дозволяє спростити подальшу обробку даних і прийняття рішень, застосовуючи до кожного кластеру свій метод аналізу (стратегія «розділяй і володарюй»). | + | * Розуміння даних шляхом виявлення кластерної структури. Розбиття вибірки на групи схожих об'єктів дозволяє спростити подальшу обробку даних і прийняття рішень, застосовуючи до кожного кластеру свій метод аналізу (стратегія «розділяй і володарюй»). |
| − | Стиснення даних. Якщо початкова вибірка надто велика, то можна скоротити її, залишивши по одному найбільш типовому представнику від кожного кластеру. | + | * Стиснення даних. Якщо початкова вибірка надто велика, то можна скоротити її, залишивши по одному найбільш типовому представнику від кожного кластеру. |
| − | Виявлення новизни (англ. novelty detection). Виділяються нетипові об'єкти, які не вдається приєднати до жодного з кластерів. | + | * Виявлення новизни (англ. novelty detection). Виділяються нетипові об'єкти, які не вдається приєднати до жодного з кластерів. |
У першому випадку число кластерів намагаються зробити поменше. У другому випадку важливіше забезпечити високу ступінь подібності об'єктів усередині кожного кластеру, а кластерів може бути скільки завгодно. У третьому випадку найбільший інтерес представляють окремі об'єкти, які не вписуються ні в один з кластерів. | У першому випадку число кластерів намагаються зробити поменше. У другому випадку важливіше забезпечити високу ступінь подібності об'єктів усередині кожного кластеру, а кластерів може бути скільки завгодно. У третьому випадку найбільший інтерес представляють окремі об'єкти, які не вписуються ні в один з кластерів. | ||
| Рядок 42: | Рядок 42: | ||
У всіх цих випадках може застосовуватися ієрархічна кластеризація, коли великі кластери дробляться на більш дрібні, ті в свою чергу дробляться ще дрібніші, і т. д. Такі завдання називаються завданнями таксономії. | У всіх цих випадках може застосовуватися ієрархічна кластеризація, коли великі кластери дробляться на більш дрібні, ті в свою чергу дробляться ще дрібніші, і т. д. Такі завдання називаються завданнями таксономії. | ||
| − | Результатом таксономії є | + | Результатом таксономії є деревоподібна ієрархічна структура. При цьому кожен об'єкт характеризується перерахуванням всіх кластерів, яким він належить, звичайно від великого до дрібного. |
Класичним прикладом таксономії на основі подібності є Біноміальна номенклатура живих істот, запропонована Карлом Ліннеєм в середині XVIII століття. Аналогічні систематизації будуються в багатьох областях знання, щоб упорядкувати інформацію про велику кількість об'єктів. | Класичним прикладом таксономії на основі подібності є Біноміальна номенклатура живих істот, запропонована Карлом Ліннеєм в середині XVIII століття. Аналогічні систематизації будуються в багатьох областях знання, щоб упорядкувати інформацію про велику кількість об'єктів. | ||
| + | |||
| + | =Формальна постановка задачі кластеризації= | ||
| + | |||
| + | Нехай <math>X~</math> - безліч об'єктів, <math>Y~</math> - множина номерів (імен, міток) кластерів. Задана функція відстані між об'єктами <math>\rho(x,x')~</math>. Є кінцева навчальна вибірка об'єктів <math>X^m = \{ x_1, \dots, x_m \} \subset X</math>. Потрібно розбити вибірку на непересічні підмножини, що називаються ''кластерами'', так, щоб кожен кластер складався з об'єктів, які близькі по мітці <math>\rho~</math>, а об'єкти різних кластерів істотно відрізнялися. При цьому кожному об'єкту <math>x_i\in X^m</math> приписується номер кластеру <math>y_i~</math>. | ||
| + | |||
| + | ''Алгоритм кластеризації'' - це функція <math>a\colon X\to Y</math>, яка будь-якого об'єкту <math>x\in X</math> ставить у відповідність номер кластеру <math>y\in Y</math>. Безліч в деяких випадках відомо заздалегідь, однак частіше ставиться завдання визначити оптимальне число кластерів, з точки зору того чи іншого ''критерію якості'' кластеризації. | ||
| + | |||
| + | Кластеризація (навчання без учителя) відрізняється від класифікації (навчання з учителем) тим, що мітки вихідних об'єктів з самого початку не задані, і навіть може бути невідомо сама множина <math>Y</math>. | ||
| + | |||
| + | Вирішення кластеризації принципово неоднозначно, і на те є кілька причин: | ||
| + | #не існує однозначно найкращого критерію якості кластеризації. Відомий цілий ряд евристичних критеріїв, а також ряд алгоритмів, які не мають чітко вираженого критерію, але здійснюють досить розумну кластеризації «з побудови». Всі вони можуть давати різні результати. | ||
| + | #число кластерів, як правило, невідомо заздалегідь і встановлюється відповідно до деякого суб'єктивний критерій. | ||
| + | #результат кластеризації істотно залежить від метрики, вибір якої, як правило, також суб'єктивний і визначається експертом. | ||
| + | |||
| + | =Використанння= | ||
| + | |||
| + | *Аналіз даних (Data mining) - це групування результатів пошуку. Кластеризація використовується для «інтелектуального» групування результатів при пошуку файлів, веб-сайтів, інших об'єктів, надаючи користувачеві можливість швидкої навігації, вибору свідомо більш релевантної підмножини і виключення свідомо менш релевантної - що може підвищити юзабіліті інтерфейсу в порівнянні з виводом в вигляді просто сортувати за релевантністю списку. | ||
| + | **Спрощення роботи з інформацією | ||
| + | http://www.nigma.ru/ пошукова система з автоматичним кластеруванням | ||
| + | **Візуалізація даних | ||
| + | http://www.quintura.ru/ інтерактивний візуальний пошук по інтернет ресурсам. | ||
| + | *Групування і розпізнаванння образів | ||
| + | Кластеризація може бути викоритана для розбиття цифрового зображення на окремі області з метою знаходження границь чи розпізнавання образів | ||
| + | *Вибір і пошук інформації | ||
| + | **Побудова зручних класифікаторів | ||
| + | |||
| + | ==Список використаних джерел== | ||
| + | |||
| + | #http://www.basegroup.ru/library/analysis/clusterization/ | ||
| + | #http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F | ||
| + | #http://www.ccas.ru/voron/download/Clustering.pdf | ||
| + | |||
| + | |||
| + | {{Завдання:Виступ|Hnytka|13 січня 2010|Кластерний аналіз}} | ||
| + | |||
| + | [[Категорія:Виступ на семінарі]] | ||
| + | [[Категорія:Планування експерименту]] | ||
Поточна версія на 01:23, 14 січня 2023
Кластерний аналіз (англ. Data clustering) - задача розбиття заданої вибірки об'єктів (ситуацій) на підмножини, що називаються кластерами, так, щоб кожен кластер складався з схожих об'єктів, а об'єкти різних кластерів істотно відрізнялися. Задача кластеризації відноситься до статистичної обробки, а також до широкого класу задач навчання без учителя.
Кластерний аналіз - це багатовимірна статистична процедура, що виконує збір даних, що містять інформацію про вибірку об'єктів, сортування об'єктів в порівняно однорідні групи (кластери) (Q-кластеризація, або Q-техніка, власне кластерний аналіз).
Кластер - група елементів, якi характеризуються загальною властивістю, головна мета кластерного аналізу - знаходження груп схожих об'єктів у вибірці. Спектр застосування кластерного аналізу дуже широкий: його використовують в археології, медицині, психології, хімії, біології, державному управлінні, філології, антропології, маркетингу, соціології та інших дисциплінах. «Тематика досліджень варіює від аналізу морфології муміфікованих гризунів у Новій Гвінеї до вивчення результатів голосування сенаторів США Однак універсальність застосування призвела до появи великої кількості несумісних термінів, методів і підходів, що ускладнюють однозначне використання і несуперечливу інтерпретацію кластерного аналізу.
Зміст
Задачі і умови
Кластерний аналіз виконує такі основні завдання:
- Розробка типології або класифікації.
- Дослідження корисних концептуальних схем групування об'єктів.
- Породження гіпотез на основі дослідження даних.
- Перевірка гіпотез або дослідження для визначення, чи дійсно типи (групи), виділені тим або іншим способом, присутні у наявних даних.
Незалежно від предмета вивчення застосування кластерного аналізу припускає наступні етапи:
- Відбір вибірки для кластеризації
- Визначення безлічі змінних, за якими будуть оцінюватися об'єкти у вибірці.
- Обчислення значень тієї чи іншої міри схожості між об'єктами.
- Застосування методу кластерного аналізу для створення груп схожих об'єктів.
- Перевірка достовірності результатів кластерного рішення.
Кластерний аналіз пред'являє наступні вимоги до даних:
- Показники не повинні корелювати між собою,
- Показники повинні бути безрозмірними;
- Їх розподіл має бути близько до нормального;
- Показники повинні відповідати вимогу «стійкості», під якою розуміється відсутність впливу на їх значення випадкових факторів;
- Вибірка повинна бути однорідна, не містити «викидів». Якщо кластерного аналізу передує факторний аналіз, то вибірка не потребує «ремонту» - викладені вимоги виконуються автоматично самою процедурою факторного моделювання (є ще одна перевага - z-стандартизація без негативних наслідків для вибірки; якщо її проводити безпосередньо для кластерного аналізу, вона може спричинити за собою зменшення чіткості поділу груп). В іншому випадку вибірку потрібно коригувати.
Типи задач кластеризації
Типи вхідних даних
- Опис об'єктів за ознаками. Кожен об'єкт описується набором своїх характеристик, які називаються ознаками. Ознаки можуть бути числовими або нечислових.
- Матриця відстаней між об'єктами. Кожен об'єкт описується відстанями до всіх інших об'єктів навчальної вибірки.
Цілі кластеризації
- Розуміння даних шляхом виявлення кластерної структури. Розбиття вибірки на групи схожих об'єктів дозволяє спростити подальшу обробку даних і прийняття рішень, застосовуючи до кожного кластеру свій метод аналізу (стратегія «розділяй і володарюй»).
- Стиснення даних. Якщо початкова вибірка надто велика, то можна скоротити її, залишивши по одному найбільш типовому представнику від кожного кластеру.
- Виявлення новизни (англ. novelty detection). Виділяються нетипові об'єкти, які не вдається приєднати до жодного з кластерів.
У першому випадку число кластерів намагаються зробити поменше. У другому випадку важливіше забезпечити високу ступінь подібності об'єктів усередині кожного кластеру, а кластерів може бути скільки завгодно. У третьому випадку найбільший інтерес представляють окремі об'єкти, які не вписуються ні в один з кластерів.
У всіх цих випадках може застосовуватися ієрархічна кластеризація, коли великі кластери дробляться на більш дрібні, ті в свою чергу дробляться ще дрібніші, і т. д. Такі завдання називаються завданнями таксономії.
Результатом таксономії є деревоподібна ієрархічна структура. При цьому кожен об'єкт характеризується перерахуванням всіх кластерів, яким він належить, звичайно від великого до дрібного.
Класичним прикладом таксономії на основі подібності є Біноміальна номенклатура живих істот, запропонована Карлом Ліннеєм в середині XVIII століття. Аналогічні систематизації будуються в багатьох областях знання, щоб упорядкувати інформацію про велику кількість об'єктів.
Формальна постановка задачі кластеризації
Нехай [math]X~[/math] - безліч об'єктів, [math]Y~[/math] - множина номерів (імен, міток) кластерів. Задана функція відстані між об'єктами [math]\rho(x,x')~[/math]. Є кінцева навчальна вибірка об'єктів [math]X^m = \{ x_1, \dots, x_m \} \subset X[/math]. Потрібно розбити вибірку на непересічні підмножини, що називаються кластерами, так, щоб кожен кластер складався з об'єктів, які близькі по мітці [math]\rho~[/math], а об'єкти різних кластерів істотно відрізнялися. При цьому кожному об'єкту [math]x_i\in X^m[/math] приписується номер кластеру [math]y_i~[/math].
Алгоритм кластеризації - це функція [math]a\colon X\to Y[/math], яка будь-якого об'єкту [math]x\in X[/math] ставить у відповідність номер кластеру [math]y\in Y[/math]. Безліч в деяких випадках відомо заздалегідь, однак частіше ставиться завдання визначити оптимальне число кластерів, з точки зору того чи іншого критерію якості кластеризації.
Кластеризація (навчання без учителя) відрізняється від класифікації (навчання з учителем) тим, що мітки вихідних об'єктів з самого початку не задані, і навіть може бути невідомо сама множина [math]Y[/math].
Вирішення кластеризації принципово неоднозначно, і на те є кілька причин:
- не існує однозначно найкращого критерію якості кластеризації. Відомий цілий ряд евристичних критеріїв, а також ряд алгоритмів, які не мають чітко вираженого критерію, але здійснюють досить розумну кластеризації «з побудови». Всі вони можуть давати різні результати.
- число кластерів, як правило, невідомо заздалегідь і встановлюється відповідно до деякого суб'єктивний критерій.
- результат кластеризації істотно залежить від метрики, вибір якої, як правило, також суб'єктивний і визначається експертом.
Використанння
- Аналіз даних (Data mining) - це групування результатів пошуку. Кластеризація використовується для «інтелектуального» групування результатів при пошуку файлів, веб-сайтів, інших об'єктів, надаючи користувачеві можливість швидкої навігації, вибору свідомо більш релевантної підмножини і виключення свідомо менш релевантної - що може підвищити юзабіліті інтерфейсу в порівнянні з виводом в вигляді просто сортувати за релевантністю списку.
- Спрощення роботи з інформацією
http://www.nigma.ru/ пошукова система з автоматичним кластеруванням
- Візуалізація даних
http://www.quintura.ru/ інтерактивний візуальний пошук по інтернет ресурсам.
- Групування і розпізнаванння образів
Кластеризація може бути викоритана для розбиття цифрового зображення на окремі області з метою знаходження границь чи розпізнавання образів
- Вибір і пошук інформації
- Побудова зручних класифікаторів
Список використаних джерел
- http://www.basegroup.ru/library/analysis/clusterization/
- http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F
- http://www.ccas.ru/voron/download/Clustering.pdf
- Студент: Користувач:Hnytka
- Виступ відбувся: 13 січня 2010
- Тема: Кластерний аналіз
