田 璐,曹付元,余麗琴

(1.山西大學 計算機與信息技術(shù)學院,太原 030006; 2.計算智能與中文信息處理教育部重點實驗室,太原 030006)

0 概述

在數(shù)據(jù)挖掘中,多數(shù)算法的輸入是由n個對象組成的一個集合,每一個對象對應(yīng)一條記錄且被多個屬性所描述[1]。然而在實際應(yīng)用中,一個對象的描述常常不止一條記錄,通常由多條記錄描述的對象稱為矩陣型對象,由矩陣型對象構(gòu)成的數(shù)據(jù)集稱為矩陣數(shù)據(jù)集,即由包含多條記錄的對象組成的數(shù)據(jù)集。例如,在超市購物時,每個用戶購買的商品不僅種類不同,而且在購買同一種商品時,購買的商品數(shù)量和頻率也不相同。通常,可以根據(jù)人們購買一個商品的數(shù)量和頻率來預測該用戶是否喜歡這個商品。因此,矩陣數(shù)據(jù)蘊含了豐富的用戶行為特性,對于行為分析具有重要的價值[2]。

在實際生活中,矩陣數(shù)據(jù)廣泛存在于通信、超市、銀行、保險以及各大電子商務(wù)應(yīng)用領(lǐng)域。為了給用戶提供更好的服務(wù),需要挖掘這種數(shù)據(jù)中潛在的有用信息并加以利用。然而,在實際應(yīng)用中大部分矩陣型數(shù)據(jù)沒有標記,如果給全部數(shù)據(jù)進行標記,需要耗費大量的人力物力,代價昂貴。通過無監(jiān)督學習來對這類型數(shù)據(jù)進行分析是一種最直觀的方法,其中聚類是無監(jiān)督學習中一種最廣泛的應(yīng)用。文獻[3]提出了k-mw-modes聚類算法來處理分類型矩陣數(shù)據(jù),該算法定義了一個新的相似性度量公式來計算兩個分類型矩陣對象之間的距離,并且給出了一種新的啟發(fā)式方法去選擇類中心。但是該算法是在隨機選取初始類中心之后,通過不斷地迭代更新聚類中心實現(xiàn)數(shù)據(jù)的劃分,容易受到不同初始類中心對聚類結(jié)果的影響。為了找到一個更好的解決方案,該類型算法需要多次使用不同的初始類中心來重新運行。此外,隨機初始化類中心的方法只有在類的個數(shù)較少且至少有一個隨機初始化結(jié)果接近于一個好的解決方案時才有效。因此,初始類中心的選擇對劃分聚類算法是非常重要的,有必要發(fā)展一種面向分類型矩陣數(shù)據(jù)的初始類中心選擇算法以獲得更好的聚類效果。

針對分類型矩陣數(shù)據(jù),本文根據(jù)屬性值的頻率定義了矩陣對象的密度和矩陣對象間的距離,擴展了最大最小距離算法,在此基礎(chǔ)上,提出一種面向分類型矩陣數(shù)據(jù)的初始類中心選擇算法(An Initial Cluster Center Selection Algorithm for Categorical Matrix Data,IC2SACMD)。

1 相關(guān)工作

