基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法

王家耀,謝明霞,2,郭建忠,陳 科

1.信息工程大學(xué)測(cè)繪學(xué)院,河南鄭州450052;2.75719部隊(duì),湖北武漢430074

基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法

王家耀1,謝明霞1,2,郭建忠1,陳 科1

1.信息工程大學(xué)測(cè)繪學(xué)院,河南鄭州450052;2.75719部隊(duì),湖北武漢430074

提出一種基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法。首先,通過相似性度量函數(shù)計(jì)算得到高維空間對(duì)象相似度矩陣,并利用近鄰法、Floyd最短路徑算法將相似度矩陣轉(zhuǎn)換為最短路徑距離矩陣;然后,將高維特征變換轉(zhuǎn)化為遺傳優(yōu)化問題,利用特征變換降維后的二維數(shù)據(jù)進(jìn)行k-均值聚類,并根據(jù)(高維坐標(biāo),降維后二維坐標(biāo))值進(jìn)行RBF神經(jīng)網(wǎng)絡(luò)訓(xùn)練,當(dāng)新對(duì)象輸入時(shí),利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)對(duì)其進(jìn)行二維映射,通過判斷該對(duì)象與各聚類簇中心距離的遠(yuǎn)近獲得其歸屬;最后,通過試驗(yàn)驗(yàn)證了改進(jìn)相似性度量函數(shù)能夠有效表達(dá)高維數(shù)據(jù)對(duì)象間的相似性,且基于特征變換的降維方法具有可操作性。

特征變換;高維數(shù)據(jù)聚類;相似度;降維

1 引 言

聚類分析是數(shù)據(jù)挖掘研究的一個(gè)重要方向。所有的聚類問題都是在對(duì)給定數(shù)據(jù)集進(jìn)行劃分的同時(shí),根據(jù)同一簇中的對(duì)象盡可能相似、不同簇間的對(duì)象盡可能相異這一準(zhǔn)則,設(shè)計(jì)優(yōu)化函數(shù),通過對(duì)所設(shè)計(jì)的優(yōu)化問題的求解實(shí)現(xiàn)數(shù)據(jù)對(duì)象的聚類[1]。由于“維度困擾”的存在,目前絕大多數(shù)聚類算法在高維空間中無法得到理想的效果。為使現(xiàn)有聚類算法能夠適用于高維空間,可以從兩個(gè)方面進(jìn)行改進(jìn):相似性度量和高維空間降維。

在高維數(shù)據(jù)相似性度量方面,就是否能獲得高維數(shù)據(jù)聚類的成效而言,指定適當(dāng)?shù)南嗨菩?相異性)度量比選擇聚類算法更為重要。現(xiàn)有的高維數(shù)據(jù)相似性度量的改進(jìn)方法可以概括為兩種:一是基于傳統(tǒng)距離度量的改進(jìn)方法[2-4];二是相似性度量方法重構(gòu)[5-7]。傳統(tǒng)的相似性度量有距離度量和相似系數(shù)。文獻(xiàn)[7-8]對(duì)Lk-范數(shù)和數(shù)據(jù)維數(shù)關(guān)系的研究結(jié)果說明在高維空間中用Lk-范數(shù)作距離函數(shù)時(shí),隨著維數(shù)的增加,點(diǎn)與點(diǎn)之間距離的對(duì)比性不復(fù)存在,基于傳統(tǒng)Lk-范數(shù)的改進(jìn)相似性度量方法本質(zhì)上無法避免“維災(zāi)”的影響; Cosine度量和Pearson相關(guān)系數(shù)適于高維空間中數(shù)值型數(shù)據(jù)的相似性度量,而不能用于分類型數(shù)據(jù)相似度的計(jì)算;Jaccard系數(shù)可以較好地反映高維數(shù)據(jù)在屬性上的相似程度,但不能反映其在高維空間距離上的相似程度。文獻(xiàn)[7-8]重新設(shè)計(jì)高維空間中的相似性度量,文獻(xiàn)[5]對(duì)其設(shè)計(jì)的相似性度量方法進(jìn)行改進(jìn),提出度量函數(shù) Hsim,該函數(shù)避免原低維空間中定義的距離函數(shù)在高維空間中的不適用問題,但不能用于對(duì)分類屬性數(shù)據(jù)的相似性度量。文獻(xiàn)[6]對(duì)函數(shù) Hsim進(jìn)行擴(kuò)展使其能夠?qū)Ψ诸愋蛿?shù)據(jù)進(jìn)行度量,但該方法仍存在一些不足,文章將在下一節(jié)對(duì)其進(jìn)行具體的分析和說明。如何設(shè)計(jì)適于高維數(shù)據(jù)對(duì)象間的相似性度量方法是提高高維數(shù)據(jù)聚類算法有效性的關(guān)鍵問題。

