基于最小生成樹的多層次k-Means聚類算法及其在數(shù)據(jù)挖掘中的應(yīng)用

金曉民, 張麗萍

(1. 內(nèi)蒙古大學(xué) 交通學(xué)院, 呼和浩特 010021;2. 內(nèi)蒙古自治區(qū)橋梁檢測與維修加固工程技術(shù)研究中心, 呼和浩特 010070;3. 內(nèi)蒙古師范大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 呼和浩特 010022)

數(shù)據(jù)挖掘就是從大量隨機(jī)的、 模糊的、 有噪聲的、 不完全的數(shù)據(jù)中, 提取潛在的、 未知的、 隱含的、 有應(yīng)用價(jià)值的模式或信息的過程[1-3]. 數(shù)據(jù)挖掘中重要的步驟是聚類[4], 聚類將數(shù)據(jù)分為多個(gè)簇或類, 使相似度較高的對象在一個(gè)類中, 不同類別中的數(shù)據(jù)相似度較低[5]. 對稀疏和密集區(qū)域的識(shí)別通過聚類完成, 并通過聚類發(fā)現(xiàn)數(shù)據(jù)屬性和分布模式間存在的關(guān)系[6]. 數(shù)據(jù)聚類廣泛應(yīng)用于醫(yī)療圖像自動(dòng)檢測、 客戶分類、 衛(wèi)星照片分析、 基因識(shí)別、 空間數(shù)據(jù)處理和文本分類等領(lǐng)域[7].

在低維情況下, 數(shù)據(jù)挖掘方法通過人眼進(jìn)行模式識(shí)別及SOM(self organizing maps)可視化功能確定聚類的數(shù)目, 完成數(shù)據(jù)的挖掘, 該方法存在挖掘時(shí)間長和挖掘結(jié)果不準(zhǔn)確的問題[8]. Means算法是數(shù)據(jù)聚類分析中常用的劃分方法, 以準(zhǔn)則函數(shù)和誤差平方作為數(shù)據(jù)聚類的準(zhǔn)則, 可快速、 有效地完成大數(shù)據(jù)集的處理. MFA算法是一個(gè)優(yōu)先考慮邊權(quán)值進(jìn)行社團(tuán)劃分的算法, 同時(shí)也繼承了通過優(yōu)化Q值進(jìn)行社團(tuán)劃分的特點(diǎn). 文獻(xiàn)[9]提出了一種基于改進(jìn)并行協(xié)同過濾算法的大數(shù)據(jù)挖掘方法, 通過分析協(xié)同過濾算法的執(zhí)行流程, 針對傳統(tǒng)協(xié)同過濾算法的不足, 從生成節(jié)點(diǎn)評分向量、 獲取相鄰節(jié)點(diǎn)、 形成推薦信息等方面對傳統(tǒng)協(xié)同過濾算法進(jìn)行改進(jìn), 得到了從運(yùn)行時(shí)間、 加速率和推薦精度三方面均運(yùn)行效率較高的改進(jìn)并行協(xié)同過濾算法.k-means算法依賴于數(shù)據(jù)輸入的順序和初始值的選擇, 通過準(zhǔn)則函數(shù)和誤差平方對聚類效果進(jìn)行測度, 各類的大小和形狀差別較大[10]. 為了優(yōu)化挖掘過程, 本文提出一種基于最小生成樹的多層次k-means聚類算法對數(shù)據(jù)進(jìn)行挖掘.

1 數(shù)據(jù)類型與聚類準(zhǔn)則函數(shù)設(shè)計(jì)

1.1 聚類分析中的矩陣類型選取

1) 數(shù)據(jù)矩陣. 數(shù)據(jù)矩陣表示一個(gè)對象的屬性結(jié)果, 是數(shù)據(jù)之間的關(guān)系表, 每列都表示對象的一類屬性, 每行表示數(shù)據(jù)對象, 如通過m個(gè)屬性對數(shù)據(jù)對象進(jìn)行描述, 屬性一般為種類、 高度等.n個(gè)對象中存在m個(gè)屬性可通過n×m矩陣表示為