聚類是數(shù)據(jù)挖掘中一個非常重要的研究方向,也是無監(jiān)督學習中使用最廣泛的一種方法[4]。聚類算法是基于數(shù)據(jù)的內(nèi)部結(jié)構(gòu)來尋找觀察樣本的自然集群。在實際應(yīng)用中,聚類算法也是一種尋找不同用戶群最普遍的方法,使用案例主要包括細分客戶、新聞聚類、異常點檢測[5]和網(wǎng)絡(luò)識別等。在k-type聚類算法中,初始類中心的選擇至關(guān)重要。根據(jù)數(shù)據(jù)類型的不同,初始類中心的選擇算法可分為數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)初始類中心選擇算法。針對數(shù)值型數(shù)據(jù),研究人員提出幾種解決初始化類中心問題的方法[6-8]。相應(yīng)地,針對分類型數(shù)據(jù),研究人員提出了多種解決初始類中心的方法[9-11]。最常見的方法是從數(shù)據(jù)集中選擇前k個不同的對象作為初始類中心。為了避免隨機選擇初始類中心對聚類結(jié)果的影響,文獻[9]將由每個屬性下頻率最高的屬性值組成的向量作為初始類中心。雖然文獻[9]提出的方法使初始中心多樣化,但是對于初始k個中心的選擇還沒有給出統(tǒng)一的準則。文獻[10]提出一種基于密度和距離的方法,通過計算對象自身的密度及對象間的距離來選取初始類中心。雖然該方法一定程度上避免了離群點、初始類中心過于密集的問題,但是在計算密度的過程中沒有考慮到不同屬性之間的差異、數(shù)據(jù)對象作為聚類中心的準確性以及第一個類中心的選取可能為全部數(shù)據(jù)集正中間的一個數(shù)據(jù)對象。文獻[11]提出了一種新的初始化類中心的方法,雖然考慮到數(shù)據(jù)對象作為類中心聚類的不精準性,并且避免了第一個類中心可能位于全部數(shù)據(jù)集正中間的一個密度最大值點的情況,但是在計算密度過程中,采用對象間的平均距離作為相似度,該算法也沒有考慮到不同屬性間的差異性。以上初始類中心算法都應(yīng)用于每個對象僅由一個特征向量描述的數(shù)據(jù)集,目前筆者尚未發(fā)現(xiàn)針對分類型矩陣數(shù)據(jù)在選擇初始類中心方面的相關(guān)工作。

2 k-mw-modes算法

k-mw-modes算法是面向分類型矩陣數(shù)據(jù)的k-type聚類算法,主要由3個部分組成:1)聚類中心的表示;2)將對象分配到聚類中;3)更新聚類中心。該算法定義了兩個矩陣對象之間的距離公式,給出一種更新類中心的方法。

2.1 矩陣對象間的距離

給定兩個矩陣對象Xi和Xj,每個對象由m個分類型屬性{A1,A2,…,Am}來描述,則Xi和Xj的距離公式定義為:

(1)

其中:

(2)

2.2 多加權(quán)模式聚類中心

(3)

k-mw-modes算法對分類型矩陣數(shù)據(jù)進行了聚類,但是該算法隨機選取初始類中心,沒有考慮到隨機初始類中心的不穩(wěn)定性以及必須至少存在一種較優(yōu)的初始類中心選擇才會得到有效的聚類結(jié)果。

3 初始類中心選擇算法

目前許多專家學者提出了多種方法來度量數(shù)據(jù)對象間的內(nèi)聚性[10-12]。最常見的一種方法是使用數(shù)據(jù)對象與全部數(shù)據(jù)對象之間的平均距離來測量數(shù)據(jù)對象的密度[12],因為其簡單且沒有參數(shù)。而對于矩陣數(shù)據(jù)集,對象Xi對應(yīng)ri條記錄,并且每個對象在每條屬性上有多個屬性值,即vips表示對象Xi在As屬性上的第p個屬性值,則需要考慮到同一屬性上不同記錄之間的差異性。因此,本文根據(jù)屬性值的頻率來定義對象的平均密度。

3.1 基本定義

(4)

為便于理解,下文給出一個計算矩陣對象的平均密度示例,如表1所示。

表1 矩陣對象的平均密度

根據(jù)式(3)計算出在每個屬性上各個記錄值的權(quán)重。

在A1屬性上:

在A2屬性上:

在A3屬性上:

根據(jù)式(4)計算每個對象的平均密度如下:

DensX(X1)=w(42)+w(-198)+w(-191)+

w(-109)+w(-142)+

w(-110)=2.333 3

DensX(X2)=w(42)+w(-198)+w(-191)+

w(-190)+w(-199)+

w(-142)+w(-102)=2.000 0

DensX(X3)=w(40)+w(42)+w(-191)+

w(-173)+w(-159)+

w(-142)+w(-63)=1.333 5

可得出對象X1的平均密度最大。

定義2給定數(shù)據(jù)對象Xi∈X(Xi≠Xz),Xi作為類中心的代表能力定義為:

Pro_Repre(Xi)=DensX(Xi)×d(Xi,Xz)

(5)