在高維空間降維方面,降維的方式有兩種:特征(或?qū)傩?選擇和特征(或?qū)傩?變換。特征(或?qū)傩?選擇在降維中存在的最大弊端在于計(jì)算的復(fù)雜度,當(dāng)數(shù)據(jù)維數(shù)比較高時(shí),子空間數(shù)目將會(huì)急劇增長(zhǎng),導(dǎo)致對(duì)子空間中各簇的搜索過程漫長(zhǎng)而又復(fù)雜,從而使算法失效;特征(或?qū)傩?變換方法包括PCA、LDA、KPCA、ISOMAP、LL E及其相應(yīng)的改進(jìn)方法等,如文獻(xiàn)[9-11]。現(xiàn)有特征變換方法的主要缺陷在于其只能獲得已知數(shù)據(jù)集的潛在低維結(jié)構(gòu),并不能給出高維空間中數(shù)據(jù)點(diǎn)到低維空間的確定性映射關(guān)系。

針對(duì)以上問題,主要對(duì)高維數(shù)據(jù)相似性度量的重構(gòu)和基于特征變換的降維進(jìn)行研究,將適于高維空間的相似性度量與降維過程中的距離保持方法相結(jié)合,使得在降維后的低維空間中,原數(shù)據(jù)集中各數(shù)據(jù)點(diǎn)之間在高維空間中的相似性得到有效保持。為確定原高維數(shù)據(jù)和降維后低維數(shù)據(jù)的映射關(guān)系,利用神經(jīng)網(wǎng)絡(luò)獲取降維轉(zhuǎn)換器,當(dāng)新的高維數(shù)據(jù)點(diǎn)輸入時(shí),能夠快速有效地獲取其相應(yīng)的低維坐標(biāo)。

2 關(guān)鍵技術(shù)

2.1 相似性測(cè)度計(jì)算

高維數(shù)據(jù)對(duì)象間的相似性主要體現(xiàn)在屬性相似性和幾何相似性兩個(gè)方面。

定義1:屬性映射值

對(duì)于區(qū)間標(biāo)度型、序數(shù)和比例標(biāo)度型對(duì)象,屬性映射值表示各維信息是否存在,即是否有取值,若存在,則對(duì)應(yīng)維的屬性映射值為1,反之為0;對(duì)于分類型對(duì)象,屬性映射值表示各維的取值,若各維取值是概念性的,如{好,中,差},將其進(jìn)行數(shù)值化映射,即{好,中,差}→{1,0,-1}。

定義2:幾何相似度

幾何相似度S(X,Y)表示對(duì)象X和Y空間距離的遠(yuǎn)近程度,S(X,Y)越大,表明 X和Y越相似,在空間上越接近;反之亦然。其表達(dá)式為

式中,xi、yi表示對(duì)象 X和 Y在第 i維上的屬性值。

定義3:屬性相似概率

屬性相似概率 P(txi,tyi)表示屬性 i上的幾何相似度在d維對(duì)象X和Y的總體相似度中所占的比例,即

式中,txi、tyi為對(duì)象X和Y在第i維上的屬性映射值;φ(txi,tyi)表示對(duì)象 X和Y在第i維上的屬性映射值是否相同,若 txi≠tyi,則φ(txi,tyi)=0,若txi=tyi,則φ(txi,tyi)=1。

文獻(xiàn)[5]所設(shè)計(jì)的高維數(shù)據(jù)相似性度量函數(shù)Hsim解決原有低維空間中定義的距離函數(shù)不適用于高維空間的問題,Hsim在高維空間中的有效性在文獻(xiàn)中已進(jìn)行論證,其具體設(shè)計(jì)如下

