Привітання та дуже загальний вступ

Привіт. Мене звати Андрій Будай і сьогодні я вестиму цю пару, темою якої є k-means алгорим. Some parts will be in English, so please do not scare if I switch to English unexpectedly, like I just did.

As you all know we are talking about the clustering of data. Human brains are very good at finding similarity in things. For example, biologists have discovered that things belong to one of two types: things are either brown and run away or things are green and don’t run away. The first group they call animals, and the second is plants.
Процес групування речей по певних ознаках ми називаємо кластеризацією. Якщо ми говоримо про то, що біологи почали поділяти тварин на ряди, роди та види, то ми говоримо про ієрархічну класифікацію. Яку я передбачаю ви вже розглянули, зоокрема підхід ієрархічної кластиризації згори-вниз та знизу-вгору.

Розуміння Partitioning алгоритмів

А що якщо ми хочемо групувати дані не в порядку збільшення або зменшення об”єму груп, якщо ми хочемо погрупувати N векторів даних на K кластерів за один логічний хід? Такий різновид кластерізації називається Partitioning алгоритмами. Іншими словами ми розбиваємо множину.

Ще раз нагадаємо що таке розбиття множини:

Система множин S={X1 … Xn} називається розбиттям множини M, якщо ця система задовольняє наступним умовам:

  • будь-яка множина Xk з S є підмножиною множини M:
∀X∈S: X⊆M
  • будь-які дві множини Xi, Xj з S мають порожній перетин:
∀Xi, Xj ∈ S: Xi≠Xj→Xi∩Xj = ∅.
  • об’єднання всіх множин, які входять в розбиття M, дає множину M:
bigcup_{X in S} X = M

Partitioning алгоритми розбивають множину на певну кількість груп за один крок, проте результати покращуються із процесом ітерування. До найвідоміших partitioning алгоритмів відносяться k-means та його модифікації із доповненнями, quality threshold алгоритм також для кластеризації можуть бути використані Locality-sensitive hashing та Graph-theoretic methods. Якщо буде час то ми поговорими і про них також.

K-means алгоритм

Отже, k-means. Насправді алгорим не є складним і я сподіваюся що всі із вас будуть розуміти суть алгоритму та будуть мати палке бажання його реалізувати. Це моя мета на сьогоднішню пару. []

Завданням алгоритму є здійснити розбиття N векторів даних на K груп. Причому число k є попередньо відомим – або є вхідним параметром алгоритму як і дані.

Опис
[Цю частину я збираюся продиктувати]

Маючи список даних спостережень (x1, x2, …, xn), де кожен x є вектором розмірності d, k-means кластеризація призначена для розбиття цього списку із n спостережень на k підмножин (k < n), в результаті чого ми повиння отримати таке розбиття S={S1, S2, …, Sk}, в якому внутрішньокластерна сума квадратів норм є мінімізованою:

underset{mathbf{S}} operatorname{arg,min} sum_{i=1}^{k} sum_{mathbf x_j in S_i} left| mathbf x_j - boldsymbolmu_i right|^2

де μi є центром Si.

Кроки алгоритму

Перш за все нам слід мати множину із k центрів m1(1),…,mk(1), які можуть бути визначені або випадковим чином, або евристичним шляхом. Алгоритм складається із двох основних кроків – кроку присвоєння та оновлення.

Ініціалізація: Перш за все нам слід мати множину із k центрів m1(1),…,mk(1),
які можуть бути визначені або випадковим чином, або евристичним шляхом.
Алгоритм складається із двох основних кроків – кроку присвоєння та
оновлення.
Крок присвоєння: Присвоюємо кожен вхідний вектор до кластеру із найближчим центром.

S_i^{(t)} = left{ mathbf x_j : big| mathbf x_j - mathbf m^{(t)}_i big| leq big| mathbf x_j - mathbf m^{(t)}_{i^*} big| text{ for all }i^*=1,ldots,k right}
Крок оновлення: Вираховуємо нові центри, щоб вони найкраще підходили векторам за які вони відповідають.

mathbf m^{(t+1)}_i = frac{1}{|S^{(t)}_i|} sum_{mathbf x_j in S^{(t)}_i} mathbf x_j
Повторюємо кроки присвоєння та оновлення допоки присвоєння ще змінюються.

