田宇　羅辛

摘 要：針對傳統(tǒng)網(wǎng)格聚類算法僅能夠去除空網(wǎng)格的問題，提出一種基于圖像分割思想來剔除稀疏數(shù)據(jù)的多密度網(wǎng)格聚類算法。該算法對原始數(shù)據(jù)進行網(wǎng)格劃分和數(shù)據(jù)映射，計算網(wǎng)格密度，將每個網(wǎng)格看作圖像中的一個像素點，采用Otsu算法確定合適閾值，并給出了閾值應用于網(wǎng)格聚類算法時的閾值折合公式，完成稀疏單元的剔除。在聚類過程中考慮到網(wǎng)格單元內(nèi)部特征，通過兩個網(wǎng)格的相對密度及邊界特征得到了相鄰網(wǎng)格的相似度度量公式，彌補了網(wǎng)格聚類算法無法應對多密度數(shù)據(jù)的缺點。在Matlab中進行仿真實驗，該算法在聚類之前對網(wǎng)格剔除率為69%，且不需要人工干預，而GAMD和SNN算法未剔除網(wǎng)格。當數(shù)據(jù)維度增加時，GAMD算法時間遠遠高于本算法。實驗證明，該算法具有較好的數(shù)據(jù)過濾效果，聚類結果與數(shù)據(jù)輸入順序無關，在得到任意簇的同時，保證了較高的時間效率且能夠廣泛應用于各種數(shù)據(jù)集。

關鍵詞：網(wǎng)格聚類；多密度；高維稀疏數(shù)據(jù)；Otsu；聚類算法

中圖分類號：TP391 文獻標志碼：A 文章編號：2095-2163（2016）01-

【Abstract】Based on the situation that the traditional grid clustering algorithm is only capable of removing empty grid issues，the paper presents an image segmentation thought to weed out the sparse data of multi-density grid clustering algorithm. The algorithm of the original data and data mapping mesh， mesh density calculation， each grid as a picture of a pixel， using Otsu algorithm to determine the appropriate threshold， and gives a reduced threshold algorithm formula while the threshold applies to the grid clustering ， and completes culling sparse unit. In the clustering process， taking into account the internal characteristics of grid cells， characterized by the relative density and the border of the two grids ，similarity measure formula of adjacent grid is achieved， which makes up for the shortcomings of grid clustering algorithm that the grid can not cope with multi-density data . Conducted in Matlab simulation， culling rate is 69% before the algorithm clustering grid， and does not require human intervention， and GAMD and SNN algorithm does not reject grid. When the data dimension increases， SNN algorithm time is much higher than the present algorithm. Experiments show that the algorithm has better filtering effect data， independent of the data input sequence clustering results， getting any cluster， while ensuring a high time efficiency， and can be widely applied to various data sets.

【Key words】 Grid Cluster； Multi-Density；High-dimensional Sparse Data；Otsu； Clustering

1 概述

聚類算法的目的是將一組未知類別的數(shù)據(jù)樣本進行劃分，以期找到隱藏在數(shù)據(jù)集中的潛在結構，并采用相似性度量方法，將具有相似性質(zhì)的數(shù)據(jù)歸于同一類，不相似性質(zhì)的數(shù)據(jù)盡可能的分開 [1，2，3]。隨著聚類算法不斷成熟，對聚類算法有了更加特殊的要求，除了能夠在多密度數(shù)據(jù)集條件下發(fā)現(xiàn)任意形狀的簇，聚類結果與數(shù)據(jù)輸入順序無關外，還要能夠應對高維度數(shù)據(jù)集的聚類要求。

目前，聚類算法主要有基于密度的方法，基于層次的方法[4]，基于網(wǎng)格的方法[5，6]，基于劃分的方法[7]，以及基于模型的方法[8]。其中，基于密度的方法能夠較好地發(fā)現(xiàn)任意形狀的簇，但該方法需要計算每個點與其它點的距離，時間代價過高。此外，基于網(wǎng)格的聚類方法采用歸一化的密度處理，處理多密度數(shù)據(jù)的聚類能力欠佳，并且起始網(wǎng)格順序?qū)ζ溆绊戄^大。

