陳曉潔，王雯娟

（龍巖學院　信息工程學院，福建　龍巖　364012）

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

陳曉潔，王雯娟

（龍巖學院信息工程學院，福建龍巖364012）

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

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

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

1　聚類分析過程及要求

聚類分析的過程為：做好分析數(shù)據(jù)的準備工作——篩選出有效特征，并將此特征存在矢量中——將數(shù)據(jù)的特征提取出來——選擇合理的距離函數(shù)，并利用此函數(shù)對特征進行聚類——對聚類結果進行評價、測試.

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

2　軟子空間與硬子空間聚類算法的對比

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

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

3.1FSC算法

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

首先對全文使用符號含義進行說明：

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

V=｛xkj｝C×D表示簇類中心矩陣；

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

W=｛wkj｝C×D表示權值矩陣；

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

有研究學者提出了一種新的聚類算法FSC，這種算法多應用在高維度的數(shù)據(jù)聚類處理中.FSC給模糊權值進行定義，并將模糊權值帶入到函數(shù)中去，得到以下目標函數(shù)：

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

3.2特征加權優(yōu)化軟子空間聚類算法

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

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

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

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

3.2.2特征加權優(yōu)化軟子空間聚類算法算法過程及分析

具體算法描述如下：

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

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

算法結束：直到目標函數(shù)值達到最下值或者V和W這兩個參數(shù)在計算過程中相鄰兩次的變化比給定的闕值小.輸出：將聚類中心矩陣V以及隸屬度矩陣U輸出.

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

4　結論

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

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

〔2〕莊景暉.特征加權優(yōu)化軟子空間聚類算法［J］.長春工業(yè)大學學報，2015，30（04）：415.

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

〔4〕畢志升，王甲海，印鑒.基于差分演化算法的軟子空間聚類［J］.計算機學報，2012，35（10）:2115.

〔5〕陳黎飛，郭躬德，姜青山.自適應的軟子空間聚類算法［J］.軟件學報，2010，21（10）:2115.

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

TP311

A

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

2016-03-08

龍巖學院青年攀登項目（LQ2014001）；龍巖學院校立服務海西項目（LQ2013009）