Демонстрація
[here I’m going to switch to English and demonstrate steps of the algo at board] 

1) k initial “means”
(in this case k=3) are randomly selected from the data set (shown in color).
2) k clusters are created by associating every observation with the nearest mean.
3) The centroid of each of the k clusters becomes the new means.
4) Steps 2 and 3 are repeated until convergence has been reached.

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

Other variations of the K-means algorithm

Because of some disadvantages of standard algorithm we’ve got few
different variations of it like Soft K-means, when data element is
fuzzy associated with mean, or like K-means++, which is additions to
the K-means to initialize cluster means better.

K-means++
With the intuition of spreading the k initial cluster centers away from
each other, the first cluster center is chosen uniformly at random from
the data points that are being clustered, after which each subsequent
cluster center is chosen from the remaining data points with
probability proportional to its distance squared to the point’s closest
cluster center.

Soft K-means алгоритм

В Soft K-means алгоритму кожен вектор має часткову приналежність до якогось кластеру, так як же і в розмитій логіці – існуть не тільки 1 та 0, а ще й 0.667. Таким чином, вектори, що знаходяться ближче до центру кластеру мають більшу приналежність до нього, а ті які знаходяться по краях мають дуже малу приналежність. Отже, для кожного вектора x ми маємо коефіцієнт який відповідає за приналежність до k-того кластеру uk(x). Звичайно, що сума коефіцієнтів для заданого вектора x є рівною 1:

forall x left(sum_{k=1}^{mathrm{num.} mathrm{clusters}} u_k(x) =1right).

Таким чином, центр кластеру вираховується як середнє всіх векторів, домножених на цей коефіцієнт приналежності до кластеру:

mathrm{center}_k = {{sum_x u_k(x)^m x} over {sum_x u_k(x)^m}}.

Коефіцієнт є обернено пропорційний до відстані до центру кластеру:

u_k(x) = {1 over d(mathrm{center}_k,x)},

опісля коефіцієнти нормалізуються із використання параметра m > 1 щоб сума була рівною 1 за такою формулою:

u_k(x) = frac{1}{sum_j left(frac{d(mathrm{center}_k,x)}{d(mathrm{center}_j,x)}right)^{2/(m-1)}}.

Коли m
близьке до 1, кластери ближчі до центру мають більшу приналежність, а ті що дальше мають меншу приналежність. Для m = 2, це відповідає лінійній нормалізації коефіцієнтів, щоб отримати суму 1 і алгоритм подібний до звичайного k-means.

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

  • Вибираємо кількість кластерів.
  • Випадковим чином вибираємо приналежність кожного із векторів до якогось кластеру.
  • Повторюємо наступне допоки алгоритм не збіжиться (це коли зміна коефіцієнтів між ітераціями не перевищує деякого числа varepsilon, що є порогом чутливості) :

    • Вираховуємо центр для кожного кластеру за допомогою формули наведеної вище.
    • Для кожного вектору вираховуємо коефіцієнти приналежності до кластерів.

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

Можливий підхід до реалізації

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

[Не дуже хочу закидати реалізацію, щоб студенти завчасно не використали її]

He-he! I’ve got it in about 3.5 hours.

I would say that core algorithm code looks very good, at least take a look at method Process:

        public void Process()
        {
            Initialize();

            while (!ClustersRemainTheSame())
            {
                AssignStep();
                UpdateStep();
            }
        }
I’ve also used realized algorithm in two applications – one is clusterization of animals by theirs properties and another is graphical demoing usage. Below is nice screenshoot:

Application

[If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.]

“The k-means clustering algorithm is commonly used in computer vision as a form of image segmentation. The results of the segmentation are used to aid border detection and object recognition. In this context, the standard Euclidean distance is usually insufficient in forming the clusters. Instead, a weighted distance measure utilizing pixel coordinates, RGB pixel color and/or intensity, and image texture is commonly used“

One of the application examples is clustering colors in image to compress image. A good article on this is written up here.

Завершення пари

Побажання зробити реалізацію алгоритму

Час на питання

P.S. So far I have some good plan for Friday… not 100% complete, but I’m satisfied with what I have. And tomorrow I’m going to work on this once again. Also not really good that I just translated a lot of stuff from wiki pages.