金曉民, 張麗萍

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

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

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

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

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

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

(1)

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

(2)

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

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

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

(3)

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

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

(4)

(5)

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

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

2 算法設(shè)計

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

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

(8)

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

(9)

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

(10)

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

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

2.2 算法描述

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

(11)

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

(12)

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

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

(13)

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

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

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

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

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

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

圖3 不同算法的數(shù)據(jù)點距離計算數(shù)比較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時, 本文提出的算法在時間效率上優(yōu)于傳統(tǒng)的MFA挖掘算法.

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

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

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

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