(1)

2) 差異矩陣. 數(shù)據(jù)對象之間的差異性用差異矩陣進(jìn)行儲(chǔ)存, 差異矩陣用n×n維矩陣表示, 其中d(i,j)為差異矩陣中的元素, 表示數(shù)據(jù)對象i和j之間存在的差異程度, 表達(dá)式為

(2)

差異矩陣中的元素d(i,j)≥0, 數(shù)據(jù)對象間的相似度越高, 該數(shù)據(jù)越接近于0； 數(shù)據(jù)對象之間的相似度越低, 該數(shù)據(jù)越大.

1.2 聚類準(zhǔn)則和加權(quán)平均平方距離計(jì)算函數(shù)設(shè)計(jì)

1) 誤差平方和準(zhǔn)則函數(shù)設(shè)計(jì). 設(shè)X={x1,x2,…,xn}表示混合樣本集, 通過相似性度量將混合樣本集聚類成C個(gè)子集X1,X2,…,XC, 每個(gè)子集都表示一個(gè)數(shù)據(jù)的類型, 分別存在n1,n2,…,nC種樣本. 采用準(zhǔn)則函數(shù)和誤差平方對數(shù)據(jù)聚類的質(zhì)量進(jìn)行衡量, 表達(dá)式為

(3)

其中：mj表示數(shù)據(jù)樣本在類中的均值；JC表示準(zhǔn)則函數(shù), 是聚類中心和樣本的函數(shù),JC值越大, 表示聚類過程中存在的誤差越大, 得到的聚類結(jié)果較差.

2) 加權(quán)平均平方距離計(jì)算. 數(shù)據(jù)聚類過程中的加權(quán)平均平方距離和準(zhǔn)則的表達(dá)式為

(4)

(5)

用數(shù)據(jù)的類間距離和準(zhǔn)則Jb2及類間距離和準(zhǔn)則Jb1對聚類結(jié)果類間存在的距離分布狀態(tài)進(jìn)行描述,Jb1和Jb2的計(jì)算公式為

其中：mj表示樣本在數(shù)據(jù)類別中的均值向量;m表示數(shù)據(jù)樣本全部的均值向量; pj表示數(shù)據(jù)類別的先驗(yàn)概率[11].

2 算法設(shè)計(jì)

2.1 基于最小生成樹的初始中心點(diǎn)選取

各矩形單元中存在的數(shù)據(jù)對象個(gè)數(shù)用最小生成樹分割, 計(jì)算公式為

(8)

其中：RecU表示矩形單元;DataN表示樣本數(shù)據(jù)的總數(shù); SF表示細(xì)分因子; k表示聚類數(shù). 最小生成樹分割得到的矩形單元均值計(jì)算公式為

(9)

其中: S表示數(shù)據(jù)對象在矩形單元中的線性和; W表示矩形單元權(quán)重. 數(shù)據(jù)對象在各矩形單元中密集程度的計(jì)算公式為

(10)

其中： vi表示每個(gè)矩形單元的面積; ni表示數(shù)據(jù)對象在每個(gè)矩形單元中的數(shù)量; dmin和dmax分別表示矩陣單元中最小數(shù)據(jù)和最大數(shù)據(jù)的距離值.

用最小生成樹對樣本數(shù)據(jù)X={x1,x2,…,xn}進(jìn)行劃分,CenterRecU表示分割后得到的矩形單元RecU, 其反映了樣本數(shù)據(jù)集的分布狀況. 采用數(shù)據(jù)集X′對集合CenterRecU進(jìn)行表示, 用矩形單元密度對數(shù)據(jù)集X′進(jìn)行降序排序, 初始聚類中心在數(shù)據(jù)集X′中選取, 記C={C1,C2,…,Ck}, 用矩形單元中心對數(shù)據(jù)集X′進(jìn)行聚類, 得到k個(gè)類, 原始樣本數(shù)據(jù)集的初始中心點(diǎn)通過在矩形單元中進(jìn)行操作獲得[12].

