Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Львівський національний університет імені Івана Франка

Факультет управління фінансами та бізнесу

Кафедра обліку і аудиту

ІНДИВІДУАЛЬНЕ НАУКОВО-ДОСЛІДНЕ ЗАВДАННЯ

на тему “Кластерний аналіз”

Виконав:

студент групи УФОм-51с

Наконечний Руслан

Львів - 2019

Зміст

Вступ

1. Кластерний аналіз, переваги його застосування

2. Методи кластерного аналізу

2.1 Ієрархічні методи кластерного аналізу

2.2 Неієрархічні методи кластерного аналізу

Висновки

Список використаних джерел

Вступ

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

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

Мета кластеризації може різнитись залежно від особливостей конкретної прикладної задачі.

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

Основне завдання кластерного аналізу - формування однорідних груп у багатовимірному просторі.

1. Кластерний аналіз, переваги його застосування

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

У маркетингу це можуть бути завдання сегментації конкурентів і споживачів.

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

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

Кластерний аналіз має низку переваг перед іншими методами класифікації даних.

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

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

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

2. Методи кластерного аналізу

2.1 Ієрархічні методи кластерного аналізу

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

Алгоритми кластеризації зазвичай будується як певний спосіб перебору кількості кластерів і визначення його оптимального значення в процесі перебору та включають 5 основних кроків:

1. Відбір вибірки для кластеризації.

2. Визначення ознак, за якими будуть оцінюватися об'єкти в вибірці.

3. Обчислення значень тієї або іншої міри подібності між об'єктами.

4. Застосування кластерного аналізу для створення груп подібних об'єктів.

5. Перевірка достовірності результатів кластерного розв'язку.

На сьогодні існує велика кількість методів розбиття груп об'єктів на кластери. Існує декілька десятків алгоритмів і ще більше їх модифікацій.

Методи кластерного аналізу дозволяють розв'язувати наступні задачі:

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

- перевірка висунутих припущень про наявність певної структури в досліджуваній сукупності об'єктів, тобто відбувається пошук існуючої структури;

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

Методи кластерного аналізу можуть бути ієрархічними і неієрархічними.

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

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

При цьому на кожному кроці кількість кластерів змінюється в бік збільшення або зменшення. Робота більшості таких методів ґрунтується на обчисленні матриці схожості, яка містить міри відстаней - числа, що виражають "схожість" кожних двох об'єктів. Робота ієрархічних методів проілюстрована на рис. 2.1. Залежно від напрямку аналізу (розділення чи об'єднання об'єктів) ієрархічні методи поділяються на агломеративні (об'єднувальні) і дивизивні (розділові).

Рис. 2.1. Ієрархічні методи кластерного аналізу

Ієрархічні агломеративні методи (Agglomerative Nesting, AGNES) характеризується послідовним об'єднанням початкових елементів і відповідним зменшенням числа кластерів.

Усі такі методи переглядають матрицю схожості розмірності N (де N - кількість об'єктів) і послідовно об'єднують найбільш схожі об'єкти. Послідовність об'єднань кластерів можна подати візуально у вигляді дендрограми (рис. 2.2).

Рис. 2.2. Приклад вертикальної дендрограми

Числа 11, 10, 3 тощо відповідають номерам об'єктів або спостережень вхідної вибірки. На першому кроці кожне спостереження - це один кластер, на другому кроці спостерігаємо об'єднання таких спостережень: 11 і 10; 3, 4 і 5; 8 і 9; 2 і 6. На другому кроці триває об'єднання в кластери: спостереження 11, 10, 3, 4, 5 і 7, 8, 9. Даний процес триває доти, поки всі спостереження не об'єднаються в один кластер. Для повної кластеризації цими методами на основі матриці схожості розмірністю N потрібно N-1 кроків.

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

Загальну схему роботи ієрархічних агломеративних методів наведено на рис. 2.3.

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

Рис. 2.3.Ієрархічні агломеративні методи кластерного аналізу

1. Метод одиночного зв'язку (nearest neighbor analysis), або, як його іноді називають, метод аналізу найближчого сусіда,є одним з найпростіших ієрархічних методів, хоча й був запропонований одним з останніх у 1973 р.

В основі алгоритму найближчого сусіда лежить припущення, що якщо об'єкти близькі за значеннямиn-1властивості (ознаки), то вони близькі за значеннями n-ї властивості (рис. 2.4).

Рис. 2.4. Робота методу одиночного зв'язку

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

Рис. 2.5. Геометрична інтерпретація класифікації за методом аналізу найближчого сусіда

2. Метод повного зв'язку (метод дальнього сусіда) був запропонований Т. Сонерсоном у 1968 р. За цим методом правило об'єднання вказує, що схожість між кандидатами на включення в існуючий кластер і будь-яким із елементів цього кластера не повинна бути меншою від певного граничного рівня.

За відстань між двома кластерами вибирається максимальна відстань між об'єктами, що входять в різні кластери.

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

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

Рис. 2.5.Геометрична інтерпретація кластеризації за методом повного зв'язку (дальнього) сусіда

3.Метод середнього зв'язку(метод середніх) розроблявся як компроміс між методами одиночного і повного зв'язку. Дві групи точок об'єднуються, якщо середня відстань між парами точок з різних груп достатньо мала. Середня відстань обчислюється як середина для кожного кластера (рис. 2.6).

Рис. 2.6.Геометрична інтерпретація класифікації за методом аналізу середнього зв'язку

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

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

4.Метод Варда був запропонований у 1963 р. і до сьогодення є одним з найбільш популярних кластерних методів. Він побудований таким чином, щоб оптимізувати мінімальну дисперсію всередині кластерів. Ця цільова функція відома як внутрішньогрупова сума квадратів або сума квадратів відхилень (СКВ).

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

Рис. 2.7.Робота методу Варда

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

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

Загальну схему роботи ієрархічних дивизивних методів наведено на рис. 2.8.

2.2 Неієрархічні методи кластерного аналізу

Неієрархічні методи мають за основу вже задану кількість кластерів (k-means, PAM кластеризація) або використовують складні алгоритми знаходження їх кількості (CLOPE, карти Кохонена).

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

Рис. 2.8.Загальна схема роботи ієрархічних дивизивних методів

Серед неієрархічних методів кластеризації особливої уваги заслуговують ітеративні методи. Вони працюють за наступним алгоритмом:

1) вихідні дані розбиваються на певну кількість кластерів та обчислюються центри тяжіння цих кластерів;

