基于幾何特征加權(quán)和選擇的數(shù)據(jù)空間聚類算法研究

聚類分析是一種非常重要的數(shù)據(jù)處理技術(shù)和方法，在識(shí)別數(shù)據(jù)內(nèi)在結(jié)構(gòu)方面有著重要作用，通過聚類分析，人們能夠識(shí)別不同區(qū)域。密集的或稀疏的，進(jìn)而發(fā)現(xiàn)全局的分布模式和數(shù)據(jù)間的相互關(guān)系。當(dāng)前，聚類分析已成為計(jì)算機(jī)、人工智能領(lǐng)域的研究熱點(diǎn)，廣泛被應(yīng)用于數(shù)據(jù)探測、模式識(shí)別、信息檢索、文本挖掘、生物信息學(xué)、醫(yī)學(xué)診斷的研究中。然而，現(xiàn)存的數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)特征不斷增加，且數(shù)據(jù)挖掘越來越強(qiáng)調(diào)多學(xué)科的交叉，不僅需要靈活運(yùn)用統(tǒng)計(jì)學(xué)、計(jì)算機(jī)、數(shù)學(xué)等建模技術(shù)，還需要有生物學(xué)、經(jīng)濟(jì)學(xué)等學(xué)科的知識(shí)背景，為此，我們必須對(duì)現(xiàn)有聚類算法進(jìn)行深入研究，并做出合理改進(jìn)?；诖?，筆者針對(duì)數(shù)據(jù)的高維特征，提出了高維聚類方法——基于競爭合并策略的軟子空間聚類算法和基于基于空間實(shí)體約束的空間聚類算法。

一、聚類分析過程與要求

聚類在數(shù)據(jù)挖掘中是一個(gè)很重要的概念。聚類過程一般為：數(shù)據(jù)準(zhǔn)備——從原有特征中選取有效特征存入向量中——進(jìn)行特征提取——選擇并利用合適的距離函數(shù)對(duì)特征進(jìn)行聚類或分組——采取內(nèi)外部有效性評(píng)價(jià)法和相關(guān)性測試評(píng)價(jià)法對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。

聚類分析時(shí)一項(xiàng)極具挑戰(zhàn)性的工作，由于應(yīng)用領(lǐng)域不同，提出了聚類的典型要求：①聚類算法應(yīng)能高度擴(kuò)展，具有良好可伸縮性。②具備處理不同類型屬性的能力，以實(shí)現(xiàn)對(duì)多種數(shù)據(jù)類型的有效聚類。③一個(gè)簇可能是任意形狀的，要求提出能發(fā)現(xiàn)任意形狀的聚類算法對(duì)任意形狀的簇進(jìn)行有效聚類。④錄入數(shù)據(jù)時(shí)可能會(huì)存在錯(cuò)誤或異常數(shù)據(jù)，聚類算法應(yīng)能處理噪聲數(shù)據(jù)。⑤進(jìn)行聚類是需要輸入一些參數(shù)，聚類算法應(yīng)能使輸入?yún)?shù)的領(lǐng)域知識(shí)最小化。⑥許多傳統(tǒng)聚類算法無法在高維空間中聚類數(shù)據(jù)對(duì)象，要求找到具有高維性、能有效聚類高維數(shù)據(jù)的聚類算法。⑦現(xiàn)實(shí)世界的應(yīng)用可能需要在各種約束條件下進(jìn)行聚類，要求找到基于約束的聚類算法。⑧通過聚類算法獲得的聚類結(jié)果應(yīng)是可解釋的、可理解的、可用的。

二、基于競爭合并策略的軟子空間聚類算法

在過去十年中，模糊加權(quán)軟子空間聚類算法（FWSC）、熵加權(quán)軟子空間聚類算法（EWSC）、基于競爭合并策略的模糊聚類算法（FCA）、基于主動(dòng)模糊約束的聚類算法（AFCC）等被提出并被應(yīng)用于各個(gè)領(lǐng)域，但與多數(shù)傳統(tǒng)聚類算法一樣，F(xiàn)WSC和EWSC算法易陷入局部最小值情況，而不能得到恰當(dāng)?shù)木垲悇澐?，F(xiàn)CA和AFCC算法則不能發(fā)現(xiàn)各個(gè)數(shù)據(jù)簇的子空間結(jié)構(gòu)。在現(xiàn)有聚類算法基礎(chǔ)上，筆者將競爭合并策略應(yīng)用于軟子空間聚類算法研究中，提出了基于競爭合并策略的模糊加權(quán)軟子空間聚類算法（FWSCA）。

最小化FWSCA算法目標(biāo)函數(shù)公式：

   （1）

（0≤≤1，=1，0≤≤1，=1）

根據(jù)公式（1）定義目標(biāo)函數(shù)L（,,,,）：

L（,,,,）

=   （2）

