◇李慧敏 李 川 翟 祥

聚類作為一種無監(jiān)督的學(xué)習(xí)算法，被廣泛應(yīng)用于社會生活的各個領(lǐng)域。它的主要目的是對大量未知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)的內(nèi)在相似性劃分為多個類別，使類別內(nèi)的數(shù)據(jù)相似度較大，而類別間的數(shù)據(jù)相似度較小。傳統(tǒng)的聚類方法主要分為層次聚類和劃分式聚類：層次聚類將每一個樣本視為一個小類，自下而上將相似的兩類進(jìn)行合并，最終形成一個大類；劃分式聚類則將所有樣本視為一個類簇，通過不斷分裂這個大類簇形成各個小類。K-means算法是劃分式聚類里非常典型的一種聚類方法，由于其適用于大樣本的特點(diǎn)，被廣泛應(yīng)用于商業(yè)數(shù)據(jù)分析中，例如近來較為熱門的客戶畫像技術(shù)，就是利用K-means聚類技術(shù)建立一個標(biāo)簽體系來定義客戶的價值。

一、傳統(tǒng)聚類方法存在的問題

隨著信息技術(shù)日新月異的發(fā)展，大量的數(shù)據(jù)從各行各業(yè)產(chǎn)生，這些數(shù)據(jù)的數(shù)量和屬性個數(shù)同時以幾何倍數(shù)快速增長，K-means算法的應(yīng)用也因此而受到局限。原因主要有兩點(diǎn)：首先，在高維空間中，數(shù)據(jù)的分布具有高度的“稀疏性”和“空空間性”；其次，傳統(tǒng)的聚類方法是針對低維數(shù)據(jù)而設(shè)計(jì)的，當(dāng)數(shù)據(jù)上升到高維空間中時，傳統(tǒng)的聚類方法將失去其原本的性能。若仍采用傳統(tǒng)的聚類方法來分析數(shù)據(jù)間的關(guān)聯(lián)信息，將會出現(xiàn)如下幾個問題：

（一）相似性函數(shù)失去效用

傳統(tǒng)的聚類方法大多采用距離函數(shù)來度量相似性程度，在高維空間中，點(diǎn)與點(diǎn)之間的距離會隨著維度的增加而失去對比性，距離函數(shù)將會失去意義。

（二）類中心無法確定

在聚類過程中，一般使用平均距離確定每次迭代過程中的類簇中心點(diǎn)，在高維情況下，由各個類簇計(jì)算得到的均值就會非常接近，聚類過程受到阻礙從而無法確定最終類簇中心點(diǎn)所在的位置。

（三）計(jì)算過于復(fù)雜

維度上升必然會導(dǎo)致傳統(tǒng)聚類方法的計(jì)算量增加，效率降低，其應(yīng)用性也隨之受到限制。

由此可見，相似性函數(shù)的定義在聚類分析中占領(lǐng)著相當(dāng)重要的地位。高維空間中的聚類分析必須在獲得相似性度量方法的前提下進(jìn)行，因此，研究一個適用于高維數(shù)據(jù)的相似性函數(shù)具有非常重要的意義，也是目前急需解決的任務(wù)。

二、相似性度量方法的介紹

傳統(tǒng)的相似性度量指標(biāo)主要是圍繞距離函數(shù)而展開的。通常情況下，根據(jù)不同的應(yīng)用場景選取不同形式的相似度函數(shù)以便達(dá)到更好的描述效果。相似性指標(biāo)的選取直接決定了聚類結(jié)果的質(zhì)量。

（一）傳統(tǒng)的LP距離函數(shù)

假設(shè)空間中存在著由組成的n個數(shù)據(jù)樣本，其中，i=1，2，…，n，m為每個樣本點(diǎn)的屬性個數(shù)，即維度數(shù)。用數(shù)據(jù)集形式可表示為：

對于空間中的任意兩個樣本點(diǎn)：Xi=（Xi1，Xi2，…，Xim），Xj=（Xj1，Xj2，…，Xjm），定義距離函數(shù)如下：

這種度量LP被稱作范數(shù)，其中P是一個參數(shù)。當(dāng)p=1時，是曼哈頓距離；當(dāng)p=2時，是歐式距離；當(dāng)p趨向無窮時，則為切比雪夫距離。該函數(shù)在低維空間中能有較好的應(yīng)用效果，然而在高維空間中的表現(xiàn)結(jié)果是極不穩(wěn)定的。Aggarwal[1]認(rèn)為，對于滿足獨(dú)立同分布的一組數(shù)據(jù)點(diǎn)，采用范數(shù)作為高維空間中的距離函數(shù)時，點(diǎn)與點(diǎn)之間的距離將失去對比性，也就是說，高維空間中查詢點(diǎn)到所有點(diǎn)的距離都幾乎是相等的。在這種情況下，最近鄰點(diǎn)的查詢是不穩(wěn)定的，聚類算法的性能自然也會隨之下降。

