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

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

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

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

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

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

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

1 引 言

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

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

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

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

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

2.1 相似性測度計算

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

定義1:屬性映射值

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

定義2:幾何相似度

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

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

定義3:屬性相似概率

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

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

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

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

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

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

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

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

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

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

根據(jù)公式

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

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

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

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

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

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

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

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

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

3 試驗及有效性分析

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

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

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

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

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

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

圖5(a)、(b)、(c)分別為利用PCA k-means、Euclid k-means以及HDsim k-means對iris數(shù)據(jù)集的聚類可視化結(jié)果,表2和表3分別為各聚類方法所用時間和精度的對比。圖6為zoo數(shù)據(jù)集的降維聚類可視化結(jié)果,表4和表5分別為利用二步聚類、Euclid k-means以及 HDsim k-means對zoo數(shù)據(jù)集的聚類所用時間和精度的對比。為便于可視化結(jié)果的對比,各方法降維結(jié)果均已進行歸一化。針對zoo數(shù)據(jù)集,由于PCA方法僅適用于變量之間存在一定相關(guān)性的數(shù)值型數(shù)據(jù)集的降維,而不能用于處理非線性數(shù)據(jù)和分類型數(shù)據(jù),因此,無法利用PCA k-means方法對zoo數(shù)據(jù)集進行降維聚類(降維結(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ù)集各算法聚類時間對比Tab.2 Consuming time of each clustering algorithm to data set iris s

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

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

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

3.3 試驗分析

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

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

4 結(jié) 論

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

[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ì)平,汪宏斌,汪誠波,等.基于模糊最近鄰的高維數(shù)據(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)召,朱揚勇.一種有效的量化交易數(shù)據(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].中國圖象圖形學(xué)報,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é)報,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é)報,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é)鵬,杜曉初,胡鵬.基于柵格距離變換的擴展對象空間聚類方法[J].測繪學(xué)報, 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.(郭慶勝,鄭春燕,胡華科.基于近鄰圖的點群層次聚類方法的研究[J].測繪學(xué)報, 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].計算機工程與應(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ì)量的評價方法[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

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

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

2010-03-10

2010-09-27

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

E-mail:wangjy@cae.cn