其中，V=[v1,...,vc]、U=[u1,...,uc]、W=[w1,...,wc]分別表示聚類中心矩陣、模糊隸屬度矩陣和特征加權(quán)系數(shù)矩陣。

假設(shè)給定U=[u1,...,uc]和W=[w1,...,wc]，m>1，α>0，最小化目標(biāo)函數(shù)JFWSCA，當(dāng)且僅當(dāng)聚類中心vik迭代公式為（3）時(shí)，為最小化目標(biāo)函數(shù)JFWSCA的必要條件。

   （3）

假設(shè)給定U=[u1,...,uc]和V=[v1,...,vc]，m>1，α>0，最小化目標(biāo)函數(shù)JFWSCA，當(dāng)且僅當(dāng)特征加權(quán)系數(shù)wik迭代公式為（4）時(shí)，為最小化目標(biāo)函數(shù)JFWSCA的必要條件。

   （4）

給定V=[v1,...,vc]和W=[w1,...,wc]最小化公式（2），關(guān)于uij和求偏導(dǎo)，令優(yōu)化方程值為0，并假設(shè)模糊隸屬度在兩次迭代之間變化不大，本文定義第i個(gè)數(shù)據(jù)簇的勢為：

   （5）

根據(jù)公式（5），按照迭代順序進(jìn)行迭代后得到uij，重新審視可發(fā)現(xiàn)：

   （6）

其中，

   （7）

   （8）

式中，表示單個(gè)樣本xj對(duì)于所有數(shù)據(jù)簇的勢的加權(quán)平均。

公式（6）中的為傳統(tǒng)FWSC算法的隸屬度迭代公式，根據(jù)樣本，可計(jì)算聚類中心的特征加權(quán)距離；用于消減某些虛假聚類中心隸屬度大小，按照公式（5）可得到勢Ni，當(dāng)其小于某個(gè)閾值，聚類中心可被消去。根據(jù)公式（8）計(jì)算聚類中心vi的勢Ni和樣本xj對(duì)于所有數(shù)據(jù)簇加權(quán)平均勢之間的差異，若Ni小于，則為負(fù)值，uij減小。我們可以將看作是一個(gè)放大因子，使其隨樣本xj到聚類中心vi之間距離的增加而減小，進(jìn)而逐漸將虛假類聚中心的勢的大小消減。

對(duì)于參數(shù)α的選擇，應(yīng)考慮、比值情況，根據(jù)公式（1），將參數(shù)α定義為：

   （9）

式中，itr指的是FWSCA算法的迭代索引指數(shù)。采用指數(shù)因子學(xué)習(xí)法將定義為：

   （10）

式中，為學(xué)習(xí)因子初始值，、為時(shí)間常量。

上述方法對(duì)于數(shù)據(jù)簇消去的閾值比較敏感，為此在上述方法的基礎(chǔ)上，本文又提出了一種新的合并過程，即先計(jì)算第itr次迭代，得到所有數(shù)據(jù)簇勢的平均值，然后利用聚類中心之間的距離判斷整個(gè)合并過程的準(zhǔn)確性和合理性。將第itr次迭代數(shù)據(jù)簇勢的平均值和閾值分別定義為：

   （11）

   （12）

式中，n表示數(shù)據(jù)樣本個(gè)數(shù)，c（itr）第itr次迭代時(shí)數(shù)據(jù)簇個(gè)數(shù)，η為合并閾值參數(shù)。按照公式（11）、（12）計(jì)算，第itr次迭代時(shí)，若某數(shù)據(jù)簇勢小于MCT，將該數(shù)據(jù)簇消去，消去數(shù)據(jù)簇的同時(shí)對(duì)數(shù)據(jù)簇個(gè)數(shù)進(jìn)行更新。

判斷整個(gè)合并過程時(shí)，將聚類中心之間的距離定義為d（r），當(dāng)其最小值滿足公式（13）時(shí)，合并數(shù)據(jù)簇，進(jìn)行數(shù)據(jù)簇個(gè)數(shù)的更新。

   （13）

總結(jié)起來，F(xiàn)WSCA算法流程為：設(shè)置最大數(shù)據(jù)簇聚類數(shù)目c=cmax（2≤cmax≤n），模糊加權(quán)指數(shù)m以及競爭合并參數(shù)n，初始化模糊隸屬度，設(shè)置迭代指數(shù)itr=1。根據(jù)公式（3）計(jì)算聚類中心矩陣V（itr+1）。根據(jù)公式（4）計(jì)算加權(quán)系數(shù)矩陣W（itr+1）。根據(jù)公式（5）計(jì)算第i個(gè)數(shù)據(jù)簇的勢Ni（1≤i≤c）。根據(jù)公式（9）和（10）更新參數(shù)α（itr）。根據(jù)公式（6）計(jì)算模糊劃分矩陣U（itr+1）。判斷Ni是否小于數(shù)據(jù)簇勢的閾值或者各個(gè)聚類中心之間最小距離是否滿足公式（13），若滿足，則刪除該數(shù)據(jù)簇。更新數(shù)據(jù)簇聚類數(shù)目c（itr+1）。若滿足迭代停止條件或數(shù)據(jù)簇聚類數(shù)目保持穩(wěn)定，則迭代停止并輸出最終聚類結(jié)果，否則itr=itr+1，并跳轉(zhuǎn)到第二步。