（二）現(xiàn)有的相似性度量方法

關(guān)于相似性度量函數(shù)，現(xiàn)已有許多學(xué)者提出了相應(yīng)的改進(jìn)方法，主要包括函數(shù)PIDist（X，Y）[2]、NPsim（X，Y）[3]、Hsim（X，Y）[4]、Close（X，Y）[5]、Esim（X，Y）[6]、Gsim（X，Y）[7]、Psim（X，Y）[8]等。這些函數(shù)雖然能適用于高維空間，但是仍然存在著一些不足。

PIDist（X，Y）函數(shù)基于等深的思想度量兩個樣本的相似性，在面對方差較大的數(shù)據(jù)時應(yīng)用性受到限制。Hsim（X，Y）和Close（X，Y）函數(shù)對數(shù)據(jù)的量級不敏感，較難發(fā)現(xiàn)差值相同的兩個維度之間的區(qū)別，且在高維空間中不具有對比性。Esim（X，Y）函數(shù)是 Hsim（X，Y）和 Close（X，Y）函數(shù)的組合情況。Gsim（X，Y）函數(shù)的均值權(quán)重極奇不穩(wěn)定。Psim（X，Y）函數(shù)的取值則與維數(shù)有關(guān)，不同維數(shù)不具有可比性。這些函數(shù)共有的一點(diǎn)，就是忽略了噪聲維的影響，而且函數(shù)對數(shù)據(jù)的類型和分布都有著一定的要求。因此，難以廣泛應(yīng)用。

三、高維空間的特點(diǎn)

“維度災(zāi)難”最早是由Bellman[8]提出的，指對于一個含有多個變量的函數(shù)，隨著變量（維度）的增加，網(wǎng)格的數(shù)目會呈指數(shù)級增長，因此，想要在這個多維網(wǎng)格中去尋求最優(yōu)化的函數(shù)是不太可能的。高維空間中的聚類就是一個多變量求最優(yōu)的過程，必然會出現(xiàn)“維度災(zāi)難”的問題，這是高維空間的特殊性所決定的。

（一）稀疏性

在高維空間中，數(shù)據(jù)對象的分布具有“稀疏性”。假定d維空間中存在一個包含N個樣本點(diǎn)的數(shù)據(jù)集，并且該數(shù)據(jù)集中的每一維度相互獨(dú)立，均服從[0，1]均勻分布，可以認(rèn)為d維的數(shù)據(jù)集分布在一個超立方體單元中。若存在一個邊長為s的超立方體，那么對于任一樣本點(diǎn)而言，落在這個超立方體中的概率為Sd，其中s滿足條件0＜s＜1。顯然，隨著維度d的增加，這個概率值將會加速衰減，超立方體包含樣本點(diǎn)的可能性也會越來越小。例如，當(dāng)維度d=100時，僅有大約0.59%的數(shù)據(jù)落在邊長為0.95的超立方體中。

更進(jìn)一步，假定維度d=50，樣本點(diǎn)N=1012，數(shù)據(jù)服從均勻分布的情況下，若將空間中的每一個維度分成完全相等的兩部分，那么整個空間就被劃分為250個網(wǎng)格單元。此時，包含數(shù)據(jù)點(diǎn)的網(wǎng)格單元共有1012個，非空網(wǎng)格單元的個數(shù)僅占到總網(wǎng)格單元個數(shù)的0.08%。由此可見，高維空間中數(shù)據(jù)的分布存在高度的稀疏性，以至于聚類過程中較難形成簇。

（二）空空間性

對于一組服從正態(tài)分布的數(shù)據(jù)，其中心點(diǎn)到各樣本點(diǎn)之間的距離也服從正態(tài)分布。隨著維度的上升，超立方體單元的內(nèi)切球的體積會先增加后逐漸減小，如圖1。各樣本點(diǎn)普遍分布于該超立方體的邊角上，中心點(diǎn)附近沒有相鄰的點(diǎn)存在，這就是所謂的“空空間”現(xiàn)象。若用歐氏距離來衡量樣本點(diǎn)之間的距離，那么各樣本點(diǎn)到中心點(diǎn)的距離會隨維度的增加而增大，最小距離和最大距離的差異逐漸減少，歐氏距離失效，與之相對應(yīng)的聚類方法也失去效用。

圖1超立方體單元內(nèi)切球體積隨維度的變化情況

四、基于信息熵的相似性度量方法

