肖宇鵬，何云斌，萬(wàn) 靜，李 松

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080）

基于模糊C-均值的空間不確定數(shù)據(jù)聚類(lèi)

肖宇鵬，何云斌，萬(wàn) 靜，李 松

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080）

針對(duì)現(xiàn)實(shí)世界中樣本對(duì)象的不確定性及樣本對(duì)象間界限劃分的模糊性，提出基于模糊C-均值的空間不確定數(shù)據(jù)聚類(lèi)算法UFCM。但由于UFCM算法在聚類(lèi)過(guò)程中涉及大量期望距離的復(fù)雜積分計(jì)算，導(dǎo)致UFCM算法性能不理想，進(jìn)而給出改進(jìn)算法I-UFCM，將空間不確定對(duì)象聚類(lèi)問(wèn)題轉(zhuǎn)化為傳統(tǒng)的確定對(duì)象聚類(lèi)問(wèn)題，采用相似度計(jì)算公式減少期望距離的計(jì)算量，提高聚類(lèi)結(jié)果的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，與UFCM和UK-Means算法相比，I-UFCM算法在空間不確定數(shù)據(jù)集上具有更好的聚類(lèi)性能，CUP耗時(shí)降低了90%以上。

模糊C-均值；不確定數(shù)據(jù)；概率密度函數(shù)；期望距離；質(zhì)心

DO I：10.3969/j.issn.1000-3428.2015.10.010

1 概述

近年來(lái)，隨著聚類(lèi)分析研究的不斷深入，以及數(shù)據(jù)不確定性在實(shí)際應(yīng)用中普遍存在，不確定數(shù)據(jù)受到越來(lái)越多的關(guān)注，因此分析和挖掘不確定數(shù)據(jù)成為當(dāng)前研究的熱點(diǎn)［1-3］。目前，國(guó)內(nèi)外學(xué)者多采用概率密度函數(shù)對(duì)不確定數(shù)據(jù)進(jìn)行建模，并在此基礎(chǔ)上擴(kuò)展現(xiàn)有聚類(lèi)算法實(shí)現(xiàn)對(duì)不確定數(shù)據(jù)的聚類(lèi)分析，例如基于K-M eans算法的UK-Means算法［4］、基于DBSCAN算法的FDBSCAN算法［5］等。但上述算法在衡量樣本間相似度時(shí)計(jì)算量大。針對(duì)該問(wèn)題，文獻(xiàn)［6］提出一種基于Voronoi圖和R-tree的剪枝策略，但該策略在構(gòu)造Voronoi圖和R-tree時(shí)會(huì)產(chǎn)生較大的時(shí)間開(kāi)銷(xiāo)。文獻(xiàn)［7］依據(jù)物理學(xué)中剛體運(yùn)動(dòng)的轉(zhuǎn)動(dòng)慣量思想，推導(dǎo)出一個(gè)相似度計(jì)算公式，其效率比傳統(tǒng)不確定聚類(lèi)算法的效率有了較大提高。文獻(xiàn)［8］通過(guò)子空間劃分的方法進(jìn)行聚類(lèi)。文獻(xiàn)［9］在度量的基礎(chǔ)上，結(jié)合三角修剪法完成二維空間下不確定數(shù)據(jù)的聚類(lèi)。文獻(xiàn)［10］通過(guò)不確定中心點(diǎn)的計(jì)算實(shí)現(xiàn)不確定數(shù)據(jù)的劃分。但是上述算法均未考

慮樣本間界限劃分模糊的問(wèn)題。