由于高維稀疏數(shù)據(jù)存在較多的噪聲信息，一般的聚類算法往往得不到準確的聚類結果。共享鄰近（Shared Nearest Neighbor，SNN）算法[9]很好地解決了針對不同密度和不同形狀簇的聚類問題，但SNN對于噪聲的處理效果欠佳，時間復雜度為O（N2） 。STING[10]聚類算法受網(wǎng)格結構的最底層的粒度制約，粒度過細處理代價會明顯增大，粒度過粗又會降低算法效率。李光興，楊燕等提出的GAMD算法[11]采用數(shù)據(jù)單元密度和網(wǎng)格質(zhì)心反映單元內(nèi)數(shù)據(jù)分布特征，首先統(tǒng)計網(wǎng)格的密度，再計算每個網(wǎng)格的質(zhì)心，將這兩個量值與其相鄰網(wǎng)格對應結果的進行相似性對比，時間效率較高。但該算法沒有考慮高維數(shù)據(jù)的稀疏性，將大量的稀疏單元加入了兩兩比較的計算過程。而高維數(shù)據(jù)集的稀疏空間遠遠大于有效空間，這將導致極低的算法效率，無法應對大數(shù)據(jù)環(huán)境下的聚類要求。

為了解決稀疏單元對聚類算法的影響，采用圖像分割思想剔除噪聲。在圖像處理領域，學者們采用圖像分割算法將前景與背景分開，這與聚類算法尋找簇的目標一致。采用圖像分割思想，將簇看作前景，稀疏數(shù)據(jù)看作背景，對聚類中的稀疏數(shù)據(jù)進行過濾，以減少聚類過程中的數(shù)據(jù)量，提高算法效率。

2 MACD算法思想

本文提出了一種基于圖像去噪的多密度網(wǎng)格聚類算法（A multi mesh density clustering algorithm based on image denoising，簡稱MDCA算法）。對高維空間進行網(wǎng)格劃分，統(tǒng)計網(wǎng)格密度，通過最大類間方差算法[12-13]（大津算法Otsu），過濾稀疏單元，再進行聚類過程。同時在聚類過程中充分考慮到網(wǎng)格內(nèi)部特征，提出了用于度量相鄰網(wǎng)格相似度的相似性函數(shù)。

2.1 大津算法

Otsu是于1987年提出的一種對圖像進行有效分割的算法，因其分割效果好，適用范圍廣泛，簡單有效。該算法思想是：以圖像的灰度等級作為依據(jù)，將圖像分成目標和背景兩部分。圖像的目標和背景的差別越大，則目標和背景之間的類間方差越大。若將部分背景錯分為目標或?qū)⒉糠帜繕隋e分為背景都會導致兩部分差別變小[14]。因此，錯分概率最小時所得到的類間方差即為最理想的分割。

3 MDCA算法描述

MDCA算法由數(shù)據(jù)過濾、聚類兩個過程組成。在閾值選擇階段，通過Otsu算法選取合適閾值，在聚類過程中采用相似性函數(shù)尋找相似單元。

3.1 MDCA算法步驟

算法MDCA

輸入：n維空間上共N個數(shù)據(jù)點，相似閾值ζ

輸出：聚類結果集合

（1） 劃分網(wǎng)格。將數(shù)據(jù)的每一維空間以 的大小劃分為r個等長且無重合的單元，從而得到了一個有rn個單元的網(wǎng)格空間S。

（2） 將全部數(shù)據(jù)點映射到網(wǎng)格空間S，計算每個網(wǎng)格的密度并標記為j，j∈[0， rn]。

（3） 根據(jù)Otsu算法計算噪聲過濾閾值 ，將密度低于 的所有單元剔除。

（4） 在j中隨機選擇一個單元作為起始單元，選擇其相鄰單元，根據(jù)相似度函數(shù)和相似閾值ζ，度量其歸屬關系，若相鄰網(wǎng)格與起始單元屬于同一個簇，則以相鄰單元為基礎，尋找其相似網(wǎng)格；若相鄰網(wǎng)格與起始單元不屬于同一個簇，則標記為待處理單元。如此反復，直到無相鄰相似單元為止。

（5） 從剩余的未標記的單元中隨機選取一個單元作為新的起始單元，并重復步驟（4），直到無剩余的未標記單元為止。

（6） 確定待處理單元的數(shù)據(jù)歸屬。

（7） 將相似單元的數(shù)據(jù)進行提取合并，輸出聚類結果。

相似閾值ζ表示的是兩個相鄰單元的相似程度，ζ越大兩個單元的相似性越高，與全局數(shù)據(jù)無關。且相似性函數(shù)符合對稱原則，與輸入順序無關。

4 實驗評估

算法驗證實驗在win7操作系統(tǒng)下進行，采用MATLAB編程實現(xiàn)。MDCA網(wǎng)格劃分大小為 四舍五入后的整數(shù)。