在對高維數(shù)據(jù)進(jìn)行聚類分析時需要考慮到兩個問題：一方面，隨著維度的上升，數(shù)據(jù)點(diǎn)的分布通常會變得稀疏且遠(yuǎn)離中心，最近鄰距離失去意義；另一方面，對于一個由眾多屬性構(gòu)成的數(shù)據(jù)，影響其最終聚類結(jié)果畢竟只是那些少數(shù)的相關(guān)維，余下的噪聲維通常會掩蓋住數(shù)據(jù)真實(shí)的信息。本文針對這兩點(diǎn)，對距離函數(shù)進(jìn)行重新設(shè)計(jì)，提出了一種基于信息熵的相似度計(jì)量方法，即先通過信息熵篩選相關(guān)維，再根據(jù)選定的維來計(jì)算樣本之間的相似性。

（一）信息熵

信息熵反映的是具有確定概率的事件所傳遞的信息量。在概率論和數(shù)理統(tǒng)計(jì)中，隨機(jī)變量的取值是不確定的，但是服從某種概率分布，隨機(jī)變量的每個取值代表了一定的信息量，平均每個取值的信息量就是該隨機(jī)變量的信息熵。

假設(shè)一個隨機(jī)變量 X 在集合 S＝｛X1，X2，…，Xn}上取值，并且其概率分布 P（X）＝｛P1，P2，…，Pn}，那么，隨機(jī)變量 X 的信息熵是其所有取值的信息量的期望值，記為H（X），表達(dá)式為：

在聚類分析過程中，數(shù)據(jù)點(diǎn)是圍繞著簇中心進(jìn)行劃分的，簇的半徑越大說明這一類別的數(shù)據(jù)點(diǎn)分布得較為分散，簇的半徑越小則意味著數(shù)據(jù)點(diǎn)分布得更為緊密。從單個變量的角度而言，如果該維上相似程度較高的點(diǎn)分布得較為緊湊，而相似程度不高的點(diǎn)分布較為稀疏，那么聚類的結(jié)果就更好。因此，利用信息熵進(jìn)行維度篩選時，信息熵值越大的維就越有可能成為相關(guān)維。

假設(shè)空間中存在由n個樣本點(diǎn)形成的簇X，維數(shù)為m，用數(shù)據(jù)集形式表示如下：

利用信息熵篩選相關(guān)維的步驟如下：

1.將第i個維度對應(yīng)的變量值進(jìn)行排序，等寬分為k段，并統(tǒng)計(jì)每一段內(nèi)的樣本點(diǎn)個數(shù)，記為ni，同時得到每一段的概率值

2.根據(jù)信息熵的計(jì)算公式，依次計(jì)算各個維度的信息熵，記為 H=｛h1，h2，…，hm}；

3.將H的值按從大到小排列，選取前d個，生成一個二值向量 δi=｛δ1，δ2，…，δm}，其中 δi=1 的那些維即為滿足條件的相關(guān)維，也是后續(xù)進(jìn)入相似度計(jì)算的相應(yīng)屬性維。

（二）基于信息熵的相似性函數(shù)

一個優(yōu)良的相似性度量函數(shù)首先要在計(jì)量數(shù)據(jù)對象的相似性方面具有一定的對比性，易于索引，即能顯著區(qū)分不同的兩個數(shù)據(jù)點(diǎn)。此外，函數(shù)本身不能過于復(fù)雜，應(yīng)符合人們的思維習(xí)慣。因此，本文的設(shè)計(jì)思路如下：（1）在信息熵的分段前提下，依次計(jì)算各個維度下分段的寬度其中分別對應(yīng)第i個維度下的最大值和最小值；（2） 若滿足 Xi－yi＜Ri，則認(rèn)為樣本點(diǎn)在維度i上具有相似性，權(quán)重yi=1，否則默認(rèn)yi=0。

設(shè)計(jì)的相似性函數(shù)如下：

上式中，Xi和Yi分別代表兩個樣本點(diǎn)X和Y在第i維的取值，δi和yi均為二值向量，d為通過信息熵選取的有效維數(shù)，Uik和lik則分別對應(yīng)于第i個維度下k個分段的上下界值。

K-Ensim相似性函數(shù)具有如下幾點(diǎn)性質(zhì)：

1.函數(shù)在經(jīng)過信息熵篩選后的維度上計(jì)量相似性。

2.函數(shù)只統(tǒng)計(jì)相似性較高的維度。樣本點(diǎn)在同一維上的差值只有在同一分段內(nèi)，在該維上才被視為具有相似性。

3.函數(shù)引入了Uik-lik這一差值的處理，使得樣本點(diǎn)的相似性在不同維度不同分段均具有可比性。

4.函數(shù)的取值范圍為[0，1]，值越大，相似性越高。

（三）高維空間的穩(wěn)定性分析