式中,d為兩個(gè)對(duì)象X和Y中不全為空的維數(shù),函數(shù)值范圍為[0,1]。該函數(shù)在設(shè)計(jì)過程中未考慮屬性之間的相似性,故不能用于分類型數(shù)據(jù)的相似性度量。為使其能夠處理分類型數(shù)據(jù),文獻(xiàn)[6]對(duì)其進(jìn)行擴(kuò)展,具體擴(kuò)展函數(shù)為

式中,若 xi=yi,則δ(xi,yi)=0;若 xi≠yi,則δ(xi,yi)=1。本文利用表1所列分類型數(shù)據(jù)來說明式(4)的不足。

表1 分類型數(shù)據(jù)Tab 1.Categorical data

根據(jù)公式(4)計(jì)算點(diǎn) X和Y之間的相似性,其結(jié)果為 Hsimc(X,Y)=1/2,顯然 Hsimc所反映出的相似性與實(shí)際情況是不相符的。本文融合高維數(shù)據(jù)的屬性相似性和幾何相似性,并將不同類型數(shù)據(jù)的相似性度量函數(shù)整合到統(tǒng)一的 HDsim函數(shù)中,具體定義如下

針對(duì)數(shù)值型數(shù)據(jù),本文提出的相似性度量方法首先對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理,避免維間數(shù)值大小相差較大給相似性度量帶來的不合理影響,并使其具有不依賴于幅值的特性;然后獲取數(shù)據(jù)集相應(yīng)的二元特征集,即對(duì)無取值的屬性設(shè)置為0,對(duì)有取值的屬性設(shè)置為1;最后根據(jù)式(5)計(jì)算對(duì)象間的相似度。在計(jì)算過程中,化簡(jiǎn)后的HDsim與原 Hsim相同。因此,本文設(shè)計(jì)的相似性度量函數(shù) HDsim在處理數(shù)值型數(shù)據(jù)時(shí)能夠充分利用Hsim函數(shù)的優(yōu)越性;針對(duì)二元數(shù)據(jù),函數(shù)Hsim與 HDsim計(jì)算得到的相似度量與Jaccard系數(shù)一致;針對(duì)分類型數(shù)據(jù)(分類型數(shù)據(jù)是二元數(shù)據(jù)的推廣,它可以取多個(gè)狀態(tài)值,即多元數(shù)據(jù)),函數(shù) HDsim計(jì)算得到的相似度量與常用的分類型數(shù)據(jù)相似性度量方法(匹配率)一致,而 Hsim已無法求得對(duì)象間的相似性。

2.2 基于相似性保持的高維空間結(jié)構(gòu)流形正確展開的降維方法

為了提高高維數(shù)據(jù)聚類的效率,本文采用特征變換的方式對(duì)原高維空間進(jìn)行降維,并在降維后的低維空間中保持?jǐn)?shù)據(jù)對(duì)象在高維空間的近鄰關(guān)系。

根據(jù)公式

將相似度矩陣轉(zhuǎn)化為距離矩陣 HD。聚類過程中數(shù)據(jù)對(duì)象間的相似關(guān)系需要滿足兩個(gè)一致性假設(shè):局部一致性——鄰近的數(shù)據(jù)點(diǎn)具有較高的相似度;全局一致性——同一流形上的數(shù)據(jù)點(diǎn)具有較高的相似度[12]。對(duì)于圖l所示的情況,按照HDsim進(jìn)行相似度度量時(shí),數(shù)據(jù)點(diǎn)1和3的相似程度明顯高于數(shù)據(jù)點(diǎn)1和2之間的相似度,因此不能反映圖1所示數(shù)據(jù)的全局一致性。

圖1 HDsim相似性度量的全局不一致Fig.1 Global inconsistency of similarity measureHDsim

為了解決上述問題,利用對(duì)象間的最短路徑代替不能表達(dá)流形結(jié)構(gòu)的歐氏距離,通過給定鄰域大小,用近鄰法創(chuàng)建與距離矩陣 HD相應(yīng)的鄰域圖[13-15],并判斷圖的連通性,對(duì)連通圖采用最短路徑算法,得到 HDsim相似性度量基礎(chǔ)上的最短路徑距離矩陣D。對(duì)每一高維數(shù)據(jù)對(duì)象隨機(jī)地賦一初始二維坐標(biāo)值,通過使二維數(shù)據(jù)對(duì)象間歐氏距離趨近于高維空間對(duì)象間的最短路徑距離,對(duì)二維坐標(biāo)值進(jìn)行迭代優(yōu)化。該過程可以近似轉(zhuǎn)化為使二維空間中各對(duì)象歐氏距離與對(duì)應(yīng)原高維空間對(duì)象間最短路徑距離測(cè)度之間的誤差總和達(dá)到最小,使以下誤差函數(shù)達(dá)到最小值