2.2 算法描述

設(shè)X1和X2表示樣本的數(shù)據(jù)集,Dist(Ci,Cj)表示樣本簇與樣本簇之間的距離, 函數(shù)Dist(Ci,Cj)的表達(dá)式為

(11)

其中： Ci和Cj分別表示含有xi和xj的兩個(gè)不同聚類簇； xi和xj分別表示數(shù)據(jù)集Xi和Xj中的樣本點(diǎn)； 用歐氏距離計(jì)算函數(shù)Dist(xi,xj)中數(shù)據(jù)間的距離； n1和n2表示數(shù)據(jù)對象在兩個(gè)樣本簇中的個(gè)數(shù). 平均簇間距定義為

(12)

其中, Ci和Cj表示兩個(gè)不同的聚類簇. 如果AvgDist(C)大于兩個(gè)簇間的距離, 則不處理這兩個(gè)簇, 繼續(xù)比較, 直到AvgDist(C)小于兩個(gè)簇之間的距離為止. 算法步驟如下：

1) 通過k個(gè)中心點(diǎn)集C={C1,C2,…,Ck}構(gòu)建最小生成樹.

(13)

6) 用式(12)比較k個(gè)聚類簇之間的距離, 如果平均簇間距AvgDist(C)大于兩個(gè)簇之間的距離, 則對兩個(gè)簇進(jìn)行合并, 直到平均簇間距AvgDist(C)小于兩個(gè)簇之間的距離為止. 用最小生成樹得到的增量數(shù)據(jù)與初始聚類中心建立最小生成樹, 用最近鄰搜索方法將增量數(shù)據(jù)依次劃分到相應(yīng)的聚類中, 完成數(shù)據(jù)的聚類, 并根據(jù)類間的平均距離對聚類結(jié)果進(jìn)行完善和修正, 獲得最優(yōu)的聚類結(jié)果, 完成數(shù)據(jù)挖掘.

基于最小生成樹的多層次k-means聚類算法流程如圖1所示.

圖1 多層次k-means聚類算法流程Fig.1 Flow chart of multi-level k-means clustering algorithm

3 算法應(yīng)用

實(shí)驗(yàn)1為了驗(yàn)證基于最小生成樹的多層次k-means聚類算法對數(shù)據(jù)挖掘的有效性, 下面對該算法進(jìn)行測試, 操作系統(tǒng)為Windows7.0. 基于聚類結(jié)果越精準(zhǔn)得到的數(shù)據(jù)挖掘結(jié)果越準(zhǔn)確的原則, 分別采用基于最小生成樹的多層次k-means聚類算法與傳統(tǒng)k-means算法進(jìn)行測試, 對比兩種不同算法對數(shù)據(jù)挖掘過程中的聚類結(jié)果, 測試結(jié)果如圖2所示, 圖2中不同形狀表示不同類別的數(shù)據(jù).

由圖2可見: 采用基于最小生成樹的多層次k-means聚類算法對數(shù)據(jù)進(jìn)行聚類時(shí), 可準(zhǔn)確地對不同類別的數(shù)據(jù)進(jìn)行劃分; 采用傳統(tǒng)k-means算法對數(shù)據(jù)進(jìn)行聚類時(shí), 得到的分類中存在不同類別的數(shù)據(jù), 聚類結(jié)果不準(zhǔn)確. 因此, 基于最小生成樹的多層次k-means聚類算法可準(zhǔn)確地對數(shù)據(jù)進(jìn)行挖掘.

實(shí)驗(yàn)2在k-means算法中, k值決定在該聚類算法中所要分配聚類簇的多少, 同時(shí)影響算法的聚類效果和迭代次數(shù), 因此利用Canopy算法先進(jìn)行粗略的聚類, 產(chǎn)生簇的個(gè)數(shù)為6, 即k-means算法的k=6.