考慮到現(xiàn)實(shí)世界中樣本對(duì)象的不確定性和樣本間界限劃分的模糊性，使得樣本對(duì)象更適合軟劃分。因此，使用模糊聚類(lèi)來(lái)分析數(shù)據(jù)的不確定性更符合實(shí)際情況。其中，模糊C-均值算法是應(yīng)用最廣泛的一種聚類(lèi)分析方法。該方法依據(jù)某個(gè)隸屬度來(lái)劃分樣本對(duì)象，從而使得類(lèi)內(nèi)誤差平方和目標(biāo)函數(shù)最小。然而，文獻(xiàn)［11-12］研究表明：算法易受到初始點(diǎn)和噪聲數(shù)據(jù)的影響，并且在處理不同密度樣本數(shù)據(jù)時(shí)存在較大誤差。對(duì)此國(guó)內(nèi)外研究者基于不同理論提出一系列方法對(duì)算法進(jìn)行改進(jìn)，例如：文獻(xiàn)［12-13］提出基于核聚類(lèi)和擴(kuò)展高斯核聚類(lèi)的算法；文獻(xiàn)［14］在模糊 C-均值算法中引入屬性權(quán)重的概念進(jìn)行聚類(lèi)分析；此外，還提出結(jié)合人工智能算法［15］和數(shù)理統(tǒng)計(jì)方法［16］優(yōu)化模糊聚類(lèi)算法。以上均是針對(duì)確定樣本空間數(shù)據(jù)處理，未考慮空間樣本的不確定性。

本文在綜合分析不確定數(shù)據(jù)聚類(lèi)現(xiàn)狀和模糊C-均值算法的基礎(chǔ)上，給出基于模糊C-均值算法的空間不確定數(shù)據(jù)聚類(lèi)算法（UFCM）。針對(duì)空間不確定數(shù)據(jù)模型在聚類(lèi)時(shí)需要大量積分計(jì)算導(dǎo)致算法性能較差的問(wèn)題，以及傳統(tǒng)歐氏距離在衡量樣本間相似度時(shí)存在的不足，在UFCM算法的基礎(chǔ)上提出改進(jìn)的UFCM算法（I-UFCM）。

2 基于模糊C-均值的不確定數(shù)據(jù)聚類(lèi)

2.1 模糊C-均值聚類(lèi)算法

設(shè)數(shù)據(jù)集X=｛χ1，χ2，…，χn｝為m維空間的一組待聚類(lèi)樣本向量，聚類(lèi)樣本的c個(gè)類(lèi)別為V=｛V1，V2，…，Vc｝，c個(gè)聚類(lèi)簇的中心表示為ν=｛ν1，ν2，…，νc｝。用隸屬度矩陣 Uc×n=（uij），uij∈［0，1］表示每個(gè)樣本對(duì)各聚類(lèi)簇的隸屬度，其中，i=1，2，…，c；j= 1，2，…，n。2個(gè)樣本對(duì)象 χi，χP之間的歐氏距離定義為：

模糊C-均值算法的目標(biāo)函數(shù)為：

其中，m∈［1，∞）是一個(gè)加權(quán)指數(shù)，隨著 m的增大，聚類(lèi)的模糊性增大。根據(jù)拉格朗日數(shù)乘法，求得使目標(biāo)函數(shù)在滿(mǎn)足約束條件的前提下取得極小值的必要條件：

模糊C-均值聚類(lèi)算法在聚類(lèi)過(guò)程中通過(guò)反復(fù)迭代式（4）和式（5），使得目標(biāo)函數(shù)式（2）不斷減少直至最小。

2.2 空間不確定數(shù)據(jù)聚類(lèi)模型

數(shù)據(jù)的不確定性主要表現(xiàn)在數(shù)據(jù)是否存在不確定性和數(shù)據(jù)屬性級(jí)別的不確定性?xún)煞矫妫?0］。在空間不確定數(shù)據(jù)聚類(lèi)中，通常使用屬性級(jí)別的不確定模型，即數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的屬性不再是確定的數(shù)據(jù)值，每個(gè)數(shù)據(jù)對(duì)象也不再是一個(gè)單獨(dú)的樣本點(diǎn)，而是通過(guò)一個(gè)概率密度函數(shù)（Probability Density Function，PDF）來(lái)定義不確定區(qū)域。概率密度函數(shù)詳細(xì)給出了空間中每個(gè)不確定對(duì)象可能的位置。

定義1（空間不確定數(shù)據(jù)） 在m維空間Rm中，給定一組不確定空間數(shù)據(jù)對(duì)象 O=｛o1，o2，…，on｝，距離函數(shù)d：Rm×Rm→R，對(duì)于每個(gè)不確定空間數(shù)據(jù)對(duì)象oi，都有一個(gè)概率密度函數(shù)fi：Rm→R定義不確定對(duì)象的分布。根據(jù)概率密度函數(shù)得到：

