陳曉潔，王雯娟

（龍巖學(xué)院　信息工程學(xué)院，福建　龍巖　364012）

特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法比傳統(tǒng)算法的優(yōu)越性分析

陳曉潔，王雯娟

（龍巖學(xué)院信息工程學(xué)院，福建龍巖364012）

聚類(lèi)算法在當(dāng)前的各個(gè)領(lǐng)域都有著非常廣泛的應(yīng)用，常見(jiàn)的有生物學(xué)和醫(yī)學(xué)領(lǐng)域的數(shù)據(jù)探測(cè)、信息檢索以及文本挖掘和圖像處理等.尤其是目前隨著計(jì)算機(jī)信息技術(shù)的發(fā)展，數(shù)據(jù)的規(guī)模比以往更大，數(shù)據(jù)挖掘工作需要的數(shù)據(jù)特征維數(shù)大大增加.導(dǎo)致高維數(shù)特征加權(quán)和選擇面臨多學(xué)科交叉的問(wèn)題，大大增加了空間聚類(lèi)分析的工作難度.本文將分析特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法，并將其與傳統(tǒng)算法進(jìn)行了對(duì)比，總結(jié)了其優(yōu)越性.

特征加權(quán)；優(yōu)化軟子空間；聚類(lèi)算法；傳統(tǒng)算法

隨著信息技術(shù)的快速發(fā)展，人們?cè)谌粘５墓ぷ鬟^(guò)程中，能夠更加方便和快捷的采集到數(shù)據(jù)資源，這就使得數(shù)據(jù)集群更加龐大和復(fù)雜.高維數(shù)據(jù)比低維數(shù)據(jù)在空間中存在很多不相關(guān)的屬性，并具有明顯的維度效應(yīng).利用聚類(lèi)分析算法，能夠提高數(shù)據(jù)內(nèi)部結(jié)構(gòu)的識(shí)別能力，發(fā)現(xiàn)不同區(qū)域的疏密度，從而確定空間的分布模式和數(shù)據(jù)關(guān)系.在計(jì)算機(jī)以及人工智能領(lǐng)域，該算法模式逐漸成為人們研究對(duì)象，為各個(gè)領(lǐng)域的相關(guān)工作提供了極大的便利性.但是隨著目前數(shù)據(jù)規(guī)模的不斷擴(kuò)大以及數(shù)據(jù)特征的多樣性明顯增強(qiáng)，在數(shù)據(jù)挖掘的過(guò)程中，不僅需要依賴(lài)統(tǒng)計(jì)學(xué)、計(jì)算機(jī)以及數(shù)學(xué)模型等，還得了解生物學(xué)、醫(yī)學(xué)和經(jīng)濟(jì)學(xué)等相關(guān)的學(xué)科背景.在傳統(tǒng)的聚類(lèi)分析算法中，存在著較大的缺陷型，尤其是在如何自動(dòng)確定數(shù)據(jù)集的簇?cái)?shù)、高維數(shù)據(jù)集的特征相似度等方面.但是鑒于聚類(lèi)算法在各個(gè)領(lǐng)域的廣泛應(yīng)用，為了提高空間聚類(lèi)分析的質(zhì)量，需要對(duì)傳統(tǒng)的算法進(jìn)行改進(jìn).經(jīng)過(guò)近幾年的研究，針對(duì)高維數(shù)據(jù)提出了很多聚類(lèi)分析方法，本文主要介紹最具代表性的子空間聚類(lèi)算法.

1　聚類(lèi)分析過(guò)程及要求

聚類(lèi)分析的過(guò)程為：做好分析數(shù)據(jù)的準(zhǔn)備工作——篩選出有效特征，并將此特征存在矢量中——將數(shù)據(jù)的特征提取出來(lái)——選擇合理的距離函數(shù)，并利用此函數(shù)對(duì)特征進(jìn)行聚類(lèi)——對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)、測(cè)試.

