聚類算法—k-Means實(shí)驗(yàn)

k-平均（k-Means），也被稱為k-均值，是一種得到最廣泛使用的聚類算法[1]. k-Means算法以k為參數(shù)，把n個(gè)對(duì)象分為k個(gè)簇，使得簇內(nèi)具有較高的相似度。

實(shí)驗(yàn)?zāi)康?/h2>

了解常用聚類算法及其優(yōu)缺點(diǎn)；

掌握k-Means聚類算法對(duì)數(shù)據(jù)進(jìn)行聚類分析的基本原理和劃分方法；

利用k-Means聚類算法對(duì)數(shù)據(jù)集進(jìn)行聚類實(shí)驗(yàn)；

熟悉使用Matlab進(jìn)行算法的實(shí)現(xiàn)。

聚類算法的主要思想

主要思想

給定一個(gè)有n個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，$k\le n$. 每一個(gè)簇至少包含一個(gè)對(duì)象，每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。

對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法，以后通過反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分較前一次更好。

評(píng)價(jià)函數(shù)

更好的標(biāo)準(zhǔn)是：同一簇中的對(duì)象越接近越好，而不同簇中的對(duì)象越遠(yuǎn)越好，目標(biāo)是最小化所有對(duì)象與其簇中心之間相異度之和。

各個(gè)簇應(yīng)該是緊湊的，各個(gè)簇間的距離應(yīng)當(dāng)盡可能遠(yuǎn)。因此，用聚類C的類內(nèi)差異（Within cluster variation）$w(C)$ 和類間差異（Between cluster variation）$b(C)$ 分別衡量上述兩要求。

$$w(C)=\sum _{i=1}^{k}w(C_i)=\sum _{i=1}^k\sum _{x\in C_i}d(x,\overline{x_i}{)}^2$$

$$b(C)=\sum _{1\le j\le i\le k}d(\overline{x_j},\overline{x_i}{)}^2$$

其中，$\overline{x_i}$ 是類 $C_i$ 的聚類中心，d 為距離函數(shù)。聚類C的總體質(zhì)量可以被定義為 $\frac{b(C)}{w(C)}$.

k-Means算法原理

k-Means算法用類內(nèi)均值作為聚類中心、用歐氏距離定義d，并使上述 $w(C)$ 最小化。

優(yōu)化目標(biāo)

$$\underset{C}{\mathrm{argmax}}\sum _{i=1}^k\sum _{x\in C_i}\parallel x?\overline{x_i}{\parallel }^2$$

表示選取合適的C使得所有對(duì)象的平方誤差總和最小，其中x是空間中的點(diǎn)，$\overline{x_i}$ 是簇 $C_i$ 的平均值，這個(gè)優(yōu)化目標(biāo)可以保證生成的結(jié)果簇盡可能的緊湊和獨(dú)立。

算法描述

首先隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心。對(duì)剩余的每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過程不斷重復(fù)，直到上述平方誤差總和收斂。

k-Means算法分析

優(yōu)點(diǎn)

• 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的，時(shí)間復(fù)雜度約為 $\mathcal{O}(k?n?t)$，t是迭代次數(shù)。k-Means算法經(jīng)常以局部最優(yōu)結(jié)束；
• 算法嘗試找出使平方誤差最小的k個(gè)劃分，當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，k-Means的效果較好。

缺點(diǎn)

• 若涉及離散屬性，其平均值無法定義，無法使用k-Means聚類；
• 必須事先給出參數(shù)k，k的選取對(duì)聚類質(zhì)量和效果影響很大；
• k-Means算法不適合發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。而且對(duì)于“噪聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)對(duì)平均值產(chǎn)生較大影響。

算法改進(jìn)

k-模算法：將k-Means的應(yīng)用擴(kuò)大到離散數(shù)據(jù)。k-原型可以對(duì)離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k-原型中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。[2]

k-中心點(diǎn)算法：解決了k-Means算法對(duì)孤立點(diǎn)敏感的問題，不采用簇中的平均值作為參照點(diǎn)，而使用簇中位置最靠近中心的對(duì)象作為參照點(diǎn)?；舅悸肥欠磸?fù)用非代表對(duì)象來替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量。PAM（Partition Around Medoid）是最早提出的k-中心點(diǎn)算法之一。[3]

代碼

clc;clear; k = 2; data = [1 1; 2 1; 1 2; 2 2; 4 3; 5 3; 4 4; 5 4;]; eps = 0.1; epochs = 100; [n,~] = size(data); % initialize the last column of data as classes data(:,end+1) = 0; % assign initial value for means rng('default') % For reproducibility clusters = data(randperm(n,k),1:end-1); % initialize E E = inf; % save means steps cnt = 0; % counter cls_steps = []; while epochs>0% to save means stepscnt = cnt + 1;cT = clusters';cls_steps(cnt,:) = cT(:)';% assign each xj to the cluster which has the closet meanD = pdist2(data(:,1:end-1),clusters);[~,I] = min(D');data(:,end) = I';% calculate new means for each classesclusters = grpstats(data(:,1:end-1),data(:,end));% calculate criterion function ElastE = E;E = .0;for i=1:nE = E + pdist2(data(i,1:end-1),clusters(data(i,end),:));endif lastE-E<=epsbreakendepochs = epochs - 1; end

Matlab2021a

結(jié)果驗(yàn)證

結(jié)果數(shù)據(jù)

在data.csv數(shù)據(jù)集上運(yùn)行上述代碼，得到結(jié)果如下：

Clusters: 聚類中心

x1x2

1.5	1.5
4.5	3.5

E = 5.65685424949238

cls_steps: 聚類中心移動(dòng)記錄

c1x1c1x2c2x1c2x2

4	3	5	3
2.33333333	2.16666667	5	3.5
1.5	1.5	4.5	3.5

結(jié)果圖像

其中，藍(lán)色/黃色實(shí)心點(diǎn)表示不同分類下的數(shù)據(jù)點(diǎn)，空心橙色/紫色圓環(huán)表示k-Means聚類中心的變化情況。

附錄（data.csv）

IndexAttr1Attr2

1	1	1
2	2	1
3	1	2
4	2	2
5	4	3
6	5	3
7	4	4
8	5	4

參考

毛國(guó)君、段立娟, 《數(shù)據(jù)挖掘原理與算法》, 清華大學(xué)出版社, 2016-01-01, ISBN：9787302415817

Ramasubramanian P , Kumar S P , Anandam D . Experimental work on Data Clustering using Enhanced Random KMode Algorithm. 2020.

Bhat A . K-Medoids Clustering Using Partitioning Around Medoids for Performing Face Recognition. 2014.

總結(jié)

以上是生活随笔為你收集整理的k-Means——经典聚类算法实验（Matlab实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。