通過(guò)期望距離衡量不確定對(duì)象的相似度。

定義2（期望距離） 不確定空間對(duì)象oi和任意點(diǎn) p的期望距離定義［7］：

由式（7）可得2個(gè)不確定空間樣本對(duì)象間的期望距離。

定義3（不確定對(duì)象間的期望距離） 不確定空間對(duì)象oi和oj間的期望距離為：

不確定空間數(shù)據(jù)的聚類(lèi)分析是對(duì)給定的一組不確定對(duì)象O及有效聚類(lèi)數(shù)目k，通過(guò)映射函數(shù)h：｛1，2，…，n｝→｛1，2，…，k｝將不確定對(duì)象劃分到k個(gè)聚類(lèi)簇C=｛c1，c2，…，ck｝中。聚類(lèi)簇 C中的每個(gè)ci為所屬簇的代表點(diǎn)。聚類(lèi)最終使得簇內(nèi)期望距離和達(dá)到最小。

2.3 空間不確定數(shù)據(jù)聚類(lèi)算法

對(duì)于不確定空間數(shù)據(jù)對(duì)象集合O，聚類(lèi)的c個(gè)類(lèi)別為OV=｛OV1，OV2，…，OVc｝，c個(gè)不確定聚類(lèi)簇中心對(duì)象為 oν=｛oν1，oν2，…，oνc｝。不確定空間數(shù)據(jù)模糊聚類(lèi)的目標(biāo)函數(shù)為：

其中，ED（oj，oνi）為2個(gè)不確定空間數(shù)據(jù)對(duì)象間的期望距離。根據(jù)拉格朗日數(shù)乘法，求得使目標(biāo)函數(shù)在約束條件式（3）下取得極小值的必要條件為：

基于以上分析提出算法1，即基于模糊C-均值的不確定樣本空間數(shù)據(jù)聚類(lèi)算法UFCM，具體描述如下：

算法1UFCM算法

輸入 n個(gè)待聚類(lèi)的不確定空間樣本對(duì)象，有效劃分?jǐn)?shù)目c，迭代次數(shù)t，最大迭代次數(shù)T，閾值θ

輸出 c個(gè)使誤差平方和準(zhǔn)則最小的聚類(lèi)簇

Step1 隨機(jī)選取c個(gè)不確定初始聚類(lèi)中心；

Step2 循環(huán)；

Step2.1 根據(jù)式（10）計(jì)算不確定空間樣本的隸屬度矩陣U；

Step2.2 由式（11）和矩陣U計(jì)算新的不確定對(duì)象中心集合oν；

Step2.3 根據(jù)式（9）計(jì)算目標(biāo)函數(shù)JUFCM，并且t=t+1；

Step4 由最終的隸屬度矩陣U劃分樣本。

UFCM算法在計(jì)算樣本隸屬度矩陣時(shí)需要計(jì)算不確定空間對(duì)象之間的期望距離ED。當(dāng)不確定空間對(duì)象的數(shù)量較多或者概率分布函數(shù)較為復(fù)雜時(shí)，式（8）計(jì)算復(fù)雜、耗時(shí)長(zhǎng)。此外，UFCM算法基于FCM算法發(fā)展而來(lái)，傳統(tǒng)的模糊C-均值算法在計(jì)算樣本點(diǎn)間相似度時(shí)采用歐氏距離作為衡量標(biāo)準(zhǔn)。這種標(biāo)準(zhǔn)計(jì)算方法具有一定局限性，易受到噪聲點(diǎn)的影響，并且在處理不同大小和密度樣本數(shù)據(jù)時(shí)存在較大的誤差。

3 改進(jìn)的UFCM聚類(lèi)算法