圖1中的數(shù)據(jù)集被分為兩類,Xz為密度最大值對象,其處于兩個類的邊界處,所以不能很好地代表一個類,則需尋找一個自身密度大的對象,且與Xz距離最遠,如圖1中E1,相對于一個虛擬類中心C1,E1并不能充分地表示類簇,因此不將E1作為初始類中心,而應(yīng)該在E1周圍選擇一個合適的虛點C1作為初始類中心。

圖1 E1作為類中心差的情況

本文基于所選的類中心代表能力最強的點E1來構(gòu)造多個候選對象集合,通過每個集合可以得到一個虛點作為候選類中心。下面給出候選對象集合的定義和求取候選類中心的定義。

定義3設(shè)Ca_Sets(1≤s≤m)是第s個候選對象集合,被定義為:

Ca_Sets={Xi∈X|d(Xi,E1)≤s}

(6)

根據(jù)式(3),可以計算出Ca_Sets的類中心cas。令Ca_Cluster1={ca1,ca2,…,cam}。

對于任意的兩個矩陣對象Xi和Xj,滿足0≤δ(Xis,Xjs)≤1,且0≤d(Xi,Xj)≤m。因此,可以根據(jù)對象與E1的距離得到m個候選對象集合,第s個集合Ca_Sets是由與E1的距離小于等于s的對象構(gòu)成的。隨著屬性s的增加,Ca_Sets集合中的對象數(shù)也會逐漸增加。也就是說,cas+1會比cas包含更多的對象信息。因為當s=m時,Ca_Sets=X,此時cas是全部數(shù)據(jù)對象聚類得到的一個候選類中心?？梢奀a_Sets包含過多的對象會削弱cas對第一個類的代表性?？梢妼τ趕的取值,并不是越大越好。

采用Microsoft Excel 2016軟件對實驗數(shù)據(jù)進行分析及制圖，并采用SPSS18.0和Design-Expert 8.0.5對數(shù)據(jù)進行統(tǒng)計分析，顯著水平p＜0.05。

若只考慮DensX(cas)最大,則只能說明cas周圍鄰居對象數(shù)最多,但不能保證cas與E1距離最近以及不能避免cas是邊界點,因此還需要考慮到d(cas,E1),并且保證cas與密度最大值對象Xz距離最遠。

定義4令Xz(Xz∈X)為密度最大值對象,E1∈X(E1≠Xz)為第一個類中心代表能力最強的點,cas(cas∈Ca_Cluster1)為第一個類的第s個候選類中心,則cas作為類中心的能力為:

Pro_Center(cas)=DensX(cas)+d(cas,Xz)-d(cas,E1)

(7)

令C1=argmaxcas∈Ca_Cluster1Pro_Center(cas),則C1為第一個類中心,即在候選類中心集合中選擇一個離密度最大的對象Xz最遠、自身密度最高,且更接近于E1的候選類中心作為新的類中心。因為所選擇對象的密度越大意味著其周圍鄰居對象數(shù)越多,此外離密度最大值點越遠意味著其成為每個類邊界點的可能性越小,并且需更加接近于類中心代表能力最強的點。圖2為第一個類中心生成過程。

圖2 第一個類中心的生成過程

從圖2可以看出,空心點表示生成的第一個類中心代表點E1。根據(jù)式(6)生成多個候選集合Ca_Sets,其中圈1中的對象表示集合Ca_Set1中包含的對象,同理,圈2和圈3分別表示Ca_Set2和Ca_Set3中包含的對象,且Ca_Set3?Ca_Set2?Ca_Set1。圖2中的五角星是生成的3個候選類中心{ca1,ca2,ca3}。根據(jù)定義4得出第一個新的類中心為ca1,記為C1。

定義5給定Xi∈X,k′∈{2,3,…,K},則第k′個類中心代表能力定義為:

(8)

其中,Ck表示第k個類中心。取Pro_Repre(Xi)的最大值所對應(yīng)的對象作為第k′個類中心代表能力最強點,即:

Ek′=argmaxXi∈X,Xi?{E1,E2,…,Ek′-1}Pro_Repre(Xi)

則cas(cas∈Ca_Clusterk′)作為第k′個類中心的能力為:

Pro_Center(cas)=DensX(cas)+

