二、基于劃分的K-means聚類算法簡介
随着資訊技術的快速發展及廣泛推進,資料挖掘成為當今社會研究的一個熱點領域,聚類分析是資料挖掘中的一項核心技術,它通過研究資料的分布特征來發現資料背後隐藏的事物内部規律。聚類算法有很多種,每一種算法都有自己的獨特之處。K-means算法是聚類分析的經典算法之一,文中主要對K-means算法進行闡述。
1 聚類分析概述
聚類分析是人的一項重要活動,比如,小孩子通過不斷學習都能夠區分動物和植物,也能夠區分雞和狗。聚類與分類不同,分類是按照一定的标準把資料分成不同的類别,聚類是通過觀察資料的特征尋找這個标準。
聚類分析的核心是聚類,即将實體或抽象對象的集合分成相似的對象類的過程。通過聚類把資料分成不同的集合,同一個集合中的資料對象彼此相似,不同資料集合的對象之間彼此相異。形成聚類的原則是使類内部的相似性最大,類間的相似性最小。聚類的研究方法有很多,用的比較多的是K-means(K-平均值)、BIRCH算法、clara算法、eLIQuE算法、chameleon(變色龍)算法等。
聚類可以對迅猛增長的資料加以組織,人們通過聚類可以發現一些資料分布的特征,是以成為比較活躍的研究課題。目前,很多領域已經成功地應用了該項技術,包括市場研究、人工智能和圖像處理、生物學、資料壓縮等領域[2]。例如,在生物學領域,聚類可以自動對物種分類,依據是物種特征;還可以更好地了解生物學中基因的功能。在商業中,市場分析員通過聚類分析可以很容易發現顧客庫中不同的顧客群。聚類還可以應用于客戶關系管理,對從接觸點收集到的資料進行分析,可以得出有價值的知識,以便用于改進營銷方案、制定定價和促銷政策。
2 K-means算法
2.1 K-means算法基本思想
K-means算法,也被稱為K-均值,是最常用、最著名的一種聚類算法。K-means算法是把n個對象分成K個簇,用簇中對象的均值表示每個簇的質心,通過疊代使每個簇内的對象不再發生變化為止。這時準則函數達到最優,每個簇内相似度高,簇間相似度低。其過程描述如下:
(1)首先,随機地選擇K個對象,代表要分成的K個簇的初始均值或中心。
(2)計算其餘對象與各個均值的距離,然後把它們分别劃分到距離中心最近的簇中。
(3)計算每個簇中所有對象的平均值,作為每個新的簇中心
(4)計算所有對象與新的K個中心的距離,根據“距離中心最近”原則,重新劃分所有對象到各個簇中
(5)重複(3)、(4),直至所有簇中心不變為止。
2.2 K-means算法劃分聚類的三個關鍵點
(1)資料對象的劃分
(1)距離度量的選擇
K-means算法比較适合處理連續型屬性,對離散型屬性不适合。在計算資料對象之間的距離時要選擇合适的相似性度量。比較著名的距離度量是歐幾裡得距離和曼哈頓距離[3],其中最常用的是歐幾裡得距離,其公式如下:
這裡xi,xj表示兩個d維資料對象,xi=(xi1,xi2,…,xid),xj=(xj1,xj2,…,xjd),d(xi,xj)表示對象xi和xj之間的距離,距離越小,二者越相似;距離越大,二者差異就越大。
根據歐幾裡得距離,計算出每一個資料對象與各個簇中心的距離。
(2)選擇最小距離,即如果
那麼,p∈ci;P表示給定的資料對象;m1,m2,…,mk分别表示簇c1,c2,…,ck的初始均值或中心;(2)準則函數的選擇。K-means算法采用平方誤差準則函數來評價聚類性能,其公式如下:
E表示資料庫中所有對象的平方誤差和,P表示給定的資料對象,mi表示簇ci的均值。(3)簇中心的計算。用每一簇的平均值作為計算相似度簇中心的依據,其公式如下:
這裡假設簇c1,c2,…,ck中的資料對象個數分别為n1,n2,…,nk。
2.3 K-means算法的實作
(1)劃分資料對象。選擇k個資料對象作為初始k個聚類的中心,根據歐幾裡得距離公式,依次比較每個資料對象與各個中心的距離,選擇距離中心最近的簇,依次把n個對象劃分到k個簇中[4]。完成第一次劃分之後,重新計算新的簇的中心,然後開始重新劃分資料對象,直到新的簇中心不再發生變化,停止疊代。
(2)計算簇中心。每次劃分資料對象之後,都要重新計算簇中心,直到簇中心不再發生變化為止。
三、部分源代碼
;
close all;
clc;
%第一類資料
mu1=[10 3 3]; %均值
S1=[0.3 0 0;0 0.35 0;0 0 0.3]; %協方差
data1=mvnrnd(mu1,S1,100); %産生高斯分布資料
%%第二類資料
mu2=[5 10 5];
S2=[0.3 0 0;0 0.35 0;0 0 0.3];
data2=mvnrnd(mu2,S2,150);
mu3=[10 10 10];
S3=[0.3 0 0;0 0.35 0;0 0 0.3];
data3=mvnrnd(mu3,S3,200);
%第三個類資料
mu4=[15 15 15];
S4=[0.3 0 0;0 0.35 0;0 0 0.3];
data4=mvnrnd(mu4,S4,50);
data=[data1;data2;data3;data4]; %這裡的data是不帶标号的
plot3(data(:,1),data(:,2),data(:,3),'+')
grid on;
hold on;
k=7;
r=10;
p=2;
for i=k:-1:2
if p == 0
break;
end
k=i
[resX resY resZ seedX seedY seedZ record] = FunK_mean3D(data(:,1),data(:,2),data(:,3),k,r);
% 下面是标記出每一個類别的類别代表點
for j=k:-1:2
p=0;
j
for m=j-1:-1:1
m
power(seedX(m)-seedX(j),2)+power(seedY(m)-seedY(j),2)+power(seedZ(m)-seedZ(j),2)
if (power(seedX(m)-seedX(j),2)+power(seedY(m)-seedY(j),2)+power(seedZ(m)-seedZ(j),2))<r
p=1
break;
end
end
p
if p==1
break; 四、運作結果
五、matlab版本及參考文獻
1 matlab版本
2014a