針對(duì)UFCM算法的不足，提出改進(jìn)的基于模糊C-均值的聚類(lèi)算法（I-UFCM）。改進(jìn)算法通過(guò)特定轉(zhuǎn)換機(jī)制，將不確定空間對(duì)象用一個(gè)確定的空間樣本點(diǎn)表示，將不確定對(duì)象的聚類(lèi)問(wèn)題轉(zhuǎn)化為經(jīng)典的確定數(shù)據(jù)對(duì)象的聚類(lèi)問(wèn)題。算法采用新的相似度計(jì)算公式衡量樣本間距，再加上有效的策略，改善傳統(tǒng)歐氏距離測(cè)定方法的不足，從而提高聚類(lèi)結(jié)果的質(zhì)量。

3.1 空間不確定數(shù)據(jù)聚類(lèi)的確定化

將不確定空間數(shù)據(jù)確定化，即通過(guò)一個(gè)樣本點(diǎn)ki表示由一組樣本點(diǎn)所代表的不確定空間對(duì)象 oi，從而將n個(gè)不確定空間數(shù)據(jù)對(duì)象聚類(lèi)問(wèn)題轉(zhuǎn)化成n個(gè)確定空間數(shù)據(jù)對(duì)象的聚類(lèi)問(wèn)題。因此，為每個(gè)不確定空間對(duì)象定義其質(zhì)心，也稱(chēng)為期望中心。

定義4（不確定對(duì)象質(zhì)心） 對(duì)于每個(gè)不確定空間對(duì)象 oi，oi的分布區(qū)域?yàn)?Rm，其質(zhì)心 ki定義如下［8］：

依據(jù)物理學(xué)中剛體轉(zhuǎn)動(dòng)慣量思想及依此推導(dǎo)出的平行軸定理，對(duì)于空間任意不確定對(duì)象 oi及不確定空間中任意點(diǎn) χP，根據(jù)質(zhì)心式（12）和期望距離式（7）定義新的期望距離計(jì)算公式為：

ED（oi，χP）=ED（oi，ki）+D ist（χP，ki） （13）

可見(jiàn)，新的期望距離計(jì)算公式只需計(jì)算出ED（oi，ki）及Dist（χP，ki），即可快速便捷地計(jì)算出ED（oi，χP），從而省去多次計(jì)算概率密度函數(shù)。

因此，對(duì)于不確定空間數(shù)據(jù)模糊聚類(lèi)，可以用c個(gè)聚類(lèi)簇中心點(diǎn)ν=｛ν1，ν2，…，νc｝代替原有的c個(gè)不確定聚類(lèi)簇中心對(duì)象。此時(shí)，不確定空間數(shù)據(jù)模糊聚類(lèi)目標(biāo)函數(shù)JUFCM為：

其中，νh（i）表示映射函數(shù)h下的聚類(lèi)簇中心點(diǎn)。對(duì)于每一個(gè)空間不確定對(duì)象oi及其密度函數(shù)fi都是定量。因此無(wú)需反復(fù)計(jì)算對(duì)象的期望中心距離 ED（oj，kj），并且ED（oj，kj）可事先計(jì)算得出且保持不變。因此，ED（oj，kj）可用 M表示，此時(shí)目標(biāo)函數(shù)為：

可見(jiàn)，只需給出每個(gè)空間不確定對(duì)象的質(zhì)心 kj，而無(wú)需考慮每個(gè)不確定空間對(duì)象的 ED（oj，kj），即可求出目標(biāo)函數(shù)在式（3）約束條件下的極小值。

3.2 相似度計(jì)算公式

在處理不同大小和密度樣本或有噪聲存在的數(shù)據(jù)時(shí)，傳統(tǒng)歐式距離存在較大誤差［15］。特別是在每次計(jì)算聚類(lèi)簇中心點(diǎn)時(shí)，簇中心極易受到簇中樣本數(shù)據(jù)分布密度的影響。由于不確定空間數(shù)據(jù)整體分布的不確定性，傳統(tǒng)的歐氏距離計(jì)算方法不適宜應(yīng)用于不確定數(shù)據(jù)聚類(lèi)問(wèn)題。

本文采用新的樣本間相似度衡量標(biāo)準(zhǔn)，即對(duì)一組空間樣本數(shù)據(jù)集 X=｛χ1，χ2，…，χn｝有［16］：

