高維空間數(shù)據(jù)灰色凸關(guān)聯(lián)度聚類算法仿真

楊成義,熊才權(quán)

(1. 廣東理工學(xué)院信息技術(shù)學(xué)院,廣東 肇慶 526100;2. 湖北工業(yè)大學(xué)計算機(jī)學(xué)院,湖北 武漢 430068)

1 引言

由于受到維度災(zāi)難等多方面因素的影響,為數(shù)據(jù)聚類提出了全新的挑戰(zhàn)[1-2],高維空間數(shù)據(jù)聚類成為當(dāng)前數(shù)據(jù)處理技術(shù)研究的主要內(nèi)容。聚類分析主要是通過相似度將數(shù)據(jù)集中的各個對象劃分為多個不同的類或者簇。目前,已經(jīng)出現(xiàn)大量比較完善的低維數(shù)據(jù)聚類算法,但是由于受到“維數(shù)災(zāi)難效應(yīng)”的影響,導(dǎo)致對低維數(shù)據(jù)有效的聚類算法常常對高維數(shù)據(jù)失效,而高維數(shù)據(jù)一直占據(jù)主要地位,所以研究高維數(shù)據(jù)聚類問題是重中之重。

武森等人[3]通過調(diào)整參數(shù)對原始稀疏差異度展開拓展處理,同時采用位集的方式完成數(shù)據(jù)聚類。朱穎雯等人[4]將隨機(jī)投影和自適應(yīng)諧振理論兩者有效結(jié)合實現(xiàn)數(shù)據(jù)流聚類處理。萬靜等人[5]優(yōu)先在高維數(shù)據(jù)集中選擇合適的維度構(gòu)建子空間,然后建立混合網(wǎng)絡(luò);最后利用子空間的相似度和相異度對數(shù)據(jù)維度實施剪枝處理,確保子空間密度得到大幅度提升,實現(xiàn)數(shù)據(jù)聚類處理。以上幾種算法都取得了比較好的結(jié)果,但是聚類時間比較長,聚類結(jié)果也不是十分準(zhǔn)確。為此,結(jié)合灰色凸關(guān)聯(lián)度提出一種全新的聚類算法。經(jīng)實驗對比分析可知,所提算法能夠獲取高效率以及高精度的聚類結(jié)果。

2 一種高維空間數(shù)據(jù)聚類算法

2.1 高維空間數(shù)據(jù)去噪

對于二維數(shù)據(jù),對應(yīng)的正離散系統(tǒng)行為序列H可以表示為以下形式

(1)

式中,m代表行數(shù);n代表列數(shù)。

(2)

式中,?a代表灰色凸關(guān)聯(lián)度系數(shù);ci代表灰色關(guān)聯(lián)序列。當(dāng)該矩陣屬于半正定矩陣,則說明全部的主子式大于等于0,同時對應(yīng)點所在的位置是凸的,也可以將其稱為該點的凸度,將凸度看作包含分量的向量。假設(shè)隨機(jī)兩個對象在某一個點的凸度越接近,則說明兩者的關(guān)聯(lián)度就越大。

結(jié)合灰色凸關(guān)聯(lián)度組建一種可以降低噪聲的截斷冪基三次樣條函數(shù)模型K(S),如式(3)所示

(3)

從模型的表達(dá)式來看,主要通過約束條件來控制高維空間中噪聲數(shù)據(jù)的變化情況。結(jié)合相關(guān)先驗知識可知,當(dāng)噪聲使近似函數(shù)曲線的波動量以及曲率變化和凸變化率比較明顯時,需要引入懲罰向量,以此降低弱噪聲對曲線擾動產(chǎn)生的影響,確保離散數(shù)據(jù)的函數(shù)曲線更加平滑。