式中,d′ij表示降維后二維對(duì)象間的歐氏距離。利用遺傳算法對(duì)此優(yōu)化問題進(jìn)行求解,誤差函數(shù)值越小,則遺傳過程中個(gè)體的適應(yīng)度值越高[16]。定義個(gè)體的適應(yīng)度函數(shù)為

2.3 降維轉(zhuǎn)換器的生成及聚類簇更新

常用的基于特征變換的降維方法對(duì)原始數(shù)據(jù)進(jìn)行降維后,當(dāng)有新對(duì)象輸入時(shí),不僅要對(duì)新數(shù)據(jù)對(duì)象進(jìn)行處理,而且需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新降維,其結(jié)果是嚴(yán)重影響降維聚類算法的時(shí)效性。針對(duì)該問題,利用遺傳降維所獲得的數(shù)據(jù)值對(duì)二維映射后數(shù)據(jù)對(duì)象,進(jìn)行RBF(徑向基)神經(jīng)網(wǎng)絡(luò)訓(xùn)練,保存訓(xùn)練好的神經(jīng)網(wǎng)絡(luò),從而獲得對(duì)象高維坐標(biāo)到低維坐標(biāo)的轉(zhuǎn)換器。當(dāng)一新數(shù)據(jù)對(duì)象 pnew輸入時(shí),利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)對(duì)其進(jìn)行低維轉(zhuǎn)換,獲得相應(yīng)的低維坐標(biāo)值 p降維,并根據(jù) p降維與原聚類簇中心的距離判斷新數(shù)據(jù)對(duì)象的歸屬,即判斷完新對(duì)象的歸屬后,重新計(jì)算各聚類均值,更新各聚類簇中心。由于新對(duì)象的低維坐標(biāo)是通過原降維轉(zhuǎn)換器獲取,其精度無法判斷,且降維轉(zhuǎn)換器需要通過對(duì)外來數(shù)據(jù)值對(duì)(本身并不通過該降維轉(zhuǎn)換器求取的數(shù)據(jù)值對(duì))的學(xué)習(xí)進(jìn)行更新,因此,本文在獲取新對(duì)象的低維坐標(biāo)后,不利用此數(shù)據(jù)值對(duì)更新降維轉(zhuǎn)換器。

2.4 基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法

本文提出的高維數(shù)據(jù)聚類改進(jìn)算法,在降維過程中保持相似性度量在高維空間中的有效性,使數(shù)據(jù)對(duì)象在降維后的低維空間中能夠正確展開高維數(shù)據(jù)對(duì)象間的相似性結(jié)構(gòu)流形。算法的流程圖如圖2所示。

圖2 基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法流程圖Fig.2 The flow of improved high dimensional data clustering algorithm based on similarity preserving and feature transformation

3 試驗(yàn)及有效性分析

3.1 仿真數(shù)據(jù)試驗(yàn)

利用MA TLAB分別隨機(jī)生成7個(gè)包含50條10維、20維、50維、100維、200維、300維以及400維記錄的數(shù)據(jù)集和5個(gè)包含10條、20條、30條、50條和100條50維記錄的數(shù)據(jù)集。對(duì)仿真數(shù)據(jù)集進(jìn)行遺傳降維,圖3和圖4分別為遺傳降維所用時(shí)間隨數(shù)據(jù)維數(shù)和數(shù)據(jù)量變化的對(duì)比圖。從圖中可以看出,本文提出的遺傳降維方法所用的時(shí)間與數(shù)據(jù)集的維數(shù)無關(guān),而與數(shù)據(jù)集的數(shù)據(jù)量相關(guān),當(dāng)數(shù)據(jù)量增加時(shí),降維所用的時(shí)間顯著增加。因此,在實(shí)際降維過程中,當(dāng)數(shù)據(jù)集的數(shù)據(jù)量非常大時(shí),為提高遺傳算法降維的效率,考慮在原始高維空間中隨機(jī)抽取若干高維數(shù)據(jù)對(duì)象進(jìn)行交叉變異,獲得其相應(yīng)的降維后坐標(biāo),根據(jù)所抽取對(duì)象的值對(duì)(原高維空間坐標(biāo)值,降維后二維空間坐標(biāo)值)進(jìn)行神經(jīng)網(wǎng)絡(luò)映射,獲得降維轉(zhuǎn)換器,并利用轉(zhuǎn)換器計(jì)算原始高維空間中未被抽取的數(shù)據(jù)對(duì)象的低維映射坐標(biāo)值。