其中，β基于統(tǒng)計(jì)學(xué)知識(shí)且由樣本數(shù)據(jù)集計(jì)算得出，其定義式為：

采用新的相似度計(jì)算公式，將I-UFCM算法的模糊聚類(lèi)目標(biāo)準(zhǔn)則函數(shù)改寫(xiě)為：

同樣，式（15）以式（3）為約束條件構(gòu)造拉格朗日函數(shù)，并求其取得極小值的必要條件為：

3.3 I-UFCM聚類(lèi)算法

I-UFCM算法計(jì)算每個(gè)不確定空間對(duì)象的質(zhì)心，并將其質(zhì)心存入 K中，此外，改進(jìn)算法選用新的相似度度量標(biāo)準(zhǔn)衡量樣本間相似度。I-UFCM算法的具體描述如下：

算法2 I-UFCM算法

輸入 n個(gè)待聚類(lèi)的不確定空間樣本對(duì)象，有效劃分?jǐn)?shù)目c，迭代次數(shù)t，最大迭代次數(shù)T，閾值θ

輸出 c個(gè)使聚類(lèi)目標(biāo)函數(shù)最小的聚類(lèi)簇

Step1 根據(jù)式（12）計(jì)算每個(gè)不確定空間對(duì)象的質(zhì)心，K=ki∪K；

Step2 令t=0，并初始化初始聚類(lèi)中心點(diǎn)集合，即構(gòu)造集合 ν=｛ν1，ν2，…，νc｝；

Step3 循環(huán)；

Step3.1 根據(jù)式（19）計(jì)算空間樣本ki的隸屬度矩陣U；

Step3.2 根據(jù)式（20）和隸屬度矩陣U計(jì)算新的樣本中心集合ν；

Step3.3 根據(jù)式（18）計(jì)算每次劃分的目標(biāo)函數(shù)JI-UFCM，并且t=t+1；

Step5 由最終的隸屬度矩陣U劃分樣本。

對(duì)于n個(gè)空間不確定對(duì)象，I-UFCM算法首先通過(guò)計(jì)算式（12），花費(fèi)O（n）的時(shí)間復(fù)雜度即可得到n個(gè)不確定樣本對(duì)象的質(zhì)心。此后，在聚類(lèi)過(guò)程中，I-UFCM算法采用新的相似度衡量準(zhǔn)則，其時(shí)間復(fù)雜度為O（nct），其中，n為不確定空間樣本對(duì)象的質(zhì)心；c為聚類(lèi)劃分?jǐn)?shù)；t為算法有效迭代次數(shù)。

4 實(shí)驗(yàn)結(jié)果與分析

本文分別采用UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集對(duì)UFCM算法和I-UFCM算法進(jìn)行實(shí)驗(yàn)，并與傳統(tǒng)的UK-Means不確定聚類(lèi)算法進(jìn)行對(duì)比。實(shí)驗(yàn)采用F-measure（F）作為聚類(lèi)外部評(píng)測(cè)標(biāo)準(zhǔn)，同時(shí)從類(lèi)間距和類(lèi)內(nèi)距出發(fā)，采用內(nèi)部評(píng)測(cè)標(biāo)準(zhǔn)評(píng)測(cè)聚類(lèi)效果。

4.1 不確定數(shù)據(jù)集的構(gòu)造

實(shí)驗(yàn)中所采用的UCI數(shù)據(jù)集的特征參數(shù)如表1所示。

表1 UCI實(shí)驗(yàn)數(shù)據(jù)集的特征參數(shù)

為在UCI基礎(chǔ)數(shù)據(jù)集的基礎(chǔ)上構(gòu)造不確定數(shù)據(jù)集，需要添加一個(gè)不確定數(shù)據(jù)生成策略。為每個(gè)數(shù)據(jù)源中的樣本數(shù)據(jù)定義一個(gè)概率密度函數(shù)fi，使每一個(gè)樣本對(duì)象由一組樣本點(diǎn)來(lái)表示，而每個(gè)樣本點(diǎn)都對(duì)應(yīng)一個(gè)概率值，即每一個(gè)樣本對(duì)象oi，有：