4.1 算法有效性評估

二維數(shù)據(jù)集采用MATLAB人工合成，原始數(shù)據(jù)總數(shù)：2 717個。為了保證算法可以應對非球狀簇，數(shù)據(jù)集主要由“Clustering”與隨機生成的噪聲構成，噪聲數(shù)據(jù)點為：728個，如圖1所示。

比較維數(shù)高低與時間的關系時，將數(shù)據(jù)總量固定為2000個，維數(shù)從2維增加到10維。MDCA算法與GAMD算法，SNN算法的時間效率的比較如圖1所示。雖然MDCA算法與GAMD算法均為線性，但是當維度增加時兩者的差不斷增大，MDCA算法有比GAMD算法更好的效率，其執(zhí)行時間與維數(shù)大小關系如表4-1所示：

5 結束語

評估噪聲數(shù)量與MDCA算法和GAMD算法時間效率的關系實驗中，保持目標數(shù)據(jù)量不變，其占據(jù)的網(wǎng)格單元傳統(tǒng)的網(wǎng)格聚類算法在應對稀疏數(shù)據(jù)時，算法效率較低。而本文提出的MDCA算法采用圖像分割思想，閾值折合公式能有效剔除稀疏單元。同時，由于MDCA算法在聚類過程中考慮到網(wǎng)格的內(nèi)部特征，提出的相似性函數(shù)能有效識別相似網(wǎng)格。實驗證明，該算法對噪聲過濾效果好，執(zhí)行效率高，可以較好地識別不同形狀的簇，聚類結果與數(shù)據(jù)輸入順序無關。而本文中網(wǎng)格劃分的大小采用統(tǒng)一的劃分策略，進一步的研究方向為網(wǎng)格劃分的大小由網(wǎng)格數(shù)據(jù)密度決定，全局采用多個劃分標準，網(wǎng)格粒度與數(shù)據(jù)密度相關聯(lián)。

參考文獻

[1] JAIN A K. Data clustering： 50 years beyond K-means[J]. Pattern Recognition Letters， 2010，31（8）：651?666.

[2] SUN J G， LIU J， ZHAO L Y. Clustering algorithms research[J]. Journal of Software， 2008，19（1）：48?61 .

[3] ZHU L， LEI J S， BI Z Q， et al. Soft subspace clustering algorithm for streaming data[J]. Journal of Software， 2013，24（11）：2610-2627 .

[4] ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of 2nd International conference on Knowledge Discovery and Data-mining（KDD 1996）. Portland， Oregen：AAAI Press， 1996， 96（34）： 226-231.

[5] WANG Wei，YANG Jiong， MUNTZ R R. STING：A statistical information grid approach to spatial data mining[C]// VLDB97 Proceedings of the 23rd Internationgal Conference on Very Large Databases.San Francisco， CA， USA：Mogan Kaufmann Publishers， 1997：186-195.

[6] AFRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[J]. Data Mining& Knowledge Discovery， 1999，27（2）：94-105.

[7] KAUFMAN L，ROUSSEEUW P J. Finding Groups in Data：An Intro duction to Cluster Analysis[M].New York：John Wiley & Sons，1990.

[8] FISHER D.Improving inference through conceptual clustering[C]// AAAI87 Proceeding of the sixth National Conference on Artificial intelligence. Seattle，WA：AAAI Press， 1987，2：461-465.

[9] ERT?Z L， STEINBACH M， KUMAR V. Finding clusters of different sizes， shapes， and densities in noisy， high dimensional data[C]//Siam International Conference on Data Mining. San Francisco，CA， USA：DBLP， 2003： 47-58.

[10] YIN G， YU X， NING H. Incremental clustering algorithm based on grid [J]. Application Research of Computers， 2009，26（6）： 2038-2040.

[11] LI G X， YANG Y. Multi-density clustering algorithm based on grid adjacency Relation[C]//Pattern Recognition （CCPR）， 2010 Chinese Conference on. Chongqing： IEEE， 2010： 1-5.

[12] OTSU N. A threshold selection method from gray-level histograms[J]. Automatica， 1975， 11（285-296）： 23-27.

[13] WU chengmao. Regularization Otsu s thresholding method based on Posterior Probability Entropy[J]. Acta Electronica Sinica， 2013， 41（12）： 2474-2478.

[14] YANG M， WANG W X. Rock discontinuity spacing measurement based on image technique[J]. Journal of Computer Applications， 2010， S1：146-147，158.