在不同的應(yīng)用領(lǐng)域中，對(duì)聚類(lèi)分析的要求也有所差異.不過(guò)總體來(lái)說(shuō)，聚類(lèi)分析過(guò)程應(yīng)該要滿(mǎn)足以下要求：第一，所選用的聚類(lèi)空間算法必須有良好的伸縮性，也就是說(shuō)能夠根據(jù)計(jì)算要求以及數(shù)據(jù)特點(diǎn)進(jìn)行擴(kuò)展或收縮；第二，對(duì)于不同的數(shù)據(jù)類(lèi)型，要有相應(yīng)的處理能力，才能很好地完成不同種數(shù)據(jù)的聚類(lèi)分析；第三，由于單個(gè)的簇形狀并不固定，因此首先要提出能夠識(shí)別不同形狀簇的聚類(lèi)算法，才能實(shí)現(xiàn)有效聚類(lèi)；第四，如果在數(shù)據(jù)的錄入過(guò)程中，出現(xiàn)了人為操作不良而導(dǎo)致的失誤，或者數(shù)據(jù)出現(xiàn)異常，聚類(lèi)算法要對(duì)噪聲數(shù)據(jù)進(jìn)行及時(shí)的處理；第五，在聚類(lèi)過(guò)程中，由于需要輸入很多的信息參數(shù)，占據(jù)很大一部分空間，所以要選擇輸入?yún)?shù)的領(lǐng)域知識(shí)最小的聚類(lèi)算法；第六，鑒于傳統(tǒng)的聚類(lèi)算法不能在高維度空間中聚類(lèi)數(shù)據(jù)對(duì)象，要對(duì)算法進(jìn)行改進(jìn)，從而找到更加高效的聚類(lèi)算法；第七，在實(shí)際應(yīng)用過(guò)程中，聚類(lèi)算法會(huì)受到不同程度的約束條件，為了保證計(jì)算過(guò)程中的順利性，需要找到基于約束的聚類(lèi)算法；第八，通過(guò)聚類(lèi)算法獲得的聚類(lèi)結(jié)果必須具備可解釋性、可用性以及可理解性［1］.

2　軟子空間與硬子空間聚類(lèi)算法的對(duì)比

子空間聚類(lèi)算法是指在高維數(shù)據(jù)空間中挖掘存在于某些低維子空間中簇類(lèi)的技術(shù).利用該方法能夠把集群數(shù)據(jù)劃分成多個(gè)簇類(lèi)，然后從中找到集群數(shù)據(jù)中每個(gè)簇類(lèi)相對(duì)應(yīng)的子空間.根據(jù)維度屬性的不同，每個(gè)簇類(lèi)都能賦予其相應(yīng)的權(quán)值，權(quán)值主要表示和簇類(lèi)之間的相關(guān)程度.在以往的研究過(guò)程中，將子空間聚類(lèi)方法分成了兩種基本類(lèi)型，包括硬子空間聚類(lèi)和軟子空間聚類(lèi)［2］.其中，硬子空間聚類(lèi)方法在聚類(lèi)過(guò)程中能夠賦予簇類(lèi)不同維度屬性的權(quán)值系數(shù)是0和1，分別表示屬性和簇類(lèi)的相關(guān)度.軟子空間聚類(lèi)和硬子空間聚類(lèi)的最大區(qū)別在于，在聚類(lèi)過(guò)程中能夠賦予簇類(lèi)各維度屬性更多權(quán)值，權(quán)值范圍是［0，1］.這樣一來(lái)，軟子空間聚類(lèi)一方面反映了屬性和簇是否具備相關(guān)性，另一方面也明確了各自的相關(guān)程度.因?yàn)閮煞N子空間聚類(lèi)算法的這一差別，軟子空間聚類(lèi)算法成為近年來(lái)數(shù)據(jù)挖掘領(lǐng)域非常重要的研究對(duì)象.但是，很多新的軟子空間聚類(lèi)算法仍然具有較大的局限性，因?yàn)樗鼈冎饕轻槍?duì)數(shù)據(jù)集群的劃分方法進(jìn)行的優(yōu)化，而忽略了各簇類(lèi)所在子空間的優(yōu)化，這就大大降低了數(shù)據(jù)計(jì)算的效率以及聚類(lèi)的精確性.本文提出一種基于特征加權(quán)優(yōu)化的軟子空間聚類(lèi)算法，簡(jiǎn)稱(chēng)SCFO算法，應(yīng)用對(duì)象是高維數(shù)據(jù)的聚類(lèi)分析.該算法的應(yīng)用優(yōu)勢(shì)為：在聚類(lèi)過(guò)程中，不僅實(shí)現(xiàn)了數(shù)據(jù)集群的連續(xù)劃分，還能完成不同簇類(lèi)子空間的優(yōu)化.除此之外，用戶(hù)除了需要輸入簇類(lèi)數(shù)之外，不用再輸入其它的參數(shù).經(jīng)過(guò)大量的應(yīng)用實(shí)踐證明，該聚類(lèi)算法具有更好的聚類(lèi)效果［3］.