為了有效降低噪聲對系統(tǒng)因素間實際關(guān)系的影響,組建包含噪聲數(shù)據(jù)灰色樣條絕對關(guān)聯(lián)度模型,通過模型去除數(shù)據(jù)中的噪聲[6-7],詳細(xì)的操作步驟如下所示:

1)通過截斷冪基三次樣條函數(shù)對離散噪聲數(shù)據(jù)展開插值處理,同時對K(S)展開極小化處理,得到與之對應(yīng)的系數(shù)矩陣

(4)

2)通過截斷冪基樣條函數(shù)的連續(xù)性展開相關(guān)計算。

3)通過構(gòu)建的模型對高維空間數(shù)據(jù)去噪處理,得到去噪后的數(shù)據(jù),如式(5)所示

(5)

2.2 高維空間數(shù)據(jù)聚類

簇類合并的重要依據(jù)即為相似度計算,各個數(shù)據(jù)集在子空間聚類的過程中[8-9],會存在不同程度的差異,比較明顯的差異就是子空間的大小不等。在計算隨機(jī)簇類相似度問題的過程中,需要優(yōu)先考慮任意兩個簇類在子空間并集上的相似度,以此為依據(jù)可以獲取簇類不同屬性,確保簇類的屬性可以和子空間的并集相對應(yīng)。

簇類不僅僅用來記錄全部數(shù)據(jù)集中的相關(guān)元素,同時還能夠記錄子空間的相關(guān)信息和各個簇類對應(yīng)的信息表。另外,在實際計算的過程中,需要重點維護(hù)和管理最相似線性表,它主要負(fù)責(zé)計算不同簇類之間的相似度。

在高維空間的基礎(chǔ)上組建信息表,子空間內(nèi)的各個簇會隨著元素的不斷調(diào)整而實時更新。設(shè)定數(shù)據(jù)集E中包含p個數(shù)據(jù),則子空間內(nèi)隨機(jī)兩個數(shù)據(jù)的相似度Sim(x,y)為

(6)

式中,xt、yt和zt分別代表不同類型數(shù)據(jù)的屬性值。

在實行簇類合并的過程中,需要計算不同簇類之間的相似度,同時將其比較,選擇相似度最高的兩個簇類合并處理,以此為依據(jù)建立最相似線性表,為后續(xù)數(shù)據(jù)聚類奠定堅實的理論基礎(chǔ)。

在實際計算時,需要實時定位各個簇所在的具體坐標(biāo)位置,同時準(zhǔn)確區(qū)分各個簇,并對各個簇編號,方便后續(xù)的處理和研究。

通過上述分析,引入信息熵,設(shè)定信源為U,則對應(yīng)的概率空間可以表示為式(7)的形式

(7)

式中,U代表概率矢量;t(u)代表概率矢量的元函數(shù)。

對應(yīng)的信息熵計算公式為

(8)

式中,D(x)代表信息熵。

設(shè)定所給定的分類數(shù)據(jù)集為R,各個數(shù)據(jù)包含d個屬性。將全部數(shù)據(jù)集歸類到設(shè)定的類中,則第i個類對應(yīng)的屬性域lj中各個值的概率?i(j)可以表示為式(9)的形式

(9)

式中,qi(lj,i)代表數(shù)據(jù)集不確定性度量;Fi,j代表數(shù)據(jù)集中各個數(shù)據(jù)的離散程度。

通過相關(guān)的先驗知識可知,不同數(shù)據(jù)集中的數(shù)據(jù)對象屬性是完全獨立的,則第i類的信息熵D(xi)可以表示為:

(10)

式中,平均信息熵可以表示為式(11)的形式

(11)

對于高維空間的數(shù)據(jù)而言,傳統(tǒng)的相異度量公式并不適用,需要設(shè)定一個全新的數(shù)據(jù)集和全新的維度,為各個類尋找對應(yīng)的子空間,同時構(gòu)建目標(biāo)函數(shù),確保目標(biāo)函數(shù)的取值最小化,詳細(xì)的操作步驟如下所示:

