下载文档原格式
基于网格局部密度的聚类算法
马莹波
【期刊名称】《林区教学》
【年(卷),期】2011(000)003
【摘要】为了使基于网格的聚类技术适用于多密度数据集,提出一种基于局部密度的聚类算法.算法提出将数据单元格密度分类的方法,使得具有不同密度的单元格使用不同密度阈值的进行聚类.同时给出了边界单元的处理方法以提高聚类结果的精度.实验结果表明,GLD算法比其他类似算法有较高的聚类精度和效率.
【总页数】2页(P95-96)
【作者】马莹波
【作者单位】南京信息工程大学,计算机与软件学院,南京,210044
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于局部密度聚类算法的变压器故障状态评估 [J], 罗伟明;吴帆;黄业广;吴杰康;覃炜梅;龚杰;金尚婷
2.基于局部密度和动态生成网格聚类算法 [J], 邱保志;郑智杰
3.一种基于局部密度的网格排序聚类算法 [J], 刘建军;周廷英
4.基于改进力导向模型和局部密度的聚类算法 [J], 刘风剑; 刘向阳
5.基于局部密度的最小生成树聚类算法及其在电力大数据的应用 [J], 靳文星;王电钢;张哲敏
因版权原因，仅展示原文概要，查看原文内容请购买。
halcon聚类算法
（原创实用版）
目录
1.聚类算法概述
2.halcon 聚类算法介绍
3.halcon 聚类算法的特点
4.halcon 聚类算法的应用实例
5.halcon 聚类算法的优缺点
正文
聚类算法是数据挖掘和机器学习领域中一种重要的无监督学习算法，其主要目的是将相似的数据点划分到同一类别中，从而实现数据的分类。
halcon 聚类算法是众多聚类算法中的一种，它是基于网格结构和距离度量来对数据进行聚类的。
halcon 聚类算法的全称是"A 网格为基础的聚类算法"，它是由Hartigan 和 Lemon 提出的。
该算法的主要思想是将数据空间划分为网格结构，然后根据数据点到网格节点的距离度量来对数据进行聚类。
具体来说，halcon 算法首先将数据空间划分为网格结构，然后计算每个数据点到网格节点的距离，最后将距离最近的数据点划分到同一类别中。
halcon 聚类算法具有以下特点：
1.可以处理任意形状的数据集，不仅仅局限于凸集；
2.可以处理大规模数据集，因为其时间复杂度为 O(n)，其中 n 为数据点的数量；
3.可以灵活地设置聚类参数，如网格密度和距离度量等。
halcon 聚类算法在许多领域都有广泛应用，例如数据挖掘、模式识
别、图像处理等。
例如，在图像处理中，可以使用 halcon 聚类算法对图像中的颜色进行聚类，从而实现图像的彩色分割。
尽管 halcon 聚类算法具有许多优点，但也存在一些缺点，如对离群点和噪声敏感，以及在处理大规模数据集时计算量较大等。
一种基于网格密度的聚类算法
摘要：提出了一种基于网格密度的聚类算法（dgca）。
该算法主要利用网格技术去除数据集中的部分孤立点或噪声数据，对类的边缘节点使用一种边缘节点判断函数进行提取，最后利用相近值的方法进行聚类。
实验表明，dgca算法能够很好地识别出孤立点或噪声，聚类结果可以达到一个较高的精度。
关键词：网格聚类；边界点；网格密度
中图分类号：tp312文献标识码：a文章编号：1672-7800（2012）012-0056-02
0引言
聚类是把一组数据按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的距离尽可能地小而不同类别上的个体间
的距离尽可能地大。
聚类的结果可以得到一组数据对象的集合，称其为簇或类。
簇中的对象彼此相似，而与其它簇中的对象相异。
迄今为止，已经提出了许多聚类算法，大体上这些算法可以分为基于距离的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等。
基于网格的聚类算法首先将d维数据空间的每一维平均分割成等长的区间段，即把数据空间分割成一些网格单元。
若一个网格单元中所含数据量大于给定的值，则将其定为高密度单元；否则将其视为低密度单元。
如果一个低密度网格单元的相邻单元都是低密度
的，则视这个低密度单元中的节点为孤立点或噪声节点。
网格聚类就是这些相邻的高密度单元相连的最大集合。
1基本概念
1.1相近值
网格单元内节点之间的相近值是利用节点间的距离来计算的。
节点间的相近值越大，它们就越相似。
即对这些网格单元内的节点进行聚类时，它们属于同一个类的可能性就越大。
定义1节点集：设p=（u，k），我们用p表示n条记录的集合。
u={u1，u2，…，un}代表网格单元内的节点集
k={k1，k2，…，kr}代表网格单元内节点的属性
其中，i，i∈（1，2，…，n），kim，m∈（1，2，…，r）代表节点ui的第m个属性km，因此，用km代表一个r维的向量（ki1，ki2，…，kir），i∈（1，2，…，n）。
定义 2 相异值：任意两个节点ui与uj之间的相异值定义如下：d（i，j）=∑rm=1|kim-kjm|，i， j=1，2，…，n（1）定义 3 相近值：任意两个节点ui与uj之间的相近值定义如下：s（i，j）=maxdf-d（i，j）（2）其中，maxdf=max1≤i，j≤nd（i， j）代表网格单元中节点间的最大相异值。
1.2边缘节点判断函数
在传统的网格聚类算法中，将与高密度单元相邻的低密度单元中的节点作为孤立点或噪声数据丢弃，这样会丢失一些有用的边缘节
点。
为提高聚类的精度，在dgca算法中引入边缘节点判断函数minf （i），其定义如下：minf（i）=（maxsim1≤j≤n（i，j）+avesim （i））/2（3）其中，maxsim1≤j≤n（i，j）=max{j︱s（i，j），1≤j≤n}，avesim（i）=1n∑nj=1s（i，j）
边缘节点函数borderf（i），其定义如下：borderf（i）=1hd∑hdi=1s（i，l）（4）其中，hd表示高密度单元中节点的个数。
边缘节点处理的方法是：如果一个高密度网格单元的相邻网格单元中有低密度单元，就使用边缘节点函数borderf（i）检查这些低密度单元中的节点i，如果borderf（i）的值大于等于设定的边缘节点判断函数值minf（i），那么判定节点i是此高密度单元的边界点，即i与此高密度单元中的节点属于一类。
这样就可以将有用的边缘节点提取出来，从而提高聚类的质量。
2dgca聚类算法
dgca聚类算法的基本思想：①将所有节点集u映射到数据空间相应的网格单元中；②根据用户输入的密度测试值minpts判断每个网格单元是低密度还是高密度网格单元，如果是高密度网格单元，则对其相邻的低密度网格单元中的节点，利用minf（i）判断各个节点是否为该高密度网格的边缘节点，如果是即提取边缘节点，如果不是就把该节点认为是孤立点或噪声数据；③根据用户输入的相近测试值minsim，对去除孤立点或噪声数据后的节点，使用相近值方法进行聚类，即如果任意两个节点的相近值s（i， j）大于或等
于给定的测试值minsim，就把这两个数据对象视为同一个类中的数据。
dgca算法如下：
输入：z，minpts，minsim
输出：类，孤立点或噪声数据
步骤1：根据用户输入的z值将整个数据空间x划分成zr个网格单元。
步骤2：将节点集u映射到网格单元中。
步骤3：逐一扫描每个网格单元，并记录每个网格单元中的节点个数cell[q].count（1≤q≤zr）。
步骤4：根据密度阈值将网格单元分为高密度单元和低密度单元。
步骤5：考虑每个高密度单元，如果其相邻网格单元有低密度的，利用边缘节点判断函数提取有用的边缘节点，低密度单元中剩余的节点作为孤立点或噪声数据丢弃。
步骤6：考虑高密度单元中的任意两个节点，如果其相似值大于给定的minsim值，则将这两个对象归于一类。
3实验结果与分析
本实验所使用的pc具有1g内存，奔腾ⅳcpu 2.40ghz，使用的操作系统是windows xp professional，算法是用vc++进行编程设计的。
3.1精度对比（综合数据集）
实验中图1对应的节点数据集是来自于参考文献，此节点集含有5 034条记录，从该图中可以直观地看到，此节点集应该被分为5类。
实验结果显示，算法dgca的结果是5个类，由于使用了边缘节点判断函数，孤立点或噪声被有效地识别出来，使得dgca算法的精度明显好于传统的网格聚类算法clique，dgca算法中的参数：z=100，minpts=10，minsim=198。
3.2时间对比
由于dgca算法的时间复杂度是o（n2），所以该算法的时间效率还有待改进。
4结语
本文提出了一种基于网格密度的聚类算法（dgca）。
该算法主要利用网格技术去除节点数据集中的部分孤立点或噪声节点，对类的边缘节点使用一种边缘节点判断函数进行提取，最后利用相近值的方法进行聚类。
实验表明，dgca算法与传统的聚类方法相比，聚类的精度有了很大的提高。
它不仅适用于综合节点数据集，而且对高维节点数据集也能够得到令人满意的聚类结果和聚类质量。
参考文献：
[1]罗静，刘宗歧.基于网格聚类算法的电力营销预测研究[j].科技信息，2012（3）.
[2]邱保志，沈钧毅.基于扩展和网格的多密度聚类算法[j].控制与决策，2006（9）.
[3]张鸿雁，刘希玉.一种网格聚类的边缘检测算法[j].控制与决策，2011（12）.
[4]邱保志，沈钧毅.网格聚类中的边界处理技术[j].模式识别与人工智能，2006（2）.
[5]levent ertoz，michael steinbach，vipin kumar.finding clusters of different sizes，shapes，and densities in noisy，high dimensional data[c].in siam international conference on data mining，2003.
（责任编辑：余晓）。
