Кластеризація методом к–середніх

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2

де k — число кластерів, S_i — отримані кластери, i = 1, 2, \dots, k, \mu_i — центри мас векторів x_j \in S_i.

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

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

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

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

Примітки[ред.ред. код]

  1. Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
  2. Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
  3. MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.

Див. також[ред.ред. код]

Посилання[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.