1)在計算的初始階段:需要選擇相異度取值較大的多個數(shù)據(jù)集對象,主要借助貪婪算法實現(xiàn),同時還需要將數(shù)據(jù)集中剩余部分的數(shù)據(jù)全部劃分到對應(yīng)的類別中[10-11]。

在選取數(shù)據(jù)對象的過程中會消耗大量的時間,所以在貪婪算法的基礎(chǔ)上加入ESCHCD抽樣,確保計算時間得到大幅度降低。在原始數(shù)據(jù)集E中抽取樣本S(|S|?|E|),同時在S中通過貪婪算法選擇差異度比較大的n個數(shù)據(jù)對象。加入抽樣方法之后,在確保計算精度的情況下,還可以有效提升計算效率。

通過式(12)計算得到樣本集S的大小

(12)

經(jīng)過選擇得到相異度比較大的數(shù)據(jù)后,需要借助距離公式將全部數(shù)據(jù)集歸類到以n個數(shù)據(jù)為中心點的類中,同時將其劃分到相應(yīng)類別中,直至數(shù)據(jù)集E中的數(shù)據(jù)全部劃分到對應(yīng)的類中。

2)優(yōu)化階段:

當(dāng)高維空間中的數(shù)據(jù)集完成劃分處理后[12],得到對應(yīng)的初始劃分結(jié)果,以初始劃分結(jié)果為依據(jù)展開相關(guān)計算,獲取對應(yīng)類的子空間;同時在迭代尋優(yōu)的過程中如果數(shù)據(jù)持續(xù)發(fā)生變化則繼續(xù)計算;反之,則停止迭代,實現(xiàn)優(yōu)化的主要目的就是查找子空間同時完成迭代尋優(yōu)。

ESCHCD是現(xiàn)階段使用比較廣泛的一種聚類方法,同時還可以確定子空間的具體大小。子空間的成員以及大小全部是由子空間的平均熵值和噪聲子空間的平均熵綜合確定。通過數(shù)據(jù)集的歸類以及維度信息熵的計算公式,可以獲取數(shù)據(jù)集在不同類別和屬性信息中對應(yīng)的信息熵,同時還可以將不同類中各個屬性的熵值保存在矩陣Qk×d中,則有

(13)

式中,Qk(d)代表矩陣中的子元素。

將式(13)中的值進(jìn)行標(biāo)準(zhǔn)化處理,確保其在區(qū)間[0,1]內(nèi),則有

(14)

式中,maxi和mini代表最大值和最小值,stdQi(j)代表標(biāo)準(zhǔn)化矩陣;Qi(j)代表噪聲屬性集合。

結(jié)合子空間的聚類特征和信息熵的相關(guān)定義可知,當(dāng)熵的取值越小,則說明關(guān)系越緊密,相異性越小。

將隨機(jī)兩個子空間的距離設(shè)定子空間搜索的目標(biāo)函數(shù)Func(x,y),如式(15)所示

(15)

在選擇子空間的過程中,需要考慮多方面的問題,主要和數(shù)據(jù)集相關(guān)的子空間以及數(shù)據(jù)在剩余空間的表現(xiàn)情況。引入子空間選擇方法建立在不同類型數(shù)據(jù)成員的整體概率分布G(a,b,c),如式(16)所示

(16)

隨機(jī)設(shè)定一個類的數(shù)據(jù)成員,確保目標(biāo)函數(shù)的取值最小,即將之前沒有轉(zhuǎn)移的目標(biāo)函數(shù)值轉(zhuǎn)移到后面的目標(biāo)函數(shù)中。在判斷一個隨機(jī)類中的數(shù)據(jù)是否轉(zhuǎn)移到另外一個類時,只需要判斷是否滿足需求即可。假設(shè)滿足則轉(zhuǎn)移,反之則不轉(zhuǎn)移。其中特別說明,將迭代尋優(yōu)過程中的目標(biāo)函數(shù)轉(zhuǎn)換為不等式可以有效降低迭代尋優(yōu)過程中的計算量以及時間。