圖3 遺傳降維所用時(shí)間隨維數(shù)變化曲線Fig.3 Change curve of consuming time with dimension

圖4 遺傳降維所用時(shí)間隨數(shù)據(jù)量變化曲線Fig.4 Change curve of consuming time with data quantity

3.2 機(jī)器學(xué)習(xí)數(shù)據(jù)試驗(yàn)

為驗(yàn)證改進(jìn)相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法針對(duì)真實(shí)數(shù)據(jù)的有效性,以UCI提供的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中iris(數(shù)值型)和zoo(分類型)數(shù)據(jù)集為例,分別利用k-均值、基于 PCA降維的k-均值(PCA k-means)、基于歐氏距離保持的k-均值(Euclid k-means)以及本文提出的高維數(shù)據(jù)聚類算法(HDsim k-means)對(duì)其進(jìn)行聚類對(duì)比分析。為提高遺傳降維算法的效率,隨機(jī)抽取數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)進(jìn)行降維,生成降維轉(zhuǎn)換器后對(duì)未被抽取的數(shù)據(jù)進(jìn)行降維映射,獲取相應(yīng)的低維坐標(biāo)。在聚類分析前,去掉iris和zoo數(shù)據(jù)集中的類標(biāo)識(shí)屬性,聚類后,利用聚類結(jié)果和類標(biāo)識(shí)屬性信息進(jìn)行對(duì)比,即對(duì)各方法獲得的聚類結(jié)果采用基于已知類標(biāo)識(shí)分布的聚類質(zhì)量度量方法——聚類簇純凈度PCC及聚類熵EIC進(jìn)行質(zhì)量評(píng)價(jià),其定義參見文獻(xiàn)[17]。

圖5(a)、(b)、(c)分別為利用PCA k-means、Euclid k-means以及HDsim k-means對(duì)iris數(shù)據(jù)集的聚類可視化結(jié)果,表2和表3分別為各聚類方法所用時(shí)間和精度的對(duì)比。圖6為zoo數(shù)據(jù)集的降維聚類可視化結(jié)果,表4和表5分別為利用二步聚類、Euclid k-means以及 HDsim k-means對(duì)zoo數(shù)據(jù)集的聚類所用時(shí)間和精度的對(duì)比。為便于可視化結(jié)果的對(duì)比,各方法降維結(jié)果均已進(jìn)行歸一化。針對(duì)zoo數(shù)據(jù)集,由于PCA方法僅適用于變量之間存在一定相關(guān)性的數(shù)值型數(shù)據(jù)集的降維,而不能用于處理非線性數(shù)據(jù)和分類型數(shù)據(jù),因此,無法利用PCA k-means方法對(duì)zoo數(shù)據(jù)集進(jìn)行降維聚類(降維結(jié)果無意義)。

圖5 iris數(shù)據(jù)集降維聚類可視化Fig.5 Dimensionality reduction clustering visualization of data set iris

圖6 zoo數(shù)據(jù)集降維聚類可視化Fig.6 Dimensionality reduction clustering visualization of zoo set iris

表2 iris數(shù)據(jù)集各算法聚類時(shí)間對(duì)比Tab.2 Consuming time of each clustering algorithm to data set iris s

表3 iris數(shù)據(jù)集聚類結(jié)果對(duì)比Tab.3 Clustering results of data set iris

表4 zoo數(shù)據(jù)集各算法聚類時(shí)間對(duì)比Tab.4 Consuming time of each clustering algorithm to data set zoo

表5 zoo數(shù)據(jù)集聚類結(jié)果對(duì)比Tab.5 Clustering results of data set

