基于最小生成樹的多層次k-Means聚類算法及其在數據挖掘中的應用

金曉民, 張麗萍

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

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

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

1 數據類型與聚類準則函數設計

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

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

(1)

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

(2)

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

1.2 聚類準則和加權平均平方距離計算函數設計

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

(3)

其中：mj表示數據樣本在類中的均值；JC表示準則函數, 是聚類中心和樣本的函數,JC值越大, 表示聚類過程中存在的誤差越大, 得到的聚類結果較差.

2) 加權平均平方距離計算. 數據聚類過程中的加權平均平方距離和準則的表達式為

(4)

(5)

用數據的類間距離和準則Jb2及類間距離和準則Jb1對聚類結果類間存在的距離分布狀態進行描述,Jb1和Jb2的計算公式為

其中：mj表示樣本在數據類別中的均值向量;m表示數據樣本全部的均值向量; pj表示數據類別的先驗概率[11].

2 算法設計

2.1 基于最小生成樹的初始中心點選取

各矩形單元中存在的數據對象個數用最小生成樹分割, 計算公式為

(8)

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

(9)

其中: S表示數據對象在矩形單元中的線性和; W表示矩形單元權重. 數據對象在各矩形單元中密集程度的計算公式為

(10)

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

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

2.2 算法描述

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

(11)

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

(12)

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

1) 通過k個中心點集C={C1,C2,…,Ck}構建最小生成樹.

(13)

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

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

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

3 算法應用

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

由圖2可見: 采用基于最小生成樹的多層次k-means聚類算法對數據進行聚類時, 可準確地對不同類別的數據進行劃分; 采用傳統k-means算法對數據進行聚類時, 得到的分類中存在不同類別的數據, 聚類結果不準確. 因此, 基于最小生成樹的多層次k-means聚類算法可準確地對數據進行挖掘.

實驗2在k-means算法中, k值決定在該聚類算法中所要分配聚類簇的多少, 同時影響算法的聚類效果和迭代次數, 因此利用Canopy算法先進行粗略的聚類, 產生簇的個數為6, 即k-means算法的k=6.

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

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

圖3 不同算法的數據點距離計算數比較Fig.3 Comparison of calculation number of data points distance of different algorithms

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

由以上分析可知, 當k=6時, 本文提出的算法在時間效率上優于傳統的MFA挖掘算法.

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

實驗3選擇初始點和聚類迭代次數在數據挖掘中均較耗時的兩個階段, 分別采用基于最小生成樹的多層次k-means聚類算法、 文獻[9]算法及傳統MFA算法對數據進行挖掘, 對比不同算法進行數據挖掘的效率, 結果如圖5所示.

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

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