3　特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法的優(yōu)越性分析

3.1FSC算法

與傳統(tǒng)的聚類(lèi)方法相比，軟子空間聚類(lèi)法充分考慮了屬性和簇類(lèi)的相關(guān)性，在聚類(lèi)過(guò)程中，會(huì)給簇類(lèi)張每個(gè)維度屬性一個(gè)權(quán)值，這些權(quán)值各不相同，每一個(gè)都代表著一種與簇類(lèi)的相關(guān)性.利用軟子空間聚類(lèi)算法，就能夠利用特征權(quán)值來(lái)識(shí)別每個(gè)子空間中的簇類(lèi)［4］.

首先對(duì)全文使用符號(hào)含義進(jìn)行說(shuō)明：

DB=｛x1，…，x1，…，xN｝表示數(shù)據(jù)集；

V=｛xkj｝C×D表示簇類(lèi)中心矩陣；

U=｛uki｝C×N表示隸屬度矩陣；

W=｛wkj｝C×D表示權(quán)值矩陣；

其中，C表示簇組數(shù)，D表示數(shù)據(jù)集中樣本點(diǎn)的維數(shù)，xij表示樣本xi的第j維屬性值（j=1，2，…，D），vkj是第k個(gè)簇中心點(diǎn)的第j維屬性值，uki表示第i個(gè)樣本對(duì)第k類(lèi)簇的隸屬度，wkj表示第j維屬性和第k個(gè)簇類(lèi)之間的相關(guān)程度，其中，當(dāng)wkj的值更大時(shí)，表示兩者之間的相關(guān)性更強(qiáng).

有研究學(xué)者提出了一種新的聚類(lèi)算法FSC，這種算法多應(yīng)用在高維度的數(shù)據(jù)聚類(lèi)處理中.FSC給模糊權(quán)值進(jìn)行定義，并將模糊權(quán)值帶入到函數(shù)中去，得到以下目標(biāo)函數(shù)：

在上述公式中，引入ε0的作用是防止FSC算法在聚類(lèi)過(guò)程中會(huì)出現(xiàn)除以零的錯(cuò)誤，τ表示模糊因子.FSC算法的模糊權(quán)值更新方式和模糊K-均值聚類(lèi)算法的模糊隸屬度的加權(quán)方法類(lèi)似.除此之外，在同一簇類(lèi)中，賦予每一維屬性的權(quán)值和該屬性上的數(shù)據(jù)分散程度呈反比，也就是說(shuō)，數(shù)據(jù)越分散，被賦予的權(quán)值就越小，數(shù)據(jù)越集中，被賦予的權(quán)值就越大.FSC算法首先對(duì)簇中心進(jìn)行初始化，然后連續(xù)更新權(quán)值矩陣W和聚類(lèi)中心矩陣V，等到滿(mǎn)足條件之后，就會(huì)自動(dòng)結(jié)束.軟子空間聚類(lèi)算法就是在FSC算法的基礎(chǔ)上研究出來(lái)［5］.

3.2特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法

3.2.1目標(biāo)優(yōu)化函數(shù)

在軟子空間聚類(lèi)算法之中，特征加權(quán)有以下特點(diǎn)：在同一個(gè)簇類(lèi)中，權(quán)值與其所屬維度的數(shù)據(jù)分散程度是反比例關(guān)系，這就說(shuō)明當(dāng)維度屬性權(quán)值越大時(shí)，對(duì)簇類(lèi)的重要性就越強(qiáng).也就是說(shuō)，特征權(quán)值的分布越是集中，就越能體現(xiàn)簇類(lèi)所在的子空間越優(yōu)化.當(dāng)wk1+wk2+…+wkD=1時(shí)，可以用以下公式來(lái)分析權(quán)值的分布情況：

分析上述公式可以發(fā)現(xiàn)，特征權(quán)值的分布越是均勻，fw和dk的值數(shù)就越小.跟一般的傳統(tǒng)聚類(lèi)算法相似的是，當(dāng)各個(gè)屬性和簇類(lèi)的重要程度一樣時(shí)，fw和dk能夠獲得最小值.根據(jù)公式（1），可以得到以下目標(biāo)函數(shù)：