為了驗(yàn)證K-Ensim函數(shù)在高維空間中的穩(wěn)定性，利用MATLAB的隨機(jī)函數(shù)按照不同的維數(shù)生成數(shù)據(jù)對象各1000條，其中每一維度都是獨(dú)立的，且服從正態(tài)分布。衡量標(biāo)準(zhǔn)如下：

其中，Dmaxd、Dmind和Davgd分別為d維空間中數(shù)據(jù)點(diǎn)到原點(diǎn)的最大距離、最小距離以及平均距離。

圖2 比值Ratio隨維度的變化情況

從圖2中可以看到，隨著維度的增加，上述比值是逐漸上升的，當(dāng)維度很高時，比值能穩(wěn)定在一個非零的常數(shù)水平。這說明K-Ensim函數(shù)在高維空間中能區(qū)分最近鄰距離和最遠(yuǎn)鄰距離，穩(wěn)定性得以驗(yàn)證。

表1 基于歐氏距離的聚類結(jié)果

表2 基于Ensim函數(shù)的聚類結(jié)果

五、仿真實(shí)驗(yàn)結(jié)果及分析

為了進(jìn)一步驗(yàn)證K-Ensim函數(shù)在高維聚類分析中的有效性，從UCI數(shù)據(jù)庫上選取了測試數(shù)據(jù)集Wine，通過仿真實(shí)驗(yàn)來對比歐氏距離和Ensim相似函數(shù)在算法應(yīng)用上的性能差異。Wine數(shù)據(jù)集共有178個數(shù)據(jù)樣本，分為三類，各類的樣本數(shù)分別是59、71和48，每條樣本均有13個屬性。此次實(shí)驗(yàn)選取k-means聚類算法，采用歐式距離和K-Ensim函數(shù)作為相似性函數(shù)分別進(jìn)行聚類。兩種算法所得結(jié)果如下：

綜合表1、表2的情況看，基于K-Ensim相似函數(shù)的聚類算法得到了相對較好的聚類效果，整體準(zhǔn)確率提高了10.67%。表2利用信息熵篩選了9個變量進(jìn)入相似度的計(jì)算，算法劃分的結(jié)果與數(shù)據(jù)集實(shí)際的分布更為接近，每一類的準(zhǔn)確率都得到了顯著提高，尤其在區(qū)分第三類上表現(xiàn)最為明顯。實(shí)驗(yàn)結(jié)果表明本文提出的Ensim改進(jìn)函數(shù)不僅能合理地度量高維數(shù)據(jù)之間的相似程度，而且能有效地應(yīng)用于高維數(shù)據(jù)的聚類分析。

六、結(jié)語

本文從聚類分析著手，以經(jīng)典的K-means算法為例，通過對傳統(tǒng)的聚類方法在高維空間中存在的問題進(jìn)行分析，得到改進(jìn)相似性函數(shù)的必然性和迫切性。針對高維空間中數(shù)據(jù)分布存在稀疏性和空空間的特性，文中設(shè)計(jì)了一種基于信息熵的相似性度量方法，該方法通過信息熵篩選相關(guān)維，然后將每個維度進(jìn)行等分，得到各個維度下的固定段長，只統(tǒng)計(jì)差值處于同一段長內(nèi)的相似性。改進(jìn)的相似性度量函數(shù)更具優(yōu)勢：它不僅能緩解高維所帶來的影響，還能使聚類算法的精度得到顯著的提升。

[1]Aggarwal C C.Re-designing distance functions and distance based applications for high dimensional data[J].Acm Sigmod Record， 2001（01）.

[2]Aggarwal C C，Yu PS.The IGrid index:reversing the dimensionality curse for similarity indexing in high dimensional space[C].ACM SIGKDD International Conference on Knowledge Discovery&Data Mining.ACM，2000.

[3]Li W，Wang G，Li K，et al.Similarity measurement method of high-dimensional data based on normalized net lattice subspace[J].Chinese High Technology Letters， 2017（02）.

[4]楊風(fēng)召，朱揚(yáng)勇.一種有效的量化交易數(shù)據(jù)相似性搜索方法[J].計(jì)算機(jī)研究與發(fā)展，2004（02）.

[5]邵昌昇，樓巍，嚴(yán)利民.高維數(shù)據(jù)中的相似性度量算法的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011（02）.

[6]王曉陽，張洪淵，沈良忠，等.基于相似性度量的高維數(shù)據(jù)聚類算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013（05）.

[7]黃斯達(dá)，陳啟買.一種基于相似性度量的高維數(shù)據(jù)聚類算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件，2009（09）.

[8]趙恒.數(shù)據(jù)挖掘中聚類若干問題研究[D].西安：西安電子科技大學(xué)，2005.