Материал: Кластерний аналіз

Кластерний аналіз

Вступ

програма деревовидний алгоритм кластеризація

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

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

Основною метою курсового проектування є:

–       навчання та набуття навиків практичного застосування теоретичних знань для вирішення конкретних практичних задач;

–       розвиток творчого мислення, виявлення та формування професійних навиків студентів;

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

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

–       набуття навиків узагальнення та аналізу результатів, отриманих іншими розробниками та дослідниками;

–       навчання та набуття студентами досвіду користування довідковою літературою і нормативними документами.

Мета курсового проектування з дисципліни «Основи програмування та алгоритмічні мови»:

–       закріпити знання, одержані під час вивчення дисципліни «Основи програмування та алгоритмічні мови;

–       засвоїти основні етапи розробки програмних виробів;

–       набути навиків при оформлення документів на програмні вироби;

одержати практичні навички з розробки програм і програмних документів.

1. Опис предметної області

.1 Метод k-середніх

Кластериза́ція ме́тодом k-сере́дніх - популярний метод кластеризації, - впорядкування множини об'єктів в порівняно однорідні групи. Винайдений в 1950-х роках математиком Гуґо Штейнгаузом і майже одночасно Стюартом Ллойдом. Особливу популярність отримав після виходу роботи Маккуїна.

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

,

де d - метрика,  - і-ий об'єкт даних, а  - центр кластера, якому на j-ій ітерації приписаний елемент .

Термін «k-середніх» був уперше вжитий Джеймсом МакКвіном (англ. James MacQueen) у 1967 році, хоча ідею методу вперше озвучив Гуґо Штейнгауз (англ. Hugo Steinhaus) у 1957 році. Стандартний алгоритм був вперше запропонований Стюартом Лойдом (англ. Stuart Lloyd) у 1957 р.

Опис алгоритму

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

1.      Дослідник визначає кількість кластерів, що необхідно утворити

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

.        Кожне спостереження «приписується» до одного з n кластерів - того, відстань до якого найкоротша

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

.        Відбувається така кількість ітерацій (повторюються кроки 3-4), поки кластерні центри стануть стійкими (тобто при кожній ітерації в кожному кластері опинятимуться одні й ті самі об'єкти), дисперсія всередині кластера буде мінімізована, а між кластерами - максимізована

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

Принцип дії

Принцип алгоритму полягає в пошуку таких центрів кластерів та наборів елементів кожного кластера при наявності деякої функції Ф(°), що виражає якість поточного розбиття множини на k кластерів, коли сумарне квадратичне відхилення елементів кластерів від центрів цих кластерів буде найменшим:

де  - число кластерів,  - отримані кластери, ,  - центри мас векторів .

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

Алгоритм методу «Кластеризація за схемою к-середніх»:

·              вибрати k інформаційних точок в якості центрів кластерів поки не завершиться процес зміни центрів кластерів;

·              зіставити кожну інформаційну точку з кластером, відстань до центра якого мінімальна;

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

·              центр кожного кластера замінити середнім від елементів кластера;

·              кінець.

Переваги

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

Недоліки

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

Незважаючи на очевидні переваги методу, він має суттєві недоліки:

1.      Результат класифікації сильно залежить від випадкових початкових позицій кластерних центрів

2.      Алгоритм чутливий до викидів, які можуть викривлювати середнє

.        Кількість кластерів повинна бути заздалегідь визначена дослідником

Застосування

Метод k-середніх є доволі простим і прозорим, тому успішно використовується у різноманітних сферах - маркетингових сегментаціях, геостатистиці, астрономії, сільському господарстві тощо.

1.2 Метод деревовидної кластеризації

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

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

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

Евклідова відстань. Це, мабуть, найбільш загальний тип відстані. Вона просто є геометричною відстанню в багатовимірному просторі і обчислюється таким чином:

відстань (х, у) = {_i (x_i - y_i)²}^1/2

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

Відстань Чебишева. Це відстань може виявитися корисним, коли бажають визначити два об'єкти як «різні», якщо вони розрізняються за якоюсь однією координатою (будь-яким одним виміром). Відстань Чебишева обчислюється за формулою:

відстань (х, у) = Максимум |x_i - y_i|

Правила об'єднання або зв'язку

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

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

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

2. Опис логічної структури

2.1 Алгоритм програми

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

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

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

Алгоритм нашої програми виглядає наступним чином:

.        Початок роботи програми. Запуск скомпільованого нами файлу.

.        Ініціалізація об’єктів програми.

.        Задання розмірів матриці

.        Кластеризація

.        Виведення результатів

Для кращого розуміння алгоритму програми складемо його блок-схему (див. рис. 3.1.1)

.

Рис. 2.1.1. Блок-схема програми кластеризації методом к-середніх

Рис. 2.1.2. Блок-схема програми кластеризації методом деревовидної кластеризації

2.2 Методи та елементи, що використовуються