3.3 試驗(yàn)分析

k-均值聚類的精度取決于聚類個(gè)數(shù)和初始中心確定的好壞,在處理高維數(shù)據(jù)時(shí),由于不易確定其聚類個(gè)數(shù)和初始聚類簇中心,導(dǎo)致聚類結(jié)果和聚類時(shí)間無法確定,而降維可視化對(duì)k-均值聚類中聚類個(gè)數(shù)和初始中心的選取具有指導(dǎo)意義。在確定聚類數(shù)和初始聚類簇中心后,由于k-均值聚類是對(duì)原始高維數(shù)據(jù)進(jìn)行處理,而 PCA kmeans、Euclid k-means以及 HDsim k-means是對(duì)降維后的數(shù)據(jù)進(jìn)行處理,降維后的數(shù)據(jù)量明顯少于原數(shù)據(jù)量,因此,僅就聚類時(shí)間(不包括數(shù)據(jù)預(yù)處理、聚類數(shù)和初始簇中心的確定所需時(shí)間)而言,PCA k-means、Euclid k-means以及 HDsim k-means的聚類時(shí)間要少于k-均值聚類。Euclid k-means和 HDsim k-means算法數(shù)據(jù)預(yù)處理階段所需時(shí)間較長(zhǎng),而PCA k-means所用的時(shí)間要遠(yuǎn)遠(yuǎn)少于 Euclid k-means和 HDsim k-means算法,但PCA應(yīng)用范圍有限,主要表現(xiàn)在以下幾個(gè)方面:①當(dāng)隨機(jī)生成的數(shù)據(jù)集維數(shù)達(dá)到170維左右時(shí),傳統(tǒng)的 PCA方法已無法對(duì)其進(jìn)行降維;②PCA不能對(duì)數(shù)值型以外的數(shù)據(jù)進(jìn)行降維;③PCA不能處理非線性數(shù)據(jù)。

文中涉及的各降維聚類方法中高維數(shù)據(jù)對(duì)象的降維坐標(biāo)是通過不同性質(zhì)的降維方法(PCA、基于Euclid距離保持的降維以及基于HDsim相似性保持的降維方法)獲取的,因此,利用各方法求取的數(shù)據(jù)對(duì)象降維后的坐標(biāo)之間并沒有相關(guān)性,從而導(dǎo)致聚類可視化結(jié)果圖5、6中各方法降維聚類結(jié)果在數(shù)據(jù)分布上不存在相似性。由可視化結(jié)果圖5可知,算法 PCA k-means、Euclid kmeans和 HDsim k-means都較好地保留iris各聚類數(shù)據(jù)的內(nèi)部局部結(jié)構(gòu),但PCA k-means所獲得的聚類結(jié)果中Virginica和Versicolor兩類之間無明顯界線;由圖6可以看出,算法 Euclid kmeans和 HDsim k-means較好地保留各聚類數(shù)據(jù)的內(nèi)部局部結(jié)構(gòu),但 Euclid k-means的聚類可視化中類與類界限不清晰。

從iris和zoo數(shù)據(jù)集的聚類精度對(duì)比結(jié)果可以看出,本文提出的基于相似性保持和特征變換的高維數(shù)據(jù)聚類改進(jìn)算法 HDsim k-means在聚類精度上要優(yōu)于傳統(tǒng)的經(jīng)典聚類方法、PCA kmeans和 Euclid k-means。針對(duì)數(shù)值型數(shù)據(jù)集(iris),文中所提出的聚類方法的聚類純凈度及聚類熵遠(yuǎn)遠(yuǎn)好于 k-均值和 PCA k-means,略好于Euclid k-means;針對(duì)分類型數(shù)據(jù)(zoo),文中方法的聚類熵與二步聚類結(jié)果類似,但優(yōu)于Euclid kmeans,且聚類純度最高。改進(jìn)算法不僅在聚類精度上優(yōu)于其他算法,而且該方法只需獲得對(duì)象間的相似度,利用遺傳交叉變異可以方便地對(duì)數(shù)據(jù)進(jìn)行相似性保持的數(shù)值化降維,后續(xù)的聚類過程可以采用統(tǒng)一的經(jīng)典聚類算法(如k-均值)完成,而不需對(duì)聚類流程進(jìn)行重新設(shè)計(jì)。

