一种基于图像去噪的多密度网格聚类算法

田宇　罗辛

摘 要：针对传统网格聚类算法仅能够去除空网格的问题，提出一种基于图像分割思想来剔除稀疏数据的多密度网格聚类算法。该算法对原始数据进行网格划分和数据映射，计算网格密度，将每个网格看作图像中的一个像素点，采用Otsu算法确定合适阈值，并给出了阈值应用于网格聚类算法时的阈值折合公式，完成稀疏单元的剔除。在聚类过程中考虑到网格单元内部特征，通过两个网格的相对密度及边界特征得到了相邻网格的相似度度量公式，弥补了网格聚类算法无法应对多密度数据的缺点。在Matlab中进行仿真实验，该算法在聚类之前对网格剔除率为69%，且不需要人工干预，而GAMD和SNN算法未剔除网格。当数据维度增加时，GAMD算法时间远远高于本算法。实验证明，该算法具有较好的数据过滤效果，聚类结果与数据输入顺序无关，在得到任意簇的同时，保证了较高的时间效率且能够广泛应用于各种数据集。

关键词：网格聚类；多密度；高维稀疏数据；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 概述

聚类算法的目的是将一组未知类别的数据样本进行划分，以期找到隐藏在数据集中的潜在结构，并采用相似性度量方法，将具有相似性质的数据归于同一类，不相似性质的数据尽可能的分开 [1，2，3]。随着聚类算法不断成熟，对聚类算法有了更加特殊的要求，除了能够在多密度数据集条件下发现任意形状的簇，聚类结果与数据输入顺序无关外，还要能够应对高维度数据集的聚类要求。

目前，聚类算法主要有基于密度的方法，基于层次的方法[4]，基于网格的方法[5，6]，基于划分的方法[7]，以及基于模型的方法[8]。其中，基于密度的方法能够较好地发现任意形状的簇，但该方法需要计算每个点与其它点的距离，时间代价过高。此外，基于网格的聚类方法采用归一化的密度处理，处理多密度数据的聚类能力欠佳，并且起始网格顺序对其影响较大。

由于高维稀疏数据存在较多的噪声信息，一般的聚类算法往往得不到准确的聚类结果。共享邻近（Shared Nearest Neighbor，SNN）算法[9]很好地解决了针对不同密度和不同形状簇的聚类问题，但SNN对于噪声的处理效果欠佳，时间复杂度为O（N2） 。STING[10]聚类算法受网格结构的最底层的粒度制约，粒度过细处理代价会明显增大，粒度过粗又会降低算法效率。李光兴，杨燕等提出的GAMD算法[11]采用数据单元密度和网格质心反映单元内数据分布特征，首先统计网格的密度，再计算每个网格的质心，将这两个量值与其相邻网格对应结果的进行相似性对比，时间效率较高。但该算法没有考虑高维数据的稀疏性，将大量的稀疏单元加入了两两比较的计算过程。而高维数据集的稀疏空间远远大于有效空间，这将导致极低的算法效率，无法应对大数据环境下的聚类要求。

为了解决稀疏单元对聚类算法的影响，采用图像分割思想剔除噪声。在图像处理领域，学者们采用图像分割算法将前景与背景分开，这与聚类算法寻找簇的目标一致。采用图像分割思想，将簇看作前景，稀疏数据看作背景，对聚类中的稀疏数据进行过滤，以减少聚类过程中的数据量，提高算法效率。

2 MACD算法思想

本文提出了一种基于图像去噪的多密度网格聚类算法（A multi mesh density clustering algorithm based on image denoising，简称MDCA算法）。对高维空间进行网格划分，统计网格密度，通过最大类间方差算法[12-13]（大津算法Otsu），过滤稀疏单元，再进行聚类过程。同时在聚类过程中充分考虑到网格内部特征，提出了用于度量相邻网格相似度的相似性函数。

2.1 大津算法

Otsu是于1987年提出的一种对图像进行有效分割的算法，因其分割效果好，适用范围广泛，简单有效。该算法思想是：以图像的灰度等级作为依据，将图像分成目标和背景两部分。图像的目标和背景的差别越大，则目标和背景之间的类间方差越大。若将部分背景错分为目标或将部分目标错分为背景都会导致两部分差别变小[14]。因此，错分概率最小时所得到的类间方差即为最理想的分割。

3 MDCA算法描述

MDCA算法由数据过滤、聚类两个过程组成。在阈值选择阶段，通过Otsu算法选取合适阈值，在聚类过程中采用相似性函数寻找相似单元。

3.1 MDCA算法步骤

算法MDCA

输入：n维空间上共N个数据点，相似阈值ζ

输出：聚类结果集合

（1） 划分网格。将数据的每一维空间以 的大小划分为r个等长且无重合的单元，从而得到了一个有rn个单元的网格空间S。

（2） 将全部数据点映射到网格空间S，计算每个网格的密度并标记为j，j∈[0， rn]。

（3） 根据Otsu算法计算噪声过滤阈值 ，将密度低于 的所有单元剔除。

（4） 在j中随机选择一个单元作为起始单元，选择其相邻单元，根据相似度函数和相似阈值ζ，度量其归属关系，若相邻网格与起始单元属于同一个簇，则以相邻单元为基础，寻找其相似网格；若相邻网格与起始单元不属于同一个簇，则标记为待处理单元。如此反复，直到无相邻相似单元为止。

（5） 从剩余的未标记的单元中随机选取一个单元作为新的起始单元，并重复步骤（4），直到无剩余的未标记单元为止。

（6） 确定待处理单元的数据归属。

（7） 将相似单元的数据进行提取合并，输出聚类结果。

相似阈值ζ表示的是两个相邻单元的相似程度，ζ越大两个单元的相似性越高，与全局数据无关。且相似性函数符合对称原则，与输入顺序无关。

4 实验评估

算法验证实验在win7操作系统下进行，采用MATLAB编程实现。MDCA网格划分大小为 四舍五入后的整数。

4.1 算法有效性评估

二维数据集采用MATLAB人工合成，原始数据总数：2 717个。为了保证算法可以应对非球状簇，数据集主要由“Clustering”与随机生成的噪声构成，噪声数据点为：728个，如图1所示。

比较维数高低与时间的关系时，将数据总量固定为2000个，维数从2维增加到10维。MDCA算法与GAMD算法，SNN算法的时间效率的比较如图1所示。虽然MDCA算法与GAMD算法均为线性，但是当维度增加时两者的差不断增大，MDCA算法有比GAMD算法更好的效率，其执行时间与维数大小关系如表4-1所示：

5 结束语

评估噪声数量与MDCA算法和GAMD算法时间效率的关系实验中，保持目标数据量不变，其占据的网格单元传统的网格聚类算法在应对稀疏数据时，算法效率较低。而本文提出的MDCA算法采用图像分割思想，阈值折合公式能有效剔除稀疏单元。同时，由于MDCA算法在聚类过程中考虑到网格的内部特征，提出的相似性函数能有效识别相似网格。实验证明，该算法对噪声过滤效果好，执行效率高，可以较好地识别不同形状的簇，聚类结果与数据输入顺序无关。而本文中网格划分的大小采用统一的划分策略，进一步的研究方向为网格划分的大小由网格数据密度决定，全局采用多个划分标准，网格粒度与数据密度相关联。

参考文献

[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.