(9)

其中,Ck′=argmaxcas∈Ca_Clusterk′Pro_Center(cas)為第k′個類中心。對于其他類中心的選擇,本文考慮到對象與所選出的類中心之間的距離,距離越大說明該對象與選出的其他類中心差異越大,能很好地代表一個類中心,同時采用最大最小距離算法用于計算其他類中心。

3.2 算法流程

算法實現(xiàn)流程如下:

算法1IC2SACMD 算法

輸入X:由m個屬性描述的n個對象矩陣數(shù)據(jù)集;K:聚類個數(shù)

輸出數(shù)據(jù)集X的K個初始類中心C={C1,C2,…,CK}

1.初始化:C = φ;

2.fork′=1to K,do

3.if(k’==1)

4.根據(jù)式(3)和式(4)計算數(shù)據(jù)集X所有對象的平均密度,找出密度最大值的對象記為Xz;

5.對于除Xz之外的其他對象,根據(jù)式(5)計算每個對象的代表能力Pro_Repre(Xi)=d(Xz,Xi)×DensX(Xi);

6.獲得第一個類中心代表能力最強的點E1=argmaxXi∈X,Xi≠XzPro_Repre(Xi);

7.根據(jù)式(6)得出候選對象集合Ca_Sets(1≤s≤m);

8.通過候選對象集合得到候選類中心集合Ca_Cluster1;

9.對于集合Ca_Cluster1中的每個候選類中心,根據(jù)式(7)計算Pro_Center(cas)=DensX(Cas)+d(Cas,Xz)-d(Cas,E1);

10.獲得第一個類中心C1=argmaxcas∈Ca_Cluster1Pro_Center(cas);

11.else

12.for i=1to n,do

13.根據(jù)式(8)求得Xi作為第k′個類中心的代表能力Pro_Repre(Xi);

14.end for

15.獲得第k′個類中心代表能力最強的點Ek′=argmaxXi∈X,Xi?{E1,E2,…,Ek′-1}Pro_Repre(Xi);

16.for k=1to(k′-1),do

18.endfor

19.獲得第k′個類中心Ck′=argmaxcas∈Ca_Clusterk′Pro_Center(cas);

20.end if

21.C=C∪Ck′;

22.end for

23.return C.

4 實驗結(jié)果與分析

為驗證本文算法的有效性,在7個不同的真實數(shù)據(jù)集上進行實驗。對數(shù)據(jù)集進行簡單介紹,給出實驗所需評價指標,將算法與其他方法進行比較,并對實驗結(jié)果進行分析。

4.1 實驗數(shù)據(jù)