4 結(jié) 論

通過對(duì)本文聚類方法與傳統(tǒng)聚類方法、PCA k-means以及Euclid k-means聚類結(jié)果的可視化和精度對(duì)比,證明本文提出的改進(jìn)聚類算法在高維空間中的有效性和可行性。研究結(jié)果表明:①本文提出的相似性度量函數(shù)在形式上比原有公式復(fù)雜,但方法的實(shí)質(zhì)只是增加了對(duì)各維屬性類型的判斷,其計(jì)算量并未增加;②在降維過程中對(duì)HDsim相似性的保持比對(duì)Euclid距離進(jìn)行保持更好地保留了各聚類數(shù)據(jù)的內(nèi)部局部結(jié)構(gòu);③改進(jìn)聚類算法雖然在降維階段所需時(shí)間較長(zhǎng),但通過降維結(jié)果的可視化較好地解決了傳統(tǒng)k-均值不易確定聚類數(shù)和初始聚類中心的問題;④在降維后的低維空間中保持高維數(shù)據(jù)對(duì)象間相似性,即將高維數(shù)據(jù)對(duì)象間的相似程度轉(zhuǎn)化為低維空間中對(duì)象間的相似程度,則對(duì)映射后的二維樣本聚類就相當(dāng)于對(duì)原始的高維樣本聚類,因此,本文提出的改進(jìn)聚類算法具有可行性。

[1] CECILIA M.Clustering Problems and Their Applications [R].Durham:Duke University,1997.

[2] XIE Lihong.The Research on Clustering for High Dimensional Data[D].Wuhan:Wuhan University,2002.(謝立宏.面向高維數(shù)據(jù)的聚類算法研究[D].武漢:武漢大學(xué),2002.)

[3] LIU Jiping,WANG Hongbin,WANG Chengbo,et al.Fuzzy Nearest Neighbor Clustering of High-dimensional Data[J]. Journal of Chinese Computer Systems,2005,26(2):261-263.(劉紀(jì)平,汪宏斌,汪誠(chéng)波,等.基于模糊最近鄰的高維數(shù)據(jù)聚類[J].小型微型計(jì)算機(jī)系統(tǒng),2005,26(2): 261-263.)

[4] JOSHUA Z H,MICHAEL K,RONG H Q,et al.Automated Variable Weighting in k-Means Type Clustering[J].IEEE Transactions on Pattern Analysis and MachineIntelligence,2005,27(5):657-668.

[5] YANG Fengzhao,ZHU Yangyong.An Efficient Method for Similarity Search on Quantitative Transaction Data[J]. Journal of Computer Research and Development,2004,41 (2):361-368.(楊風(fēng)召,朱揚(yáng)勇.一種有效的量化交易數(shù)據(jù)相似性搜索方法[J].計(jì)算機(jī)研究與發(fā)展,2004,41(2): 361-368.)

[6] ZHAO Heng.Study on Some Issues of Data Clustering in Data Mining[D].Xi’an:Xidian University,2005.(趙恒.數(shù)據(jù)挖掘中聚類若干問題研究[D].西安:西安電子科技大學(xué),2005.)

[7] AGGARWAL C C.Re-designing Distance Functions and Distance-based Applications forHigh Dimensional Data [J].ACM SIGMOD Record,2001,30(1):13-18.

[8] AGGARW AL C C.On the Effects of Dimensionality Reduction on High Dimensional Similarity Search[C]∥Proceedings of the 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.New York:ACM,2001: 256-266.

[9] LIU Xiaoming,YIN Jianwei,FENG Zhilin,et al.Orthogonal Neighborhood Preserving EmbeddingBased Dimension Reduction and Classification Method[J].Journal of Image and Graphics,2009,14(7):1319-1326.(劉小明,尹建偉,馮志林,等.正交化近鄰關(guān)系保持的降維及分類算法[J].中國(guó)圖象圖形學(xué)報(bào),2009,14(7):1319-1326.)