其中，ωim為不確定對(duì)象oi的一個(gè)樣本點(diǎn)；fi（ωim）是與每個(gè)樣本相對(duì)應(yīng)的概率

此外，為對(duì)比算法性能，需構(gòu)造一組人工模擬數(shù)據(jù)集。人工模擬數(shù)據(jù)是在二維空間［0，l］×［0，l］中生成n個(gè)空間不確定對(duì)象的數(shù)據(jù)集。對(duì)于每一個(gè)不確定對(duì)象 oi，在邊長(zhǎng) d的正方形包圍框中，隨機(jī)生成m個(gè)樣本點(diǎn)，并且為每個(gè)樣本點(diǎn)賦一個(gè)介于0和1之間的均勻分布概率值。將 m個(gè)樣本點(diǎn)的概率值標(biāo)準(zhǔn)化，使其總和為1。從而構(gòu)造一組在［0，l］×［0，l］中的 n個(gè)二維空間不確定對(duì)象的數(shù)據(jù)集。

4.2 結(jié)果分析

實(shí)驗(yàn)對(duì)傳統(tǒng)UK-Means算法及本文提出的UFCM算法、I-UFCM算法分別進(jìn)行50次獨(dú)立聚類(lèi)實(shí)驗(yàn)，記錄每次實(shí)驗(yàn)結(jié)果，求其平均值并對(duì)比3個(gè)算法的實(shí)驗(yàn)結(jié)果，如表2所示。在表2中，F(xiàn)-AVG（C，C～）為聚類(lèi)外部評(píng)測(cè)標(biāo)準(zhǔn)F-measure（F）指標(biāo)，其值越高則說(shuō)明算法聚類(lèi)的效果越好；Q-AVG（C）為類(lèi)內(nèi)距和類(lèi)

間距的指標(biāo)合并，即Q（C）=intra（C）-inter（C）。由于將類(lèi)內(nèi)距intra（C）和類(lèi)間距inter（C）標(biāo)準(zhǔn)化后其范圍均在［0，1］內(nèi)，因此 Q（C）取值范圍在［-1，1］之間。

表2 聚類(lèi)算法有效性對(duì)比

結(jié)果顯示，對(duì)Iris，Wine和Glass 3組數(shù)據(jù)集的空間不確定對(duì)象的聚類(lèi)劃分中，UFCM算法和I-UFCM算法的F平均指標(biāo)及Q平均指標(biāo)均高于傳統(tǒng)UK-Means算法。對(duì)于Balance數(shù)據(jù)集，UFCM算法的聚類(lèi) F平均指標(biāo)及 Q平均指標(biāo)略低于UK-Means算法。而改進(jìn)后的I-UFCM算法在對(duì)Balance數(shù)據(jù)集的實(shí)驗(yàn)中，表現(xiàn)出更優(yōu)越的聚類(lèi)能力，其F平均指標(biāo)和Q平均指標(biāo)都高于UK-Means算法和UFCM算法。

此外，構(gòu)造多個(gè)人工模擬2D空間不確定數(shù)據(jù)集測(cè)試算法的性能。對(duì)于有效聚類(lèi)數(shù)k值及不確定樣本對(duì)象具有相同的 m個(gè)樣本點(diǎn)時(shí)，為公平地評(píng)價(jià)算法性能，假設(shè)3個(gè)算法在聚類(lèi)初始時(shí)均選取一致的初始聚類(lèi)中心點(diǎn)。圖1反映了在有效聚類(lèi)數(shù)k值確定的情況下，3個(gè)算法在不同規(guī)模的樣本數(shù)下的CPU耗時(shí)情況。

圖1 有效聚類(lèi)數(shù)相同情況下的CPU耗時(shí)