本文實驗使用了7個真實的數(shù)據(jù)集,其中musk[13]數(shù)據(jù)集是從UCI上下載,其余數(shù)據(jù)集是由Veronika Cheplygina整理[14]存放在(http://www.miproblems.org)網(wǎng)站上。mutagenesis[15]和musk是由藥物活性預測問題引起的,在這些數(shù)據(jù)集上,可將每個分子的每個形狀看作一個特征向量,由多個形狀構(gòu)成的分子看作一個矩陣對象。mutagenesis根據(jù)難易程度分為兩種,即文中的mutagenesis1和mutagenesis2。ucsb_breast[16]是一個圖像數(shù)據(jù)集,可以從網(wǎng)址(http://www.bioimage.ucsb.edu/research/biosegmentation)上下載。elephant和tiger是從(http://www.cs.columbia.edu/～andrews/mil/datasets.html)下載的圖像數(shù)據(jù)集[17],可將每張圖片的一個分割部分看作一個特征向量,則多個分割部分合成的圖片就是一個矩陣對象。component[18]是從(http://www.biocreative.org/tasks/biocreative-i/task-2-functional-annotations/)下載的一個文本數(shù)據(jù)集,可以將每個段落看作一個特征向量,多個段落組成的一個文本就是一個矩陣對象。表3給出全部數(shù)據(jù)集的相關(guān)信息。

表3 實驗中使用的數(shù)據(jù)集

因為缺少公開的分類型矩陣數(shù)據(jù)集,且已有的分類型矩陣數(shù)據(jù)集的維度較低,對于計算屬性間距離有比較大的影響,所以本文用數(shù)值型矩陣數(shù)據(jù)集來驗證提出算法的有效性。由于數(shù)值型數(shù)據(jù)的屬性值是連續(xù)的,因此需要對其進行離散化處理。對于musk數(shù)據(jù)集,數(shù)據(jù)的屬性值是整數(shù)型,可以認為是離散型數(shù)據(jù),則只需對除musk數(shù)據(jù)集之外的其余數(shù)據(jù)集進行歸一化處理,歸一化公式定義為:

(10)

然后將歸一化后的數(shù)據(jù)集進行均勻離散化處理,將其平均分成10份,相對應(yīng)的值分別設(shè)置為{1,2,…,10}構(gòu)成了實驗所需數(shù)據(jù)集。

4.2 評價指標

為評價本文提出的初始類中心算法的有效性,使用5個評價指標,即精度(AC)、查準率(PR)、召回率(RE)、標準互信息(NMI)[19]和調(diào)整蘭德指數(shù)(ARI)[20]評價算法的優(yōu)劣[3]。

4.3 結(jié)果分析

為驗證本文提出的初始類中心選擇算法的有效性,將該算法與一種隨機初始化Random算法[3]進行了比較,并與另外兩種典型的初始類中心選擇算法CAOICACD算法[10]和BAIICACD算法[11]也進行了比較。對于初始類中心算法IC2SACMD、CAOICACD和BAIICACD,只需聚類一次即可。而對于實驗中的Random算法,由于該算法采取隨機初始化類中心,則需要對每個數(shù)據(jù)集進行50次聚類,將其均值作為最終的結(jié)果。由于目前在分類型矩陣數(shù)據(jù)上的相關(guān)工作較少,本文選用了針對普通分類型數(shù)據(jù)比較典型的兩種初始類中心選擇算法CAOICACD和BAIICACD來進行比較,因此需要將本文中的7個真實的數(shù)據(jù)集進行簡單處理,即先將矩陣數(shù)據(jù)集進行了壓縮,每個矩陣對象用頻率最高的屬性值來表示。在新生成的數(shù)據(jù)集中,一個對象只有一條記錄,然后將后兩種算法在新生成的數(shù)據(jù)集中進行實驗。本文實驗結(jié)果如表4所示,其中,表中加粗字體為不同算法針對每個數(shù)據(jù)集在不同評價指標上的最優(yōu)結(jié)果。

表4 不同算法在各數(shù)據(jù)集上的實驗結(jié)果

從實驗結(jié)果可以看出,在7個真實數(shù)據(jù)集上,本文IC2SACMD算法優(yōu)于Random算法、CAOICACD算法和BAIICACD算法,并在5個評價指標上都產(chǎn)生了比較好的聚類效果,尤其是在mutagenesis2數(shù)據(jù)集上的聚類效果顯著,相比Random算法提高了22%的精度,相比ucsb_breast數(shù)據(jù)集提高了5%的精度。而CAOICACD算法和BAIICACD算法在不同數(shù)據(jù)集的5個評價指標上的效果相差不大,僅在tiger和component數(shù)據(jù)集上相差比較明顯,特別是BAIICACD算法在component數(shù)據(jù)集上達到相對最優(yōu),甚至超過了本文算法2%的精度,可見,BAIICACD算法在component數(shù)據(jù)集上效果更好。但是CAOICACD算法和BAIICACD算法因為數(shù)據(jù)集進行壓縮時,會導致許多信息的丟失,以至于精確度較低。

5 結(jié)束語

分類型矩陣數(shù)據(jù)在實際應(yīng)用中廣泛存在。針對分類型矩陣數(shù)據(jù),本文根據(jù)屬性值的頻率定義了矩陣對象的密度和矩陣對象間的距離,擴展了最大最小距離算法,從而實現(xiàn)初始類中心的選擇,在此基礎(chǔ)上,提出一種面向分類型矩陣數(shù)據(jù)的初始類中心選擇算法。實驗結(jié)果表明,與傳統(tǒng)初始類中心選擇算法相比,該算法具有較優(yōu)的聚類效果。在未來的工作中將結(jié)合半監(jiān)督學習來選擇初始類中心。