一種基于圖像去噪的多密度網(wǎng)格聚類(lèi)算法

田宇　羅辛

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

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

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 概述

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

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

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

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

2 MACD算法思想

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

2.1 大津算法

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

3 MDCA算法描述

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

3.1 MDCA算法步驟

算法MDCA

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

輸出：聚類(lèi)結(jié)果集合

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

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

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

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

（5） 從剩余的未標(biāo)記的單元中隨機(jī)選取一個(gè)單元作為新的起始單元，并重復(fù)步驟（4），直到無(wú)剩余的未標(biāo)記單元為止。

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

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

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

4 實(shí)驗(yàn)評(píng)估

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

4.1 算法有效性評(píng)估

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

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

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

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

參考文獻(xià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.