圖2 兩種不同算法的聚類結(jié)果Fig.2 Clustering results of two different algorithms

在k=6的條件下, 為進(jìn)一步驗(yàn)證本文算法的優(yōu)越性, 在分類簇的劃分過程中, 可用挖掘數(shù)據(jù)對象到簇中心的距離衡量算法的優(yōu)劣. 聚類過程中, 距離計(jì)算次數(shù)能很好地衡量挖掘算法的相關(guān)性能. 通過對本文改進(jìn)k-means算法和傳統(tǒng)的MFA算法的距離計(jì)算次數(shù)進(jìn)行比較, 完成性能對比, 對比結(jié)果如圖3所示. 由圖3可見, 本文提出的改進(jìn)k-means算法得到的距離計(jì)算次數(shù)比傳統(tǒng)MFA算法少, 隨著計(jì)算挖掘控制維度的不斷增加, 這種優(yōu)勢對比越來越明顯. 與MFA算法相比, 在數(shù)據(jù)維度不斷增加的集合中, 本文算法的效率提升約50%. 利用本文提出的改進(jìn)k-means算法和MFA算法在運(yùn)行實(shí)際效率上進(jìn)行實(shí)驗(yàn)對比, 結(jié)果如圖4所示. 由圖4可見, 本文算法在每次迭代過程中, 在時(shí)間效率上都優(yōu)于傳統(tǒng)MFA算法, 且維度越大, 效果越明顯.

圖3 不同算法的數(shù)據(jù)點(diǎn)距離計(jì)算數(shù)比較Fig.3 Comparison of calculation number of data points distance of different algorithms

圖4 不同算法迭代階段的運(yùn)行時(shí)間比較Fig.4 Comparison of running time of different algorithms in iterative stages

由以上分析可知, 當(dāng)k=6時(shí), 本文提出的算法在時(shí)間效率上優(yōu)于傳統(tǒng)的MFA挖掘算法.

圖5 不同算法的效率測試結(jié)果比較Fig.5 Comparison of efficiency test results of different algorithms

實(shí)驗(yàn)3選擇初始點(diǎn)和聚類迭代次數(shù)在數(shù)據(jù)挖掘中均較耗時(shí)的兩個(gè)階段, 分別采用基于最小生成樹的多層次k-means聚類算法、 文獻(xiàn)[9]算法及傳統(tǒng)MFA算法對數(shù)據(jù)進(jìn)行挖掘, 對比不同算法進(jìn)行數(shù)據(jù)挖掘的效率, 結(jié)果如圖5所示.

由圖5可見, 采用基于最小生成樹的多層次k-means聚類算法對數(shù)據(jù)進(jìn)行挖掘時(shí), 在選擇初始點(diǎn)階段的迭代次數(shù)較多, 在聚類階段中的迭代次數(shù)較低. 采用其他算法對數(shù)據(jù)進(jìn)行挖掘時(shí), 在選擇初始點(diǎn)階段的迭代次數(shù)較少, 但在聚類階段中的迭代次數(shù)較多. 對比基于最小生成樹的多層次k-means聚類算法其他和算法的迭代次數(shù)可知, 基于最小生成樹的多層次k-means聚類算法的總體迭代次數(shù)少于其他算法的總體迭代次數(shù), 因此基于最小生成樹的多層次k-means聚類算法對數(shù)據(jù)進(jìn)行挖掘時(shí)迭代次數(shù)較少, 挖掘所用時(shí)間較短.

綜上可見, 針對傳統(tǒng)聚類算法挖掘數(shù)據(jù)時(shí), 存在挖掘結(jié)果不準(zhǔn)確、 挖掘時(shí)間長的問題, 本文提出了一種基于最小生成樹的多層次k-means聚類算法, 解決了目前數(shù)據(jù)挖掘效率低的問題, 可有效提高信息檢索率.