2) кожна точка даних поміщується в кластер з найближчим центром тяжіння;

3) обчислюються нові центри тяжіння кластерів; кластери не замінюються на нові доти, поки не будуть повністю переглянуті всі дані;

4) кроки 2 і 3 повторюються доти, поки не перестануть змінюватись кластери.

Загальну схему роботи ітеративних методів подано на рис. 2.9.

Рис. 2.9.Загальна схема роботи ітеративних методів

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

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

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

До найбільш простих і ефективних алгоритмів кластеризації відноситься k-means, або в україномовному варіанті k-середніх,запропонований Г. Боллом і Д. Холлом у 1965 р. Конструктивно алгоритм - це ітераційна процедура, що складається з наступних кроків (рис. 2.10).

1. Задається кількість кластерів k, яка повинна бути сформована з об'єктів вхідної вибірки.

2. Випадковим чином обирається k записів, які будуть слугувати початковими центрами кластерів. Початкові точки, з яких потім виростають кластери, часто називають "насінням". Кожний такий запис являє собою "ембріон" кластера, що складається тільки з одного елемента.

Рис. 2.10. Приклад роботи алгоритму k-means

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

4. Проводиться обчислення центроїдів - центрів тяжіння кластерів. Це робиться шляхом визначення середнього для значень кожної ознаки всіх записів у кластері. Наприклад, якщо в кластер увійшли три записи з наборами ознак (x1, y1), (x2, y2), (x3, y3), то координати його центроїда будуть розраховуватися в такий спосіб:

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

Кроки 3 і 4 повторюються доти, поки виконання алгоритму не буде перервано або поки не буде виконана умова відповідно до певного критерію збіжності.

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

Алгоритм k-means звичайно знаходить набір стабільних кластерів за кілька десятків ітерацій.

Розвитком методу k-середніх є метод, що отримав назву ISODATA. Є низка алгоритмів, в основу яких покладені ідеї методів k-серед них та ISODATA.

кластеризація ієрархічний дендрограма

Висновки

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

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

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

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

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

Перевага цієї групи методів порівняно з неієрархічними методами - їх наочність і можливість одержати детальне подання структури даних. Перед проведенням кластеризації в аналітика може виникнути питання: якій групі методів кластерного аналізу надати перевагу?

Вибираючи між ієрархічними й неієрархічними методами, потрібно враховувати їхні особливості.

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

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

Список використаних джерел

1. Айвазян С.А., Бухштабер В.М., Енюков I.С., Мешалкин Л.Д. Прикладна статистика: класификацiя та понижені розмiрностi. -- М.: Фiнанси та статистика, 2009.

2. Журавльов Ю.I., Рязанов В.В., Сенько О.В. «Розпiзнання». Математичнi методи. Программна система. Практичнi застосування. -- М.: Фазис, 2006. ISBN 5-7036-0108-8.

3. Загоруйко Н.Г. Прикладнi методи аналiзу даних и знань. -- Новосибирск: ИМ СО РАН, 2009. ISBN 5-86134-060-9.

4. Мандель I.Д. Кластерний аналiз. -- М.: Фiнанси та статистика, 2008. ISBN 5-279-00050-7.

5. Паклин Н.Б., Орешков В.I. Бiзнес-аналитика: от данных к знаниям (+ СD). -СПб: Питер, 2009. ISBN 978-5-49807-257-9

6. Хайдуков Д.С. Застосунок кластерного аналізу в державному управління // Фiлософiя математики: актуальнi проблеми. - М.: МАКС Пресс, 2009.

7. Шлезингер М., Главач В. Десять лекцiй по статистичному та структурному розпiзнаваннi. -- Киев: Наукова думка, 2004. ISBN 966-00-0341-2.

Размещено на Allbest.ru