圖1顯示本文提出的UFCM算法與UK-Means算法的耗時(shí)大體一致。而改進(jìn)后的I-UFCM算法由于簡(jiǎn)化了期望距離ED的計(jì)算復(fù)雜度，其CPU耗時(shí)相比傳統(tǒng)UK-Means算法和UFCM算法降低了90%以上。此外，IUFCM算法的耗時(shí)基本花費(fèi)在計(jì)算不確定樣本對(duì)象的質(zhì)心上，然而不確定空間對(duì)象質(zhì)心的計(jì)算只需一次。一旦不確定樣本數(shù)據(jù)的質(zhì)心計(jì)算完成，算法只需花費(fèi)很少的時(shí)間完成空間聚類(lèi)。

在空間不確定對(duì)象數(shù)量n和有效聚類(lèi)數(shù)k值確定的情況下，圖2給出每個(gè)不確定樣本對(duì)象 oi在不同樣本數(shù)m下，3個(gè)算法的CPU耗時(shí)情況。同樣，在初始聚類(lèi)時(shí) 3種算法均選取一致初始聚類(lèi)中心點(diǎn)。

圖2 空間不確定對(duì)象數(shù)相同情況下的CPU耗時(shí)

由圖2可知，當(dāng)每個(gè)空間不確定對(duì)象 oi的樣本數(shù)m增大時(shí)，3個(gè)算法的CPU耗時(shí)也隨之增加。在計(jì)算每個(gè)不確定空間對(duì)象oi時(shí)，改進(jìn)后的I-UFCM算法的計(jì)算量和質(zhì)心計(jì)算隨著樣本點(diǎn)數(shù)m的增加而增大。當(dāng)質(zhì)心一旦確定，空間不確定對(duì)象聚類(lèi)問(wèn)題就可簡(jiǎn)化成精確點(diǎn)的聚類(lèi)問(wèn)題，因此，I-UFCM算法的CPU耗時(shí)仍小于傳統(tǒng)UK-Means算法和UFCM算法。

5 結(jié)束語(yǔ)

本文在模糊C-均值聚類(lèi)的基礎(chǔ)上，提出面向空間不確定數(shù)據(jù)的聚類(lèi)算法UFCM。然而由于空間不確定對(duì)象模型的復(fù)雜度高，UFCM算法在聚類(lèi)過(guò)程中涉及大量期望距離的復(fù)雜積分計(jì)算，導(dǎo)致UFCM算法性能不理想，進(jìn)一步給出改進(jìn)的I-UFCM算法。I-UFCM算法將不確定空間聚類(lèi)問(wèn)題確定化，使用新的相似度衡量方式彌補(bǔ)傳統(tǒng)歐氏距離的不足，并通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證了I-UFCM的正確性，并表明其對(duì)空間不確定數(shù)據(jù)聚類(lèi)的研究具有借鑒作用。下一步將對(duì)基于連續(xù)性概率密度函數(shù)的不確定數(shù)據(jù)聚類(lèi)分析進(jìn)行相關(guān)研究。

［1］ 張志兵.空間數(shù)據(jù)挖掘及其相關(guān)問(wèn)題研究［M］.武漢：華中科技大學(xué)出版社，2011.

［2］ Aggarwal C C，Yu P S.A Survey of Uncertain Data Algorithm s and Applications［J］.IEEE Transactions on Know ledge and Data Engineering，2009，21（5）：609-623.

［3］ Jiang Bin，Pei Jian，Tao Yufei，et al.Clustering Uncertain Data Based on Probability Distribution Similarity［J］. IEEE Transactions on Know ledge and Data Engineering，2013，25（4）：751-763.

［4］ Chau M，Cheng R，Kao B，et al.Uncertain Data Mining：An Example in Clustering Location Data［C］// Proceedings of PAKDD’06.Berlin，Germ any：Springer，2006：199-204.

［5］ Kriegel H P，Pfeifle M.Density-based Clustering of Uncertain Data［C］//Proceedings of the 11th ACM SIGKDD International Conference on Know ledge Discovery in Data Mining.New York，USA：ACM Press，2005：672-677.

［6］ Kao B，Lee S D.Clustering Uncertain Data Using Voronoi Diagrams and r-tree Index［J］.IEEE Transactions on Know ledge and Data Engineering，2010，22（9）：1219-1233.

［7］ Lee S D，Kao B，Cheng R.Reducing UK-means to K-means［C］//Proceedings of the 7th IEEE International Conference on Data Mining Workshops.Washington D.C.，USA：IEEE Press，2007：483-488.