其中，目標(biāo)函數(shù)的第1項(xiàng)是加權(quán)的簇內(nèi)緊湊度之和；系數(shù)rk的作用是平衡簇內(nèi)的緊湊度以及特征權(quán)值分布對(duì)目標(biāo)函數(shù)的具體影響.

3.2.2特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法算法過(guò)程及分析

具體算法描述如下：

輸入：簇類(lèi)個(gè)數(shù)C；然后隨機(jī)選擇C個(gè)初始聚類(lèi)中心，然后把所有的特征權(quán)值的初始值都設(shè)置為1/D.

重復(fù)：根據(jù)上述公式，更新隸屬度矩陣U，簇類(lèi)中心矩陣V，權(quán)值矩陣W.

算法結(jié)束：直到目標(biāo)函數(shù)值達(dá)到最下值或者V和W這兩個(gè)參數(shù)在計(jì)算過(guò)程中相鄰兩次的變化比給定的闕值小.輸出：將聚類(lèi)中心矩陣V以及隸屬度矩陣U輸出.

特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法采用了和k-均值聚類(lèi)相似的算法，將計(jì)算權(quán)值特征的具體步驟增加到聚類(lèi)過(guò)程中，還重新定義了每個(gè)計(jì)算步驟使用的公式.也就是說(shuō)，該算法極大了保留了k-均值聚類(lèi)算法的特性.假如要進(jìn)行P次的循環(huán)迭代才能夠滿(mǎn)足S軟子空間聚類(lèi)算法的結(jié)束條件，那么每個(gè)步驟都能夠獲得算法的時(shí)間復(fù)雜度都是0.由此可以證明，該算法和k-均值聚類(lèi)算法在計(jì)算時(shí)間上的復(fù)雜性一樣［6］.

4　結(jié)論

子空間聚類(lèi)算法其實(shí)就是傳統(tǒng)的聚類(lèi)算法與特征選擇技術(shù)的結(jié)合，在進(jìn)行聚類(lèi)劃分時(shí)，得到了與各個(gè)數(shù)據(jù)簇相對(duì)應(yīng)的特征子集，也可以稱(chēng)作是特征權(quán)重.這樣一來(lái)，就能為各個(gè)數(shù)據(jù)簇找到相對(duì)應(yīng)的特征子空間.其中，利用子空間的聚類(lèi)技術(shù)能夠根據(jù)數(shù)據(jù)集子空間的不同，找到與之對(duì)應(yīng)的數(shù)據(jù)簇.由于子空間聚類(lèi)算法又可以分為硬子空間聚類(lèi)和軟子空間聚類(lèi)，經(jīng)過(guò)實(shí)踐表明，軟子空間聚類(lèi)算法的實(shí)用性更強(qiáng).但是傳統(tǒng)的軟子空間聚類(lèi)算法具有較大的缺陷型，因此，本文對(duì)其進(jìn)行了優(yōu)化，基于特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法比傳統(tǒng)算法有更大的優(yōu)越性，不僅能夠在聚類(lèi)過(guò)程中對(duì)數(shù)據(jù)集群劃分，還可以?xún)?yōu)化各個(gè)簇類(lèi)的子空間，從而獲得更加良好的聚類(lèi)質(zhì)量.

〔1〕朱林，雷景生，畢忠勤，楊杰.一種基于數(shù)據(jù)流的軟子空間聚類(lèi)算法［J］.軟件學(xué)報(bào)，2013（11）：2611.

〔2〕莊景暉.特征加權(quán)優(yōu)化軟子空間聚類(lèi)算法［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)，2015，30（04）：415.

〔3〕邱云飛，楊倩，唐曉亮.基于粒子群優(yōu)化的軟子空間聚類(lèi)算法［J］.模式識(shí)別與人工智能，2015，28（10）:904.

〔4〕畢志升，王甲海，印鑒.基于差分演化算法的軟子空間聚類(lèi)［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（10）:2115.

〔5〕陳黎飛，郭躬德，姜青山.自適應(yīng)的軟子空間聚類(lèi)算法［J］.軟件學(xué)報(bào)，2010，21（10）:2115.

〔6〕鄧文韜.基于幾何特征加權(quán)和選擇的數(shù)據(jù)空間聚類(lèi)算法研究［J］.信息技術(shù)與信息化，2014（12）：68.

TP311

A

1673-260X（2016）07-0018-02

2016-03-08

龍巖學(xué)院青年攀登項(xiàng)目（LQ2014001）；龍巖學(xué)院校立服務(wù)海西項(xiàng)目（LQ2013009）