基于速度加速度的子空間聚類算法

聚類分析是數(shù)據(jù)挖掘中非?；钴S的研究領(lǐng)域。聚類是將給定的數(shù)據(jù)集劃分成不同類別（或稱為一個聚類），使同一類別中個體的相似度盡可能大，而不同類別中個體的相似度盡可能小。聚類可以發(fā)現(xiàn)屬性之間所存在的聯(lián)系，從而找出數(shù)據(jù)分布的模式，目前它已經(jīng)廣泛應(yīng)用于模式識別、數(shù)據(jù)分析、圖象處理和市場分析。聚類分析所涉及的領(lǐng)域包括：數(shù)據(jù)挖掘、統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)、空間數(shù)據(jù)技術(shù)、生物學(xué)、市場學(xué)等。

隨著數(shù)據(jù)量的快速增大，數(shù)據(jù)往往是具有很多特征，即現(xiàn)實(shí)中的數(shù)據(jù)大多是高維度數(shù)據(jù)集，而高維度的數(shù)據(jù)往往是稀疏的（即不存在全部維度上都密集的聚類），又因?yàn)榫垲愃惴ǖ臅r間復(fù)雜度往往會隨著維度的增加而快速的增大，故而，高維度數(shù)據(jù)空間中的子空間聚類是很有效的一種獲取有用信息的方法。

3 算法實(shí)驗(yàn)結(jié)果及分析
評估一種邊界點(diǎn)檢測算法的標(biāo)準(zhǔn)主要有兩個方面：算法的有效性（正確性）和執(zhí)行效率。有效性意味著算法能夠準(zhǔn)確地檢測出聚類的邊界點(diǎn)；執(zhí)行效率高意味著算法不僅可以應(yīng)用在小型數(shù)據(jù)集上，而且可以應(yīng)用到大型數(shù)據(jù)集上，有很好的擴(kuò)展性。下面，我們從這兩方面對算法做出評估。

3.1有效性分析
我們使用一個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果和一個數(shù)據(jù)集的理論分析來說明問題。

1、為了直觀地說明算法的有效性，本文使用二維數(shù)據(jù)集進(jìn)行測試。

原圖 CLIQUE          BAS-CLIQUE

圖4 兩種算法實(shí)驗(yàn)結(jié)果比較

圖4為包含8486個數(shù)據(jù)對象的數(shù)據(jù)集，從實(shí)驗(yàn)結(jié)果可以看出來，CLIQUE把聚類邊界的很多數(shù)據(jù)點(diǎn)歸為噪聲，造成了精度的下降，這也是很多基于網(wǎng)格的聚類算法都存在的問題即邊界的檢測問題。而改進(jìn)后的BAS-CLIQUE算法，在聚類的邊界處使用間隔之間數(shù)據(jù)點(diǎn)個數(shù)變化的速度和加速度參數(shù)，使聚類邊界得到了很好的柔化，能較好地避免邊界點(diǎn)的損失，提高聚類精度。

2、數(shù)據(jù)集理論分析。

我們從理論上的示例數(shù)據(jù)集來說明算法的效果。

圖5在示例數(shù)據(jù)集上進(jìn)行理論說明

如圖5，使用CLIQUE算法，如果設(shè)定的密度閾值過高，則兩個菱形中的稀薄區(qū)域?qū)⒉粫话诰垲愔?；如果密度閾值過低，則左右兩個菱形會被認(rèn)為是同一個聚類（因?yàn)殚g隔t2的數(shù)據(jù)點(diǎn)密度比較大，CLIQUE會認(rèn)為它與t1和t3同屬于一個聚類）。

而BAS-CLIQUE加入了速度和加速度參數(shù)來增加聚類邊界的精確度，由t1、t2到t3，密度變化的趨勢為先減后加，加速度會超過給定標(biāo)準(zhǔn)（因?yàn)樗俣鹊淖兓容^大），我們會認(rèn)為t2是聚類的邊界；同時在兩個菱形的稀薄區(qū)域，密度變化的趨勢都為逐漸減小，加速度不會超過給定標(biāo)準(zhǔn)，我們會得到較CLIQUE更為精確的聚類形狀。

3.2 時間復(fù)雜度分析
本算法對CLIQUE算法主要做了兩點(diǎn)改進(jìn)：

1、在每一維查找密集單元時，通過間隔內(nèi)密度的速度和加速度進(jìn)行聚類。對每一個滿足密度閾值的密集單元進(jìn)行一次遍歷，計算速度和加速度并進(jìn)行合并，此項(xiàng)操作會增加密集單元的掃描次數(shù)，只增加線性的時間復(fù)雜度，在總體算法時間復(fù)雜度方面沒有影響。但此項(xiàng)操作可以有效地減少密集單元的個數(shù)(因?yàn)樯闪俗赃m應(yīng)間隔，而自適應(yīng)間隔可能有固定間隔幾倍的跨度范圍)，進(jìn)而減少在以后剪枝操作中的遍歷次數(shù)，在最壞的情況下，即每一個密集間隔與其他密集間隔都不相鄰，將會產(chǎn)生與CLIQUE相同的時間復(fù)雜度。

2、在剪枝的操作過程中，考慮速度和加速度的因素，會增加線性的時間復(fù)雜度，在總體算法時間復(fù)雜度方面沒有影響。

綜上，BAS-CLIQUE相比CLIQUE，時間復(fù)雜度相同，通常情況下效率更高一點(diǎn)(最壞情況下與CLIQUE相同O(Cd+md) ，其中m是輸入數(shù)據(jù)點(diǎn)數(shù)，C為常數(shù)，d是數(shù)據(jù)空間的維度)。

4結(jié)論及進(jìn)一步工作
本文提出了基于速度加速度的子空間檢測算法，該算法基于CLIQUE，在尋找密集單元和剪枝的過程中利用速度和加速度進(jìn)行了優(yōu)化，能有效地提高CLIQUE的精確度和計算效率。但本算法增加了一個參數(shù)（在本文2.2中表述，加速度參數(shù)取速度參數(shù)的常數(shù)倍數(shù)），下一步我們將在更多數(shù)據(jù)集包括真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以證明算法的有效性，及采取有效措施減小參數(shù)對聚類結(jié)果的影響。