［8］ Günnemann S，Kremer H，Seidl T.Subspace Clustering for Uncertain Data［C］//Proceedings of 2010 SIAM International Conference on Data Mining.［S.l.］：Society for Industrial and Applied Mathematics，2010：385-396.

［9］ Ngai W K，Kao B，Cheng R，et al.Metric and Trigonometric Pruning for Clustering of Uncertain Data in 2D Geometric Space［J］.Information Systems，2011，36（2）：476-497.

［10］ Gullo F，Tagarelli A.Uncertain Centroid Based Partitional Clustering of Uncertain Data［J］.Proceedings of the VLDB Endowment，2012，5（7）：610-621.

［11］ Nazari M，Shanbehzadeh J，Sarrafzadeh A.Fuzzy C-means Based on Automated Variable Feature Weighting［C］//Proceedings of International Multi Conference of Engineers and Computer Scientists.Calgary，Canada：International Association of Engineers，2013：13-15.

［12］ Ramathilagam S，Huang Yueh-Min.Extended Gaussian Kernel Version of Fuzzy C-means in the Problem of Data Analyzing［J］.Expert System s with Applications，2011，38（4）：3793-3805.

［13］ 王 亮，王士同.基于成對(duì)約束的動(dòng)態(tài)加權(quán)率監(jiān)督模糊核聚類(lèi)［J］.計(jì)算機(jī)工程，2012，38（1）：148-150.

［14］ 王麗娟，關(guān)守義，王曉龍，等.基于屬性權(quán)重的Fuzzy CMean算法［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（10）：1797-1802.

［15］ Qu Jianhua，Shao Zengzhen，Liu Xiyu.Mixed PSO Clustering Algorithm Using Point Symmetry Distance［J］.Journal of Computational Information Systems，2010，6（6）：2027-2035.

［16］ Wu Kuo-Lung，Yang Miin-Shen.Alternative C-means Clustering Algorithms［J］.Pattern Recognition，2002，35（10）：2267-2278.

編輯陸燕菲

Clustering of Space Uncertain Data Based on Fuzzy C-means

XIAO Yupeng，HE Yunbin，WAN Jing，LI Song
（School of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China）

Aiming at the uncertainty of sample object in real world and the fuzzy boundary between sample objects，this paper proposes a Uncertain Fuzzy C-Means（UFCM）algorithm.Because of a lot of complex integral calculation in expected distance computation，UFCM algorithm is inefficiency.Further，an improved algorithm called I-UFCM is proposed.In this algorithm，the spatial uncertain objects are transformed into the traditional certain objects for clustering. Besides，a new formula for calculation similarity is introduced instead of traditional Euclidean norm to evaluate the distance between objects.The quality of clustering results is improved by reducing the computational amount of excepted distance.Experimental results demonstrate the clustering performance of I-UFCM algorithm is more effective than UFCM and UK-Means algorithm，and its CPU time is reduced by 90%.

fuzzy C-means；uncertain data；probability density function；excepted distance；centroid

肖宇鵬，何云斌，萬(wàn) 靜，等.基于模糊 C-均值的空間不確定數(shù)據(jù)聚類(lèi)［J］.計(jì)算機(jī)工程，2015，41（10）：47-52.

英文引用格式：Xiao Yupeng，He Yunbin，Wan Jing，et al.Clustering of Space Uncertain Data Based on Fuzzy C-means［J］.Computer Engineering，2015，41（10）：47-52.

1000-3428（2015）10-0047-06

A

TP18

黑龍江省自然科學(xué)基金資助項(xiàng)目（F201014，F(xiàn)201134，F(xiàn)201302）；黑龍江省教育廳科學(xué)技術(shù)研究基金資助項(xiàng)目（12531120，12541128，12511100）。

肖宇鵬（1986-），男，碩士，主研方向：空間數(shù)據(jù)挖掘；何云斌（通訊作者），教授；萬(wàn) 靜，教授、博士；李 松，副教授、博士。

2014-09-24

2014-11-13E-m ail：pengF-14@163.com