三、基于空間實(shí)體約束的空間聚類算法

空間實(shí)體的存在會(huì)對(duì)空間聚類分析產(chǎn)生影響。傳統(tǒng)聚類算法中一般是采用樣本間的直線距離來衡量樣本間、數(shù)據(jù)簇間的相似性，忽略了空間實(shí)體的約束作用，從而影響了聚類結(jié)果。比如要在一個(gè)城市內(nèi)設(shè)置ATM，對(duì)給定的ATM進(jìn)行選址的時(shí)候，為了保證服務(wù)網(wǎng)絡(luò)最優(yōu)化，不僅要按照空間位置特征對(duì)城市所有的居民點(diǎn)進(jìn)行聚類，還需要考慮道路、橋梁、河流、山脈等可跨越障礙物的便利體的連通作用。

基于約束Delaunay三角網(wǎng)特性提出一種基于Delaunay三角剖分的用于空間約束數(shù)據(jù)聚類的算法——基于空間實(shí)體約束的空間聚類算法（CDC）。CDC算法首先要?jiǎng)澐謹(jǐn)?shù)據(jù)集，提取空間位置屬性，同時(shí)考慮空間障礙和空間便利，利用非空間屬性調(diào)整初始劃分，最后對(duì)劃分結(jié)果進(jìn)行合并。得到的包含約束點(diǎn)的三角網(wǎng)需首先刪除約束點(diǎn)以及與之相連的邊，記錄與便利點(diǎn)相連的點(diǎn)集和點(diǎn)集間相連的邊，對(duì)所得邊進(jìn)行統(tǒng)計(jì)，若已有邊的權(quán)值大于通過便利點(diǎn)連接后的權(quán)值，則刪除已有邊，將通過便利點(diǎn)連接的邊納入邊集合，若已有邊權(quán)值小于通過便利點(diǎn)連接的邊，則保留原有邊。為實(shí)現(xiàn)三角網(wǎng)的自動(dòng)劃分，要在三角網(wǎng)中刪除便利點(diǎn)和與點(diǎn)相連的邊，本文給出三角形Ti的平均值和三條邊的方差：

   （14）

   （15）

三角形從長到短的邊分別定義為：Timax、Timid、Timin，當(dāng)Timax-Timin>2Sub（Ti），保留最短邊，刪除最長邊；若Timid-Timin>2Sub（Ti），保留最短邊，刪除中間長度的邊。反之則保留最長邊或中間長度的邊。重復(fù)上述過程直到每個(gè)三角形判斷完成，停止三角網(wǎng)劃分。

四、結(jié)語

空間數(shù)據(jù)挖掘是一個(gè)從空間數(shù)據(jù)中提取或識(shí)別有效、有利用價(jià)值、可理解的數(shù)據(jù)的非平凡過程，在這個(gè)過程中，需要以空間聚類算法為支撐。本文在現(xiàn)有聚類算法的基礎(chǔ)上，提出了FWSCA算法和CDC算法，這兩種算法都是對(duì)原有聚類算法的改進(jìn)，具有良好適用性和有效性。但本研究對(duì)于聚類分析這一應(yīng)用廣闊的領(lǐng)域來說只是初步的，聚類分析相關(guān)理論仍需進(jìn)一步完善，聚類結(jié)果的質(zhì)量、聚類受初始值影響程度、能否發(fā)現(xiàn)任意形聚類及聚類的執(zhí)行效率也有待提高，只有將理論研究成果實(shí)用化，才能使之真正應(yīng)用于實(shí)際問題的解決中。

參考文獻(xiàn)：

[1]周濤,陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2012,12:100-111.

[2]朱林,雷景生,畢忠勤,楊杰.一種基于數(shù)據(jù)流的軟子空間聚類算法[J].軟件學(xué)報(bào),2013,11:2610-2627.

[3]于翔,印桂生,許憲東,王建偉.一種基于區(qū)域劃分的數(shù)據(jù)流子空間聚類方法[J].計(jì)算機(jī)研究與發(fā)展,2014,01:88-95.

[4]李婧.基于數(shù)據(jù)幾何特征的空間聚類算法[D].重慶師范大學(xué),2014.

[5]曹世媛.基于密度的數(shù)據(jù)流子空間聚類算法研究[D].燕山大學(xué),2010.

 本文來源：http://m.xwlcp.cn/w/kj/11621.html  《信息技術(shù)信息化》