分別對不同類中的各個數(shù)據(jù)樣本展開掃描處理,將不等式作為判斷依據(jù),判斷數(shù)據(jù)是否可以轉(zhuǎn)移到其它的類別中。假設(shè)隨機(jī)一次遍歷結(jié)束之后,需要將全部數(shù)據(jù)轉(zhuǎn)移到其它類中,則在此次遍歷結(jié)束之后可以獲取優(yōu)化后的全新歸類,對全新的歸類展開子空間選擇,得到全新的子空間;再次展開遍歷處理,當(dāng)完成遍歷之后沒有數(shù)據(jù)可以轉(zhuǎn)移,則停止計算,輸出最優(yōu)歸類以及其對應(yīng)的子空間,同時得到最小目標(biāo)函數(shù),實現(xiàn)高維空間數(shù)據(jù)聚類處理[13-15]。

3 仿真研究

通過一系列的仿真驗證所提基于灰色凸關(guān)聯(lián)度的高維空間數(shù)據(jù)聚類算法的有效性,通過MATLAB仿真軟件模擬生成6組200×10的數(shù)據(jù)集,數(shù)據(jù)集是由多個屬性不同以及類型不同的樣本構(gòu)成,其中全部數(shù)據(jù)集共包含6種不同類型的數(shù)據(jù)。其中,不同類型數(shù)據(jù)集的具體特征可以表示為表1的形式:

表1 不同測試數(shù)據(jù)集的具體特征描述

隨機(jī)選擇兩個數(shù)據(jù)集展開實驗測試,通過圖1獲取數(shù)據(jù)樣本集在高維空間中的分布情況:

圖1 數(shù)據(jù)集在樣本空間的分布情況

通過圖2給出所提方法獲取的數(shù)據(jù)聚類結(jié)果:

圖2 高維空間數(shù)據(jù)集聚類結(jié)果分析圖

分析圖2中的實驗數(shù)據(jù)可知,在實驗過程中,所提算法獲取的聚類結(jié)果具有比較強(qiáng)的穩(wěn)定性,可以獲取比較滿意的聚類結(jié)果,同時可以精準(zhǔn)聚類出對應(yīng)的類別數(shù)。

以下實驗測試對不同聚類算法的時間復(fù)雜度展開分析,利用圖3給出具體的實驗結(jié)果。

圖3 不同聚類算法的時間復(fù)雜度測試結(jié)果對比

通過圖3可以看出,相比另外幾種聚類算法,所提算法所使用的時間明顯更少一些,說明所提算法可以以較快的速度完成聚類。

4 結(jié)束語

高維數(shù)據(jù)聚類是現(xiàn)階段大數(shù)據(jù)挖掘時代的重要技術(shù)和方法,傳統(tǒng)的數(shù)據(jù)聚類方法已經(jīng)發(fā)展得十分成熟,但是仍然存在一系列的問題。為此,提出基于灰色凸關(guān)聯(lián)度的高維空間數(shù)據(jù)聚類算法。經(jīng)過詳細(xì)的實驗數(shù)據(jù)對比分析可知,所提算法獲取的數(shù)據(jù)聚類結(jié)果具有較高的精度,同時整體的計算時間也明顯更低一些,全面驗證了在時間復(fù)雜度分析方面的優(yōu)勢。

由于受到時間限制,導(dǎo)致所提算法存在大量的不足,后續(xù)將針對以下幾方面內(nèi)容展開更加深入的研究:

1)分別將不同的優(yōu)化算法引入到迭代尋優(yōu)中,選擇性能最佳的優(yōu)化算法。

2)將其廣泛應(yīng)用于不同的研究領(lǐng)域內(nèi),為后續(xù)的研究提供全新的思路。