[10] L I Yang.Distance-preserving Projection ofHighdimensional Data for Nonlinear Dimensionality Reduction [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1243-1246.

[11] LIU Zhonghua,ZHOU Jingbo,CHEN Yi,et al.Non-linear Dimensionality Reduction Techniques of Distance-preserving Projection for Visualization and Classification[J].Acta Electronica Sinica,2009(8):1820-1825.(劉中華,周靜波,陳燚,等.距離保持投影非線性降維技術(shù)的可視化與分類[J].電子學(xué)報(bào),2009(8):1820-1825.)

[12] WANG Na,DU Haifeng,WANG Sunan.Iterative Optimization Clustering Algorithm Based on Manifold Distance [J].Journal of Xi’an Jiaotong University,2009,43(5): 76-79.(王娜,杜海峰,王孫安.一種基于流形距離的迭代優(yōu)化聚類算法[J].西安交通大學(xué)學(xué)報(bào),2009,43(5): 76-79.)

[13] TENENBAUM J B,SILVA V,UNGFORD J C.A Global Geometric Framework for NonlinearDimensionality Reduction[J].Science,2000,290(12):2319-2323.

[14] GENG Xiepeng,DU Xiaochu,HU Peng.Spatial Clustering Method Based on Raster Distance Transform for Extended Objects[J].Acta Geodaetica et Cartographica Sinica, 2009,38(2):162-167,174.(耿協(xié)鵬,杜曉初,胡鵬.基于柵格距離變換的擴(kuò)展對(duì)象空間聚類方法[J].測(cè)繪學(xué)報(bào), 2009,38(2):162-167,174.)

[15] GUO Qingsheng,Zheng Chunyan,HU Huake.Hierarchical Clustering Method ofGroup of Points Based on the Neighborhood Graph[J].Acta Geodaetica et Cartographica Sinica,2008,37(2):256-261.(郭慶勝,鄭春燕,胡華科.基于近鄰圖的點(diǎn)群層次聚類方法的研究[J].測(cè)繪學(xué)報(bào), 2008,37(2):256-261.)

[16] WANG Baowen,YAN Junmei,LIU Wenyuan,et al.High Dimensional Datas Fuzzy Clustering Based on Genetic Algorithm[J].Computer Engineering and Application, 2007,43(16):191-192,221.(王寶文,閻俊梅,劉文遠(yuǎn),等.基于遺傳算法的高維數(shù)據(jù)模糊聚類[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(16):191-192,221.)

[17] ZHANG Weijiao,LIU Chunhuang,LI Fangyu.Method of Quality Evaluation for Clustering [J].Computer Engineering,2005,31(20):10-12.(張惟皎,劉春煌,李芳玉.聚類質(zhì)量的評(píng)價(jià)方法[J].計(jì)算機(jī)工程,2005,31(20): 10-12.)

Improved High Dimensional Data Clustering Algorithm Based on Similarity Preserving and Feature Transformation

WANGJiayao1,XIE Mingxia1,2,GUO Jianzhong1,CHEN Ke1
1.Institute of Surveying and Mapping,Information Engineering University,Zhengzhou 450052,China;2.75719 Troup,Wuhan 430074,China

Improved high dimensional data clustering algorithm based on similarity preserving and feature transformation is proposed.Firstly,gain the similarity matrix of high dimensional data with the designed similarity measure function,and translate it into distance matrix of the shortest path through the nearest neighbor searching method and the algorithm Floyd.Then,translate high dimensional feature transformation into the optimization and resolve this optimization problem with genetic algorithm.The reduced data is used for clustering analysis via k-means and the value pairs between the coordinates of high dimensional data and their reduced 2D coordinates are used for RBF neural network training.Determine the belongingness of new object based on the distance from the new object to each current clustering center through the trained neural network.Finally,the experimental results prove the validity of the improved similarity measure and the operability of the dimensionality reduction method based on feature transformation.

feature transformation;high dimensional data clustering;similarity measure;dimensionality reduction

WANGJiayao(1936—),male,professor, academician ofChineseAcademicofEngineering, majors in teaching and scientific research of cartography and geographic information engineering.

1001-1595(2011)03-0269-07

TP181

A

國(guó)家863計(jì)劃(2009AA12Z228);國(guó)家科技支撐計(jì)劃課題(2007BAH16B03)

(責(zé)任編輯:宋啟凡)

2010-03-10

2010-09-27

王家耀(1936—),男,教授,中國(guó)工程院院士,從事地圖制圖學(xué)與地理信息工程學(xué)科的教學(xué)與科研。

E-mail:wangjy@cae.cn