下载文档原格式
基于密度与分形维数的数据流聚类算法金建业;倪志伟;汪莎【摘要】提出一种基于密度与分形维数的数据流聚类算法.采用在线/离线的两阶段框架,结合密度聚类和分形聚类的优点,克服传统数据流聚类算法的不足.针对数据流的时效性,在计算网格密度时对数据点使用衰减策略.实验结果表明,该算法能有效提高数据流聚类效率及聚类精度,且可以发现任意形状和距离非邻近的聚类.%Considering deficiencies of some popular data stream clustering algorithms, a data stream clustering algorithm based on density and fractal dimension is presented. It consists of two phases of online and offline processing, combined with the advantages of density clustering and fractal clustering. The deficiency of the traditional clustering algorithm is overcome. In the algorithm, a density decaying strategy to reflect the timelines of data stream is adopted. Experimental results show the algorithm improves the efficiency and accuracy of data stream clustering, and can find arbitrary shapes and non-neighboring clusters.【期刊名称】《计算机工程》【年(卷),期】2012(038)005【总页数】3页(P38-40)【关键词】数据流;聚类;分形维数;衰减系数;网格;网格密度【作者】金建业;倪志伟;汪莎【作者单位】合肥工业大学管理学院;合肥工业大学过程优化与智能决策教育部重点实验室,合肥230009;合肥工业大学管理学院;合肥工业大学过程优化与智能决策教育部重点实验室,合肥230009;合肥工业大学管理学院;合肥工业大学过程优化与智能决策教育部重点实验室,合肥230009【正文语种】中文【中图分类】TP391.11 概述随着信息技术的发展，许多领域中出现了连续到达、持续增长、动态演化的数据——数据流。
高效多维数据聚类算法及其在数据挖掘中的应用在数据挖掘领域中，高效多维数据聚类算法是一个重要的研究方向。
这些算法能够对大规模、高维度的数据进行快速且准确的聚类分析，从而帮助人们发现数据中隐藏的模式和规律。
本文将介绍几种常用的高效多维数据聚类算法，并探讨它们在数据挖掘中的应用。
首先，我们将介绍一种常用的高效多维数据聚类算法：k-means算法。
k-means算法是一种基于距离的聚类算法，它通过迭代计算数据点与聚类中心之间的距离，将数据点划分到最近的聚类中心中。
该算法的时间复杂度较低，适用于处理大规模数据集。
k-means算法在数据挖掘领域中广泛应用于图像分割、文本聚类等任务中。
除了k-means算法，另一种常用的高效多维数据聚类算法是DBSCAN算法。
DBSCAN算法是一种基于密度的聚类算法，它将数据点分为核心点、边界点和噪声点三种类型。
该算法利用数据点周围的密度信息来确定聚类簇的形状和大小，能够处理复杂的数据分布。
DBSCAN算法在数据挖掘中常用于异常检测、空间数据聚类等应用中。
此外，高效多维数据聚类算法还包括层次聚类算法和密度聚类算法等。
层次聚类算法将数据点逐步合并或分割，形成嵌套的聚类层次结构。
此类算法在数据挖掘中常用于社交网络分析、生物信息学等领域。
密度聚类算法根据数据点在空间中的密度分布进行聚类，能够发现不同形状和大小的聚类簇，适用于各种类型的数据集。
高效多维数据聚类算法在数据挖掘中有广泛的应用。
首先，聚类分析能够帮助人们发现数据中的模式和规律。
例如，在市场营销领域，通过对消费者数据进行聚类分析，可以识别出不同类型的消费者群体，从而制定个性化的营销策略。
其次，聚类算法可以用于异常检测。
通过对正常数据进行聚类分析，可以建立一个模型，然后用来检测新的数据是否异常。
这在金融领域中尤为重要，可以帮助银行发现信用卡欺诈等异常行为。
另外，聚类算法还可以用于图像分析、文本挖掘、生物信息学等领域。
然而，高效多维数据聚类算法也面临一些挑战和限制。
基于分形维数的选择性聚类融合算法研究的开题报告一、研究题目基于分形维数的选择性聚类融合算法研究二、研究背景随着信息技术的快速发展和数据量的不断增加，数据挖掘和智能分析在各个领域中的应用越来越广泛。
选择性聚类算法是数据挖掘领域中的一种有用的聚类方法，能够解决大规模数据集的聚类问题，并且具有较高的效率和准确性。
然而，现有的选择性聚类算法多数基于对象之间的相似度度量，不能有效处理复杂数据结构和非线性数据的聚类问题。
分形维数是一种描述物理、生物、社会现象等自相似性现象的重要参数，被广泛应用于数字信号处理、图像识别、模式识别等领域。
基于分形维数的聚类算法能够刻画数据的自相似性特征，处理非线性和复杂的数据结构，有效提高聚类算法的准确性和稳定性。
三、研究目的本研究旨在提出一种基于分形维数的选择性聚类融合算法，解决现有选择性聚类算法无法有效处理非线性和复杂数据结构的问题，提高聚类算法的准确性和稳定性，为数据挖掘和智能分析领域的应用提供基础技术支撑。
四、研究方法和内容1. 综述选择性聚类算法和分形维数的相关研究成果，分析现有算法的不足和存在的问题。
2. 提出基于分形维数的选择性聚类融合算法，通过计算分形维数刻画数据的自相似性特征，筛选出具有代表性的核心对象，进一步进行聚类分析。
3. 在人工数据集和真实数据集上进行实验验证，评估所提算法的性能和准确性，并与现有方法进行比较。
五、研究预期成果1. 提出基于分形维数的选择性聚类融合算法，有效提高聚类算法的准确性和稳定性。
2. 在人工数据集和真实数据集上进行实验验证，证明所提算法的可行性和优越性。
3. 为数据挖掘和智能分析领域的应用提供基础技术支撑，促进相关领域的发展和进步。
六、研究计划和进度安排1. 第一年(1) 综述选择性聚类算法和分形维数的相关研究成果，分析现有算法的不足和存在的问题。
(2) 提出基于分形维数的选择性聚类融合算法，并设计实验方案，搭建实验环境。
(3) 编写实现代码，进行初步的数据分析和实验验证。
基于网格的聚类方法研究【摘要】由于已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想，分析了现有基于网格的聚类算法。
使用网格方法的数据分析方法将空间划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类，最后提出基于网格的聚类需要进一步研究的方向。
【关键词】数据挖掘；网格；聚类1 引言数据挖掘指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。
它是数据库研究中的一个很有应用价值的领域，融合了数据库、机器学习、统计学等多个领域的理论和技术。
数据挖掘中广为研究的课题之一是聚类分析，从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用信息或知识。
目前已经提出了不少著名的数据聚类算法，有CLARANS、BIRCH、DBSCAN和CLIQUE 等。
但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。
空间数据处理中常用的将空间数据离散化的方法是网格方法。
由于易于增量实现和进行高维数据处理而广泛应用聚类算法。
研究人员已经提出了很多基于网格的聚类算法，包括利用了存储在网格单元中的统计信息的STING；用一种小波转换方法来聚类数据对象的WaveCluster；在高维数据空间中基于网格和密度的聚类方的CLIQUE法等。
本文分析了从网格的表示，划分网格单元的方法，到统计网格内信息，搜索近邻网格单元，聚类超过指定阙值的网格单元的各个步骤，对已有的基于网格的聚类算法进行了研究，最后展望了基于网格方法聚类的研究方向。
2 网格的定义与划分网格的基本概念，设A1，A2，…，Ar是数据集O={O1，O2，…，On}中数据对象的r个属性的有界定义域，那W=A1×A2×…×Ar就是一个r维空间，将A1，A2，…，Ar看成是W的维（属性、字段），则对于一个包含n个数据点的r维空间中的数据集O={O1，O2，…，On}，其中Oi={Oi1，Oi2，…，Oir}（i=1，2，…，n），Oi的第j个分量Oij∈Aj。
一种改进的基于密度和网格的高维聚类算法Ξ朱 倩 黄志军(海军工程大学 武汉 430033)摘 要:提出了一种改进的基于密度和网格的高维聚类算法,并对算法有效性进行了验证。
该算法通过减少样本点数量的方法达到减少稠密子空间数量。
在发现高维稠密子空间时,对样本库进行精简。
这些样本点的求得能有效减少求解最小聚类的时间复杂度。
关键词:数据挖掘;聚类;网格;密度;高维数据;子空间;最小聚类中图分类号:TP311V alidity V alidation of An Improved High-dimensional ClusterAnalysis Algorithm B ased on G rid and IntensityZhu Q ian H u ang Zhijun(Navy University of Engineering,Wuhan 430033)Abstract:This paper proposes an improved high-dimensional cluster analysis algorithm based on grid and intensity,then dis2 cusses it’s validity validation.The amount of the density subspace can be deduced by cutting down that of sample data.The sam2 ple library is simplified as the high-dimensional subspaces are found.By working out such sample data the time complexity of fig2 uring out min cluster is effectively reduced.K ey w ords:data mining,cluster,grid,density,high-dimensional data,subspace,min clusterClass number:TP3111 引言聚类分析是数据挖掘领域中的一项重要的研究课题,同时也是一个具有很强挑战性的领域。
一种基于网格密度的聚类算法作者：刘敏娟，于景茹，张西芝来源：《软件导刊》2012年第12期摘要：提出了一种基于网格密度的聚类算法（DGCA）。
该算法主要利用网格技术去除数据集中的部分孤立点或噪声数据，对类的边缘节点使用一种边缘节点判断函数进行提取，最后利用相近值的方法进行聚类。
实验表明，DGCA算法能够很好地识别出孤立点或噪声，聚类结果可以达到一个较高的精度。
关键词：网格聚类；边界点；网格密度中图分类号：TP312文献标识码：A文章编号：1672-7800（2012）012-0056-020引言聚类是把一组数据按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的距离尽可能地小而不同类别上的个体间的距离尽可能地大。
聚类的结果可以得到一组数据对象的集合，称其为簇或类。
簇中的对象彼此相似，而与其它簇中的对象相异。
迄今为止，已经提出了许多聚类算法，大体上这些算法可以分为基于距离的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等。
基于网格的聚类算法首先将d维数据空间的每一维平均分割成等长的区间段，即把数据空间分割成一些网格单元。
若一个网格单元中所含数据量大于给定的值，则将其定为高密度单元；否则将其视为低密度单元。
如果一个低密度网格单元的相邻单元都是低密度的，则视这个低密度单元中的节点为孤立点或噪声节点。
网格聚类就是这些相邻的高密度单元相连的最大集合。
1基本概念1.1相近值网格单元内节点之间的相近值是利用节点间的距离来计算的。
节点间的相近值越大，它们就越相似。
即对这些网格单元内的节点进行聚类时，它们属于同一个类的可能性就越大。
定义1节点集：设P=（U，K），我们用P表示n条记录的集合。
U={U1，U2，…，Un}代表网格单元内的节点集K={K1，K2，…，Kr}代表网格单元内节点的属性其中，，i∈（1，2，…，n），，m∈（1，2，…，r）代表节点Ui的第m个属性Km，因此，用Km代表一个r维的向量（ki1，ki2，…，kir），i∈（1，2，…，n）。
基于多维数据的聚类算法优化随着现代技术的快速发展，大数据分析越来越成为人们重视的话题。
其中，聚类算法是一种常用的数据挖掘技术，可以将数据集中类似的数据归为一类，为数据分析和处理提供了重要的工具。
然而，传统的聚类算法存在一些缺陷。
例如，对于高维数据，传统的聚类算法往往会受到维数灾难的影响，导致效率低下；同时，传统聚类算法在处理数据时可能会受到数据形态、噪声等因素的影响，导致聚类结果不理想。
为了解决这些问题，近年来出现了基于多维数据的聚类算法。
这种算法通过将数据转化为多个维度的方式来提高聚类效率和准确率。
下面我们来具体看看基于多维数据的聚类算法的优化点。
1. 基于主成分分析的聚类算法主成分分析是一种常用的降维技术，可以将高维数据转化为低维数据，从而减小聚类算法的计算量。
在基于主成分分析的聚类算法中，通过对原始数据集进行主成分分析，得到了原始数据的主要特征，并将这些特征作为新数据的维度，从而达到了降维的目的。
这种算法可以将高维数据转化为低维数据，从而提高聚类算法的效率。
但需要注意的是，在进行主成分分析时，需要保留最主要的几个主成分，在保证聚类准确度的同时，避免因降维过度而导致信息丢失。
2. 基于模糊聚类的算法传统的聚类算法将每个数据点只归为一个类别，然而现实中的数据往往是模糊的，即某些数据点可能同时属于多个类别。
基于模糊聚类的算法考虑了这种数据的特点，通过将数据分为多个部分，并将每个部分中的数据点按照不同的权重分配到不同的类别中，从而提高了聚类的准确度和鲁棒性。
3. 基于密度的聚类算法传统的聚类算法常常将数据点看作离散的点进行聚类，而忽略了数据点的密度变化。
基于密度的聚类算法通过考虑数据点的密度信息，将数据点划分为高密度区和低密度区，并根据这些区域来进行聚类，从而使聚类结果更加鲁棒和准确。
4. 基于谱聚类的算法基于谱聚类的算法是利用图论和线性代数的一种聚类算法，它将聚类问题转化为图的谱分解问题，通过对图进行归一化拉普拉斯变换，得到图的特征向量，从而将数据点划分成不同的类别。
一种基于网格和密度的簇边缘精度增强聚类算法张宁，单世民，江贺，张宪超大连理工大学软件学院，辽宁大连（116621）E-mail：izhangning@摘要：现有的基于网格聚类算法在付出较小的时间复杂度的同时，牺牲了聚类的质量，得到的往往并不是最理想的聚类结果，尤其是在簇边缘可能出现数据点聚类不准现象。
本文提出了一种将网格化空间中位于簇边缘的网格进行精度进一步细化处理的算法，将这些边缘网格中的这些不确定的点重新恢复他们的固有信息，再利用相似度函数将他们分配到合适的簇O n时间内得到优中。
在空间数据集上实验数据表明，这种簇边缘精度增强聚类算法可在()于CLIQUE算法的聚类结果。
关键词：数据聚类，基于网格，基于密度，混合算法文献标识码：A 中图分类号：TP181 引言聚类（clustering）是将数据集划分为若干个类，使得相同类中的数据具有较高相似度，而不同类中的数据具有较高相异度的过程[9]，广泛应用于地理、医学、化学、商业等领域中[14]。
现有的经典聚类算法可分为[13]：基于划分的方法，如k-means[1]；基于层次的方法，如CHAMELEON[8]、CURE[6]、BIRCH[2]；基于密度的方法，如DBCSCAN[3]、DENCLUE[7]和基于网格的方法，如STING[4]、CLIQUE[5]等。
基于网格和密度的方法由于其对数据输入顺序不敏感，适于增量处理数据，能发现任意形状聚类等特点引起了众多研究人员的注意。
基于密度的聚类方法认为，簇（cluster）是那些被低密度区域隔离开来的高密度区域[3]。
这种方法可以很好地处理形状不规则的聚类，并可以排除噪声的干扰，得到较高质量的聚类结果。
但是，由于这种方法需要计算每个点与其他点的距离，因此时间代价较高，达到了2O n，不适于处理大规模数据集。
DBSCAN虽然使用R*树来降低时间复杂度到()O n n，但是建立R*树结构本身也耗费资源。
基于网格的方法将数据空间划分为若干(log)互不相交的网格单元（cell），以网格单元为单位进行聚类过程而不是单个数据点。
基于多维网格空间的改进K-means聚类算法邵伦;周新志;赵成萍;张旭【期刊名称】《计算机应用》【年(卷),期】2018(038)010【摘要】K-means算法是被广泛使用的一种聚类算法,传统的K-means算法中初始聚类中心的选择具有随机性,易使算法陷入局部最优,聚类结果不稳定.针对此问题,引入多维网格空间的思想,首先将样本集映射到一个虚拟的多维网格空间结构中,然后从中搜索出包含样本数最多且距离较远的子网格作为初始聚类中心网格,最后计算出各初始聚类中心网格中所包含样本的均值点来作为初始聚类中心.此法选择出来的初始聚类中心与实际聚类中心拟合度高,进而可据此初始聚类中心稳定高效地得到最终的聚类结果.通过使用计算机模拟数据集和UCI机器学习数据集进行测试,结果表明改进算法的迭代次数和错误率比较稳定,且均小于传统K-means算法测试结果的平均值,能有效避免陷入局部最优,并且聚类结果稳定.【总页数】6页(P2850-2855)【作者】邵伦;周新志;赵成萍;张旭【作者单位】四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065【正文语种】中文【中图分类】TP301.6【相关文献】1.基于网格的二次K-means聚类算法 [J], 欧阳浩;陈波;王萌;黄镇谨2.一种基于网格的K-Means聚类算法 [J], 张西芝;朱小艳;刘敏娟3.多维数据K-means谱聚类算法改进研究 [J], 谢志明;王鹏;黄焱4.基于网格和密度的k-means聚类算法 [J], 李永定5.基于K-means的多维聚类算法在客户信息中的应用 [J], 周继成;蔡冠宇;高尚因版权原因，仅展示原文概要，查看原文内容请购买。
第４２卷 第６Ａ期２０１５年６月计算机科学Ｃｏｍｐｕｔｅｒ ＳｃｉｅｎｃｅＶｏｌ．４２Ｎｏ．６ＡＪｕｎｅ ２０１５伍育红（１９８１－），硕士生，讲师，主要研究方向为数据挖掘、网络控制与信息安全、电子商务与现代物流。
聚类算法综述伍育红（重庆邮电大学移通学院 重庆４０１５３９） 摘 要 数据挖掘技术可以从大量数据中发现潜在的、有价值的知识，它给人们在信息时代所积累的海量数据赋予了新的意义。
随着数据挖掘技术的迅速发展，作为其重要的组成部分，网格聚类技术已经被广泛应用于数据分析、图像处理、市场研究等许多领域。
网格聚类算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。
介绍了数据挖掘理论，对网格聚类算法进行了深入的分析研究。
在研究了传统网格聚类算法的基础上，提出了一些改进的网格聚类算法，这些算法相比传统网格聚类算法有更好的聚类质量和效率。
在分析了传统的多密度聚类算法的基础上，提出了基于网格的多密度聚类算法（Ｇｒｉｄ－ｂａｓｅｄ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｍｕｌｔｉ－ｄｅｎｓｉｔｙ）［１］，该算法主要采用密度阈值递减的多阶段聚类技术提取不同密度的聚类，同时对聚类结果进行了人工干预。
研究结果表明，基于网格的多密度聚类算法不仅能够对数据集进行正确的聚类，同时还能有效地弥补孤立点检测，有效地解决了传统多密度聚类算法不能有效识别孤立点和噪声的缺陷。
基于网格的多密度聚类算法比传统的共享近邻ＳＮＮ算法精度高，适合于均匀密度数据集、大部分多密度数据集，并且可以发现任意形状的聚类，对噪声数据和数据输入顺序不敏感，但对小部分多密度数据集的聚类结果不理想［１］。
关键词 网格聚类，密度阈值递减，多阶段聚类中图法分类号 ＴＰ３０１ 文献标识码 Ａ Ｇｅｎｅｒａｌ Ｏｖｅｒｖｉｅｗ ｏｎ Ｃｌｕｓｔｅｒｉｎｇ ＡｌｇｏｒｉｔｈｍｓＷＵ Ｙｕ－ｈｏｎｇ（Ｃｏｌｌｅｇｅ ｏｆ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ ４０１５３９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｄａｔａ ｍｉｎｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｃａｎ ｂｅ ｕｓｅｄ ｔｏ ｆｉｎｄ ｏｕｔ ｐｏｔｅｎｔｉａｌ ａｎｄ ｕｓｅｆｕｌ ｋｎｏｗｌｅｄｇｅ ｆｒｏｍ ｔｈｅ ｖａｓｔ ａｍｏｕｎｔ ｏｆ ｄａｔａ，ａｎｄ ｉｔ ｐｌａｙｓ ａ ｎｅｗ ｓｉｇｎｉｆｉｃａｎｔ ｒｏｌｅ ｔｏ ｔｈｅ ｓｔｏｒｅｄ ｄａｔａ ｉｎ ｔｈｅ ｉｎｆｏ－ｔｉｍｅｓ．Ｗｉｔｈ ｔｈｅ ｒａｐｉｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｔｈｅ ｄａｔａ ｍｉｎｉｎｇｔｅｃｈｎｉｑｕｅｓ，ｔｈｅ ｔｅｃｈｎｉｑｕｅ ｏｆ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ，ａｓ ｉｍｐｏｒｔａｎｔ ｐａｒｔｓ ｏｆ ｄａｔａ ｍｉｎｉｎｇ，ａｒｅ ｗｉｄｅｌｙ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｆｉｅｌｄｓ ｓｕｃｈ ａｓｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ，ｄａｔａ ａｎａｌｙｓｉｓ，ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ，ａｎｄ ｍａｒｋｅｔ ｒｅｓｅａｒｃｈ．Ｒｅｓｅａｒｃｈ ｏｎ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｈａｓ ｂｅ－ｃｏｍｅ ａ ｈｉｇｈｌｙ ａｃｔｉｖｅ ｔｏｐｉｃ ｉｎ ｔｈｅ ｄａｔａ ｍｉｎｉｎｇ ｒｅｓｅａｒｃｈ．Ｉｎ ｔｈｉｓ ｔｈｅｓｉｓ，ｔｈｅ ａｕｔｈｏｒ ｐｒｅｓｅｎｔｅｄ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ｄａｔａ ｍｉｎｉｎｇ，ａｎｄｄｅｅｐｌｙ ａｎａｌｙｚｅｓ ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｏｆ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ．Ｂａｓｅｄ ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｒａｄｉｔｉｏｎａｌ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ，ｗｅ ａｄ－ｖａｎｃｅｄ ｓｏｍｅ ｉｍｐｒｏｖｅｄ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｈａｔ ｃａｎ ｅｎｈａｎｃｅ ｔｈｅ ｑｕａｌｉｔｙ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ ｃｏｍｐａｒｅｄｗｉｔｈ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ．Ｂａｓｅｄ ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍｕｌｔｉ－ｄｅｎｓｉｔｙ，ｗｅ ａｄ－ｖａｎｃｅｄ ａ ｇｒｉｄ－ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉ－ｄｅｎｓｉｔｙ（ＧＤＤ）．Ｔｈｅ ＧＤＤ ｉｓ ａ ｋｉｎｄ ｏｆ ｔｈｅ ｍｕｌｔｉ－ｓｔａｇｅ ｃｌｕｓｔｅｒｉｎｇ ｔｈａｔｉｎｔｅｇｒａｔｅｓ ｇｒｉｄ－ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ，ｔｈｅ ｔｅｃｈｎｉｑｕｅ ｏｆ ｄｅｎｓｉｔｙ ｔｈｒｅｓｈｏｌｄ ｄｅｓｃｅｎｄｉｎｇ ａｎｄ ｂｏｒｄｅｒ ｐｏｉｎｔｓ ｅｘｔｒａｃｔｉｏｎ．Ａｓ ｓｈｏｗｎ ｉｎｔｈｅ ｒｅｓｅａｒｃｈ，ＧＤＤ ａｌｇｏｒｉｔｈｍ ｃａｎ ｎｏｔ ｏｎｌｙ ｃｌｕｓｔｅｒｓ ｃｏｒｒｅｃｔｌｙ ｂｕｔ ｆｉｎｄ ｏｕｔｌｉｅｒｓ ｉｎ ｔｈｅ ｄａｔａｓｅｔ，ａｎｄ ｉｔ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅｓ ｔｈｅｐｒｏｂｌｅｍ ｔｈａｔ ｔｒａｄｉｔｉｏｎａｌ ｇｒｉｄ ａｌｇｏｒｉｔｈｍｓ ｃａｎ ｃｌｕｓｔｅｒ ｏｎｌｙ ｏｒ ｆｉｎｄ ｏｕｔｌｉｅｒｓ ｏｎｌｙ．Ｔｈｅ ｐｒｅｃｉｓｉｏｎ ｏｆ ＧＤＤ ａｌｇｏｒｉｔｈｍ ｉｓ ｂｅｔｔｅｒｔｈａｎ ｔｈａｔ ｏｆ ＳＮＮ．Ｔｈｅ ＧＤＤ ａｌｇｏｒｉｔｈｍ ｗｏｒｋｓ ｗｅｌｌ ｆｏｒ ｅｖｅｎ ｄｅｎｓｉｔｙ ｄａｔａｓｅｔ ａｎｄ ｌｏｔｓ ｏｆ ｍｕｌｔｉ－ｄｅｎｓｉｔｙ ｄａｔａｓｅｔｓ；ｉｔ ｃａｎ ｄｉｓ－ｃｏｖｅｒ ｃｌｕｓｔｅｒｓ ｏｆ ａｒｂｉｔｒａｒｙ ｓｈａｐｅｓ；ｉｔ ｉｓｎ’ｔ ｓｅｎｓｉｔｉｖｅ ｔｏ ｔｈｅ ｉｎｐｕｔ ｏｒｄｅｒ ｏｆ ｎｏｉｓｅｓ ａｎｄ ｏｕｔｌｉｅｒｓ ｄａｔａ，ｂｕｔ ｉｔ ｉｓ ｉｍｐｅｒｆｅｃｔ ｔｏｃｌｕｓｔｅｒ ｏｎ ｓｏｍｅ ｍｕｌｔｉ－ｄｅｎｓｉｔｙ ｄａｔａｓｅｔｓ．Ｋｅｙｗｏｒｄｓ Ｇｒｉｄ ｃｌｕｓｔｅｒｉｎｇ，Ｄｅｎｓｉｔｙ ｔｈｒｅｓｈｏｌｄ ｄｅｓｃｅｎｄｉｎｇ，Ｍｕｌｔｉ－ｓｔａｇｅ ｃｌｕｓｔｅｒｉｎｇ １ 引言聚类已经被广泛地研究了许多年，迄今为止，研究人员已经提出了很多聚类算法，大体上这些算法可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法。
高维聚类算法
高维聚类算法是处理高维数据的聚类分析技术，其目标是在高维空间中将相似的数据点划分为同一簇，而将不相似的数据点划分到不同的簇中。
由于高维数据的复杂性，传统的聚类算法在高维空间中可能表现不佳，因此需要专门设计的高维聚类算法。
高维聚类算法主要包括以下几种类型：
1. 基于降维的聚类方法：这种方法首先通过降维技术（如主成分分析、多维缩放等）将高维数据转换为低维数据，然后在低维空间中使用传统的聚类算法进行聚类。
然而，这种方法可能会丢失原始数据中的某些重要信息，且对噪声数据敏感。
2. 子空间聚类算法：这类算法将数据的原始特征空间分割为不同的特征子集，从不同的子空间角度考察各个数据簇聚类划分的意义，同时在聚类过程中为每个数据簇寻找到相应的特征子空间。
典型的子空间聚类算法有CLIQUE、ENCLUS和MAFIA等。
它们使用Apriori策略来查找和合并满足特定条件的网格，产生候选子空间，并根据子空间的覆盖度进行排序和剪枝。
3. 基于谱聚类的算法：谱聚类是一种基于图论的聚类方法，通过构造数据的相似度矩阵，并利用矩阵的特征向量进行聚类。
在高维空间中，谱聚类能够发现非凸形状的簇，并对噪声和异常值具有一定的鲁棒性。
4. 基于密度的聚类算法：如DBSCAN（基于密度的带噪声的空间聚类应用与噪声）等，它们根据数据点的密度进行聚类，能够在高维空间中发现任意形状的簇，并对噪声和异常值具有较好的处理能力。
每种高维聚类算法都有其特点和适用场景，选择哪种算法取决于数据的性质、聚类的目的以及计算资源等因素。
在实际应用中，可能需要根据具体情况对算法进行调整和优化，以达到更好的聚类效果。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.19, No.6, June 2008, pp.1283−1300 DOI: 10.3724/SP.J.1001.2008.01283 Tel/Fax: +86-10-62562563© 2008 by Journal of Software. All rights reserved.∗基于多重分形的聚类层次优化算法闫光辉1,2+, 李战怀1, 党建武21(西北工业大学计算机学院,陕西西安 710072)2(兰州交通大学电子与信息工程学院,甘肃兰州 730070)Finding Natural Cluster Hierarchies Based on MultiFractalYAN Guang-Hui1,2+, LI Zhan-Huai1, DANG Jian-Wu21(School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China)2(School of Information and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)+ Corresponding author: E-mail: yangh@Yan GH, Li ZH, Dang JW. Finding natural cluster hierarchies based on MultiFractal. Journal of Software,2008,19(6):1283−1300. /1000-9825/19/1283.htmAbstract: A cluster is a collection of data objects that are similar to one another within the same cluster and aredissimilar to the objects in other clusters. Moreover, there will exist more or less similarities among these largeamounts of initial cluster results in real life data set. Accordingly, analyzer may have difficulty to implement furtheranalysis if they know nothing about these similarities. Therefore, it is very valuable to analyze these similarities andconstruct the hierarchy structures of the initial clusters. The traditional cluster methods are unfit for this clusterpost-processing problem for their favor of finding the convex cluster result, impractical hypothesis and multiplescans of the data set. Based on multifractal theory, this paper proposes the FCHO (fractal-based cluster hierarchyoptimization) algorithm, which integrates the cluster similarity with cluster shape and cluster distribution toconstruct the cluster hierarchy tree from the disjoint initial clusters. The elementary time-space complexity of theFCHO algorithm is presented. Several comparative experiments using synthetic and real life data set show theperformance and the effectivity of FCHO.Key words: data mining; clustering; multifractal; post-processing; optimization摘要: 大量初始聚类结果之间存在强弱不同的相似性,会给用户理解与描述聚类结果带来不利影响,进而阻碍数据挖掘后续工作的顺利展开.传统聚类算法由于注重聚类形状及空间邻接性,或者考虑全局数据分布密度的均匀性,实际中均难以解决这一类问题.为此,提出了基于分形的聚类层次优化算法FCHO(fractal-based clusterhierarchy optimization),FCHO算法基于多重分形理论,利用聚类对应多重分形维数及聚类合并之后多重分形维数的变化程度来度量初始聚类之间的相似程度,最终生成反映数据自然聚集状态的聚类家族树.此外,初步分析了算法的时空复杂性,基于合成数据集和标准数据集的有关实验工作证实了算法的有效性.∗Supported by the National Natural Science Foundation of China under Grant No.60573096 (国家自然科学基金); the NSFC-JSTMajor International (Regional) Joint Research Project under Grant No.60720106001 (NSFC-JST重大国际(地区)合作项目); theFoundation of Gansu Province Educational Department of China under Grant No.0604-09 (甘肃省教育厅基金)Received 2007-03-01; Accepted 2007-10-091284 Journal of Software软件学报 V ol.19, No.6, June 2008关键词: 数据挖掘;聚类;多重分形;后续处理;优化中图法分类号: TP181文献标识码: A聚类是将物理或抽象对象的集合分组成为由相似对象组成的多个集合的过程,其中属于同一个集合的对象之间的彼此相似,属于不同集合的对象之间彼此相异(按照某种度量机制).通过聚类操作,我们能够识别数据集的密集和稀疏区域,发现数据的全局分布模式,以及数据间有趣的相互关系.聚类作为数据预处理的重要手段和数据挖掘的基础性支持工具,在统计学和知识发现等领域得到了广泛而深入的研究,国内外研究者针对不同的应用、数据类型与聚类目的,进行了大量卓有成效的研究工作,取得了丰富的研究结果[1−3].统计聚类方法[4−6]基于欧氏距离度量机制,在低维数据分析中获得了优良的性能和令人满意的聚类结果,但也存在无法发现非球形聚类或者大小差别很大的聚类的缺陷,因而可能降低无监督学习的精度和效率,并给用户进一步的数据分析工作带来了困难甚至误导用户的判断[7−15].基于层次、密度和网格的聚类技术在大数据集、增量及任意形状聚类方面与统计聚类技术相比具有较大的优越性,然而却无法应对聚类内部密度不均匀及聚类非邻接的情况(表现为在数据空间中离散分布的一些数据聚集,宏观上某些非邻接的数据聚集最终都属于同一个聚类,一些常见的分形数据集,如康托尘(Cantor set)).如图1所示,以均匀分布生成位于二维数据空间不同位置的10个矩形,以及利用正态分布生成的、分别位于二维空间的4个象限内的、由同一圆环分割而成的4个四分之一圆环(为对比实验方便,命名该数据集为D2-20K),通过聚类操作我们容易得到如图1所示的9个聚类(其中红色圆圈对应稀疏数据点),分别对应中心交叉矩形框、4个圆环聚类和位于四角的4个相交矩形框.然而,根据数据集的生成方式我们得知矩形数据集之间具有较强的相似性,同时,圆环数据集之间也具有较强的相似性.遗憾的是,当前的聚类技术忽视这种相似性,因而也就无法对初始聚类结果进一步优化,错失了发现更隐藏、更有趣模式的机会.基于模型的聚类方法[16,17]根据数据由潜在的概率分布生成的假设,试图优化给定的数据集和潜在概率模型之间的适应性,从而进行相应的聚类工作.基于模型的方法一方面需要对数据集施以较强的限定,而这种限定在实际应用中很难满足(如属性相互独立);另一方面,还存在训练时间过长及无法适应于大数据集的情况,同时也无法满足数据流等增量聚类的要求,因而难以在实际中应用.yxFig.1 Initial cluster results图1 初始聚类结果聚类定义的本质依赖于模式之间的相似性,属于同一个聚类的模式之间相似性最大,属于不同聚类的模式之间相似性最小,同样在聚类合并过程中也应该遵循这一原则,即进行合并的初始聚类之间也必然存在某种相似性,但这种相似性仅仅依靠聚类之间的距离无法准确度量.就我们所知,对于图1所示的数据集,当前的聚类算法得到的聚类结果都无法反映数据集的自然聚集状况.通过分析,容易发现该问题与传统聚类问题的特征及要求不完全一致,即对聚类合并的要求不仅限于空间邻接或距离上比较接近,而且更加突出聚类之间的整体相似性,这种相似性可以表现为空间形状的相似性、空间距离的接近性、聚类整体分布的相似性及以上因素的综合等,因而造成传统聚类技术由于仅考虑某一特性而无法成功地解决这一类问题.闫光辉 等:基于多重分形的聚类层次优化算法1285我们将这种问题称为非邻接聚类问题,或将其推广为聚类后续处理问题.该问题主要关注于每个初始聚类作为一个整体而言的结构与行为特征,要求能够跨越空间和局部的联系,这与经典聚类算法主要关注空间联系和局部特性有着完全不同的侧重点.为了发现数据集中隐藏的,更有趣的及自然的模式,我们提出利用多重分形技术进行初始聚类结果的后续处理.第1节介绍了相关的基本工作,并分析了当前聚类算法在面对聚类后续处理问题的不足之处;第2节详细论述了FCHO 算法的基本思想、实现过程;第3节基于合成数据集和实际数据集对FCHO 算法进行了验证性测试工作,给出了相关的运行结果及聚类合并家族树,对算法的时空复杂性进行了初步分析;最后对研究工作做了阶段性总结,同时展望了研究工作的方向.1 相关工作1.1 分形及分形维数20世纪70年代诞生的分形理论在空间数据查询效率分析[18,19]、多维索引技术[20]等研究领域得到了广泛的应用.下面给出一些相关的基本概念.定义1(分形). 一个数据集基于不同的观察尺度表现出部分和整体的相似性(可以表现为空间形状自相似性,也可以表现为统计分布上的自相似性),称该数据集为一个分形,许多实际的数据集呈现统计分形的特征.本文主要从数据集的统计分形角度来进行相关的聚类研究工作.定义2(嵌入维数). 嵌入维数是数据集位于的数据空间的维数,也就是数据集对应的属性数目. 定义3(内在维数). 内在维数是数据集合的真正表现维数.内在维数不随数据集嵌入维数的不同而改变,在一定程度上定量地描述了数据集内部结构的复杂性.例如:一条直线若位于二维平面内,其嵌入维数为2,若位于三维空间之中,则嵌入维数为3,但无论位于多少维空间中,其内在维数都大致为 1.此外,内在维数还可以在一定程度上反映属性之间的非线性相关性,如二维空间中的圆形对应的内在维数大致为1.在实际应用中,鉴于内在维数的计算复杂性,经常采用分形维数来近似内在维数[19],图2给出了不同数据集位于不同的嵌入空间所对应的分形维数(第1行对应数据集分布情况,中间行对应关联分形维数,第3行对应相应的多重分形维数q −D q 曲线).考虑到实际数据分布的多样性和复杂性,仅以某单一分形维数(如盒维数,信息维数及关联维数)为特征,难以区分单一分形集(single fractal)和多重分形集(multiple fractal),同时也存在不同分布的数据集却具有比较接近的单一分形维数的特殊情况.如图2所示,二维空间圆形与三维空间直线对应的关联分形维数比较接近,因此,单独利用关联分形维数也就无法区分这两个数据集.为了能够更精确地描述一个分形集,同时也为了能够更加有效地支持聚类后续处理工作,需要增加能刻画数据集更精细特征的不同的分形参数,由此引入了多重分形维数和多重分形理论,有关多重分形维数的详细内容见文献[21].定义4(多重分形维数). 对于一个在区间],[21r r (无标度区)内呈现统计自相似特征的数据集,其多重分形维数D q 定义如下:120Log lim, 1log ,[,]1Log lim ,11Log qi i i r q qi ir p p q r D r r r p q q r →→⎧∑=⎪⎪=∈⎨∑⎪≠⎪−⎩(1)其中,r 是覆盖数据空间所用的网格的边长,i P 为网格的奇异性测度,即网格所包含的数据点数目与全部数据点数目之比.已经证明,00lim D D q q =→即是豪斯道夫维数(盒维数),11lim D D q q =→为信息维数,22lim D D q q =→为关联维数,这3种维数同时也是在实际中经常用到的几种分形维数.根据式(1),理论上可以给出无限多的D q 定义,从而得到广义分形维数谱.其中,q >0的高阶维数D q 反映了分形集中点的聚集程度,即由q 个点构成的集团分布情况,相应地,q <0的高阶维数D q 则反映了分形集空隙分布情况.由此可见,引入广义分形维数可以更精确地反映数据集的1286 Journal of Software软件学报 V ol.19, No.6, June 2008分布情况,从而为数据集描述提供了更加有力的工具.另外,广义分形维数的引入也为我们对数据集进行分类带来了更有力的工具.例如:当两个数据集的单一分形维数如D0接近甚至相同时,单独依靠D0就无法区分这两个数据集合,而如果它们对应的信息维数D1或关联维数D2取值不同,则我们就可以根据D1或D2对它们进行分类.基于这种思路,可选的q次分形维数越多,则其相应的区分不同数据集的能力也就越强.考虑到实际应用的需求及计算资源的限制,一般情况下,利用D10及D−10作为可选的分形维数.从图2第3行容易看出具有相近D2值的圆形和直线数据集对应的D−10和D10差别明显,可以作为区分这两个数据集的特征使用.Fig.2 Data sets and the q−D q plots图2 数据集及其对应q−D q曲线针对实际数据集中可能包含各种形式的分布情况、聚类密度不均匀以及多重分形维数的特点,我们考虑采用D−10,D2和D10作为度量聚类相似程度的主要依据,其中, D−10,D2和D10在聚类合并过程中各有侧重点:在判断聚类能否合并的情况下,D−10,D2和D10具有同样的权重(主要目的在于从聚类的离散度,密集度及形状等多方面来综合考虑),而聚类合并之后(假定聚类之间不存在相互包含的情况,则合并后聚类的离散度会大于合并之前聚类的离散度)D−10会发生比较大的变化,相应地,我们着重利用D2和D10来判断合并操作是否合法.由此,基于多重分形的聚类后续处理技术同时考虑聚类内部数据分布特点及聚类整体形态特征,可以发现潜在的﹑更能反映数据集本质特性的模式.1.2 层次、网格、密度及分形聚类技术层次聚类是一种有效的聚类技术,它通过将数据对象组成为一棵聚类的树,为用户提供多种可选的聚类结果,可以根据需要随时结束聚类操作过程,因而是目前广泛应用的一种聚类技术.层次聚类的具体实现过程分为两种形式:自底向上凝聚(agglomerative)与自顶向下分裂(divisive),凝聚与分裂操作都要基于某种特定的相似性度量机制.单连接方式与全连接方式是两种常见的度量聚类之间相似性的技术.单连接是计算分别位于两个聚类中的模式之间的最大相似度;全连接方式则相反,计算分别位于两个聚类中的模式之间的最小相似度,随后的闫光辉等:基于多重分形的聚类层次优化算法1287聚类凝聚与分裂操作也主要基于所得到的相似度来进行.BIRCH[7](balanced iterative reducing and clustering using hierarchies)算法引入聚类特征与聚类特征树进行概括聚类描述,首先扫描数据集并建立一个基于内存的聚类特征树,然后采用某个聚类算法对聚类特征树的叶子结点进行聚类操作.BIRCH算法的主要问题在于其利用半径或直径来控制聚类的边界,因而无法适应于非球形聚类的情况.CURE[8](clustering using representatives)通过选择数据空间中固定数目的具有代表性的点来描述聚类,ROCK[9](robust clustering using linKs)算法实际上是CURE算法针对分类属性的扩充版本.Chameleon[10]算法首先构造数据集的k-最近邻居图,然后基于图的划分技术将数据对象聚集为大量相对较小的子聚类,最后利用一个凝聚的层次聚类算法反复地合并子聚类来寻找真正的结果聚类.层次聚类算法一般需要用户输入参数,如聚类个数等来结束算法的执行.网格聚类技术首先将对象空间划分为互不相交单元(网格)以构成网格结构,然后利用网格结构完成聚类操作,具有一遍扫描数据集及运行时间与数据点数无关的特点,在高维、海量数据聚类领域获得了较为广泛的应用,目前在数据流聚类领域也出现了利用网格技术进进行聚类的尝试.网格聚类技术的不足之处在于,网格的数目随着数据集合维度的增加而呈指数增长,针对这一缺陷,基于网格的聚类算法要么仅保留超过某一密度阈值的网格,要么采用Apriori原理进行网格的预先删除,而进行网格的预先删除需要各维之间的连接工作,无法适应动态数据流环境.STING[13]是首个基于网格的聚类技术,它利用一个互不相交的且层次嵌套的网格结构覆盖数据空间,通过一遍扫描数据集,利用底层网格所包含的统计信息逐层递推得到上层网格的统计信息,从而支持不同粒度的多次查询请求,同时,基于底层网格的统计信息也可以进行相关的聚类工作.Wave-Cluster[14]和CLIQUE[15](clustering in QUEst)则是将基于网格与基于密度相结合的方法.典型的基于密度方法包括:DBSCAN[11](density-based spatial clustering of applications with noise)、OPTICS[12](ordering points to identify the clustering structure)等.该方法将聚类定义为一组“密度连接”的点集,通过不断生长足够高密度区域从含有噪声的数据集中发现任意形状的聚类.DBSCAN是第一种利用密度的聚类算法,它需要用户设置两个参数Eps(密集区域半径)和MinPts(最少密集近邻数目)用于控制正常聚类的密度.但由于实际高维数据经常分布不均匀,因而造成全局密度参数无法精确刻画其内在的聚类结构.OPTICS算法针对DBSCAN算法的缺陷,提供一个逐步增加的密度区域顺序来代替聚类操作,并能从中发现用户所需要的聚类信息,但OPTICS算法本质上也是基于欧氏距离的,同样无法满足聚类后续处理的需求.国内研究人员针对当前聚类算法的不足也做了一定的研究工作[22].提出将密度与距离度量机制相结合的聚类算法,提高了聚类的质量及发现任意形状互连聚类能力[23].提出结合参考点和密度的聚类算法,从而进一步地增强算法发现任意形状聚类能力.文献[24]提出一种基于主次属性划分的聚类方法及数据可视化方法.文献[25]提出二分网格划分机制结合动态网格密度来发现任意形状、非均匀密度分布的聚类.从本质上分析,层次聚类技术﹑网格及密度聚类技术所采用的相似性度量机制仍然是基于欧氏距离和邻接特征的,因而也就无法跳出只能发现空间上邻接的聚类的局限,无法解决非邻接聚类问题.分形理论通过分析部分与整体的相似性来描述数据的分布特征,是研究数据之间的相似性以及数据集部分与整体相似性的有力工具.多重分形既关注数据集的整体分布与行为特征,同时又引入多重分形维数来描述数据集局部的结构与行为特征,可以提供更精细的相似性度量机制.因此,利用多重分形理论同时考虑部分与整体相似性的固有特点,引入多重分形技术进行相关的聚类工作尤其是聚类后续处理工作在理论与技术上是可行的.Barbará首次提出基于分形的FC(fractal clustering)聚类算法[26],分析了FC算法的时空复杂度.针对合成与实际数据集的实验结果显示FC算法对属性数目及数据集规模具有较好的可扩展性,在算法的执行时间、存储需求及聚类结果的优劣方面对FC算法、BIRCH及CURE等聚类技术进行了实验对比分析,结果表明,FC算法具有相对优良的聚类结果,此时,上述三者面对大数据集的执行时间与存储空间需求基本相当.FC算法具有发现任意形状聚类及增量聚类的特点,但算法仍然利用聚类之间的最近距离作为聚类合并的唯一依据,因而同样无法解决非邻接聚类问题.此外,FC算法也无法得到聚类合并的层次结构.基于多重分形技术,我们提出了聚类层次优化算法FCHO(fractal-based cluster hierarchy optimization),FCHO算法利用整型Z-Ordering技术[27]通过一遍扫描数据集来创建初始的底层网格结构,基于该底层网格结构利用密度和网格的聚类技术来生成初始聚类,1288 Journal of Software 软件学报 V ol.19, No.6, June 2008结合多重分形技术优化初始聚类结果,针对优化的初始聚类结果自底向上构建聚类家族树,从而在更高程度上支持用户的数据分析工作,进而发现数据中更为隐蔽的模式.2 基于分形的聚类层次优化算法2.1 数据结构及概念设12{,,...,}d A A A A =是有界域的集合,12...d S A A A =×××是一个d 维数据空间,其中12,,...,d A A A 表示S 的d 个维或d 个属性域.12{,,...,}N X x x x =表示S 上的N 个点的集合,其中,12,,...,d i i i i x x x x =表示一个数据点,j i A x j ∈ 表示数据点i x 的第j 维的值,也就是数据点i x 的第j 维坐标.为便于计算数据集的分形维数,类似于STING 算法构建多层网格结构,以二维数据空间为例,所构建的多层网格结构如图3所示.数据空间格式化为边长为1的单位网格,则嵌套的下层网格的边长按照如下方式划分:0112,12,...,12level ,其中level 为网格结构的层数.顶层网格对应数据空间整体,包含4(22,d 维空间为d 2)个第二层网格(边长为1/2),其中,上层的每一个网格均包含其直接下层的4个网格(边长为上层网格边长减半).Fig.3 2D embedded grid structure and Z-ordering code图3 二维嵌套网格及Z-ordering 编码为了满足对网格进行存储以及分形维数的计算需要,[27]引入整型Z-ordering 编码技术对最低层网格编址,该技术可以实现从底层网格所包含统计信息到最上层网格所包含统计信息的映射工作,图3以二维空间为例给出底层网格坐标逐层映射为其直接高层网格坐标的过程,其中,网格坐标的修改操作按照式(2)进行.1111,MOD 20212, MOD 212s d s i i s d s i C C C C C C −−−⎧−⎛⎞==⎜⎟⎪⎪⎝⎠⎨−⎛⎞⎪=−=⎜⎟⎪⎝⎠⎩(2) 其中,C s 为修改之前的维坐标值;C d 为修改之后的对应维坐标值;i 为当前合并的层次数.i =1对应由最低层向次低层合并, i =2对应由次低层向其直接上层合并,依此类推.定义 5(网格选择度). 网格Grid i 的选择度为XGrid count Grid y selectivit i i )()(=, 其中,count (Grid i )为网格Grid i 所包含的数据点数,|X |为数据集总的数据点数.根据多层嵌套网格结构定义形式及网格坐标映射机制,只要保存底层网格结构及其相应的数据点数目信息,容易得到任意层、任意网格的选闫光辉 等:基于多重分形的聚类层次优化算法 1289择度.定义 6(密集网格). 对于i Grid ,若τ×>X Grid y selectivit i )(,其中,τ为网格密集度阈值,则i Grid 为密集 网格.定义 7(初始聚类). 数据空间中邻接的密集网格的最大集合即为初始聚类.两个网格i Grid 和j Grid 邻接的条件之一是它们之间共享一个公共超平面,或者存在另一个网格k Grid ,使得i Grid 与k Grid 邻接,同时k Grid 与j Grid 邻接.规定网格对应的选择度后,给定网格密集度阈值τ,容易得到密集网格信息,相应地我们可以通过判断邻接的密集网格来进行初始的聚类操作,从而得到初始的聚类结果,图1为合成数据集对应的初始聚类情况.分析基于密度和网格的聚类算法过程易知,选择不同的网格密度阈值并不会从根本上改变聚类的形状,虽然我们可以通过改变网格的边长来得到不同的聚类结果,但无论我们怎样改变网格的边长,也无法将所有矩形框生成为一个聚类,同时将4个四分之一圆环形成为一个聚类.因此,我们考虑在已经得到了一定数目的、能基本反映数据集分布情况的初始聚类结果的基础上,如何对初始聚类结果进一步优化,以求能更精确地反映数据的自然聚集情况.基于前面的分析,我们设计了FCHO 算法对所得到的聚类结果进行后续处理, 从而发现数据中更为隐蔽的模式.为便于对算法进行描述,表1列出了算法所使用的主要符号.Table 1 Symbols 表1 算法使用符号No. Symbol Signification 1S Data space 2 A Bounded interval 3X Data set 4Current _cluster Cluster number 5Cluster i Cluster i6qi D q th fractal dimension of Cluster i 7Cluster ij Merge of Cluster i and Cluster j 8qij D q th fractal dimension of Cluster ij9G i Cluster set for merging10 εq Threshold value of q th fractal dimension for grouping 11δq Threshold value of q th fractal dimension for merging2.2 FCHO 算法描述分形维数是反映数据分布复杂程度的一个重要特征参数,随着数据集结构形态的不同而变化,在一定程度上定量地描述了数据集内部结构的复杂性,并且同一数据集的分形维数不会因嵌入空间维数及嵌入位置不同 而发生显著变化.表2列出了图1中的聚类所对应的分形维数)10,2,10(−=q D q i ,图4为合成数据集初始聚类 结果对应的q −D q 曲线,容易看出,位于四角的交叉矩形框和中心交叉矩形框所对应的分形维数基本接近,而位于4个象限内的4个四分之一圆环所对应的分形维数基本接近.考虑到多重分形维数的性质,位于同一数据空间的聚类如果具有比较接近的多重分形维数,并且合并之后聚类所对应的分形维数与原聚类对应的分形维数相比变化较小,则根据分形维数的性质可知合并后的聚类内部结构特征与合并前的聚类内部结构特征相似,相应地,这两个聚类从相似性角度而言应该合并.。
网格聚类算法研究【摘要】聚类分析是数据挖掘中非常重要的方法，并且在很多领域发挥了巨大的作用。
本文以研究网格聚类算法为目的，介绍了常见的基于网格的聚类算法，并比较分析了各类算法的基本思想和优缺点。
【关键词】网格聚类算法;STING算法;WaveCluster算法;CLIQUE算法0.引言聚类就是将多个数据对象分成不同的类或者簇，每个类中的对象之间具有较高的相似度，而不同类的对象相似度低。
聚类算法是数据挖掘中的重要算法，可以应用于机器学习、统计学、模式识别、图像处理、考古学、市场营销和生物学等多个领域。
聚类是数据挖掘的主要任务之一，目前常见的文献中主要有以下几类聚类算法：划分方法、层次方法、基于密度的算法、基于网格的算法及基于模型的算法等。
一些聚类算法集成了多种聚类方法的思想，所以有时不能将某个给定的算法划分为属于某一类特定的聚类方法。
各类算法各有自己的特点，应用于不同的领域并且发挥了很大的作用，实现了数据的有效聚类。
1.基于网格的聚类方法(grid-based method)基于网格的方法采用了网格的数据结构，首先将数据空间划分成为有限个单元（cell），这些单元就形成了网格结构，所有的处理都是以单个的单元为对象的。
这种方法的主要优点就是处理速度很快，处理时间与目标数据库中记录的个数无关的，但是又依赖于数据空间的单元数目。
代表算法有：STING[1]、WaveCluster、CLIQUE。
1.1 STING（Statistical Information Grid，统计信息网格）算法STING算法是一种基于网格的多分辨率聚类算法，其基本思想是：先将数据空间区域划分成矩形单元。
对于不同级别的分辨率，通常存在着不同级别的矩形单元，这些单元形成一个层次结构，高层的每一个单元被划分为多个低一层的单元。
每个网格单元属性的统计信息如均值等都被预先计算和存储起来，以方便下一步的查询操作。
高层单元的统计参数可以通过计算低层单元获得，这些参数包括：属性无关的参数count（计数）；属性相关的参数mean(平均值)，stdev(标准偏差)，min(最小值)，max(最大值)，以及该单元中属性值遵循的分布(distribution)类型，例如一致分布、正态分布等。
龙源期刊网
基于网格与分形维数的聚类算法
作者：梁敏君倪志伟倪丽萍杨葛钟啸
来源：《计算机应用》2009年第03期
摘要：提出了一种基于网格和分形维数的聚类算法，它结合了网格聚类和分形聚类的优点，克服了传统网格聚类算法聚类质量降低的缺点，改进了分形聚类耗时较大的问题。
此算法首先根据网格密度得到初始类别，再利用分形的思想，将未被划分的网格依次归类。
实验结果证明，它能够发现任意形状且距离非邻近的聚类，且适用于海量、高维数据。
关键词：聚类；分形维数；网格。
