基于层次划分的密度优化聚类算法

针对传统的聚类算法对数据集反复聚类,且在大型数据集上计算效率欠佳的问题,提出一种基于层次划分的最佳聚类数和初始聚类中心确定算法——基于层次划分密度的聚类优化(CODHD)。该算法基于层次划分,对计算过程进行研究,不需要对数据集进行反复聚类。首先,扫描数据集获得所有聚类特征的统计值;其次,自底向上地生成不同层次的数据划分,计算每个划分数据点的密度,将最大密度点定为中心点,计算中心点距离更高密度点的最小距离,以中心点密度与最小距离乘积之和的平均值为有效性指标,增量地构建一条关于不同层次划分的聚类质量曲线;最后,根据曲线的极值点对应的划分估计最佳聚类数和初始聚类中心。实验结果表明,所提CODHD算法与预处理阶段的聚类优化(COPS)算法相比,聚类准确度提高了30%,聚类算法效率至少提高14.24%。所提算法具有较强的可行性和实用性。     

基于约束动态更新的半监督层次聚类算法

提出了一种基于约束动态更新的半监督层次聚类算法. 与现存的半监督层次聚类算法类似, 该算法也使用了必连和不连约束. 但不同的是, 该算法并不是在对满足必连约束的数据样本点进行预先划分的基础上依据不连约束进行聚合操作, 而是首先将约束扩展为一个闭包, 然后在这此基础上直接依据不连约束进行聚合操作, 并在聚合的过程中依据聚类结果动态地更新必连和不连约束, 以保证最终的聚类结果同时满足必连和不连约束. 该算法的优势在于省略了对必连约束的数据样本点进行预先划分的步骤, 这一改进能够保证数据样本点获得更为合理的聚合顺序, 从而得到更为准确的聚类结果. 本文具体给出了该算法基于Ward 层次聚类算法的实现, 提出了C-Ward算法.实验表明, 与其他同类算法相比, 无论是在人工模拟数据集还是在现实数据集上, 本文提出的算法都表现出了更高的准确性和更强的稳定性.     

基于划分与层次方法的混合聚类算法

为了更好地实现聚类,在汲取传统的划分算法、层次算法特性的基础上,提出了一种新的基于划分和层次的混合聚类算法（MPH）,该算法将聚类的过程分为分裂和合并两个阶段,在分裂阶段反复采用k-means算法,将数据集划分为多个同质的子簇,在合并阶段采用凝聚的层次聚类算法。实验表明,该算法能够发现任意形状、任意大小的聚类,并且对噪声点不敏感。     

复杂分布数据的二阶段聚类算法

提出了一种用于复杂分布数据的二阶段聚类算法(two-phase clustering,简称TPC),TPC包含两个阶段:首先将数据划分为若干个球形分布的子类,每一个子类用其聚类中心代表该类内的所有样本;然后利用可以处理复杂分布数据的流形进化聚类(manifold evolutionary clustering,简称MEC)对第1阶段得到的聚类中心进行类别划分;最后综合两次聚类结果整理得到最终聚类结果.该算法基于改进的K-均值算法和MEC算法.在进化聚类算法的基础上引入流形距离,使得算法能够胜任复杂分布的数据聚类问题.同时,算法降低了引入流形距离所带来的计算量.在分布各异的7个人工数据集和7个UCI数据集测试了二阶段聚类算法,并将其效果与遗传聚类算法、K均值算法和流形进化聚类算法做了比较.实验结果表明,无论对于简单或复杂、凸或非凸的数据,TPC都表现出良好的聚类性能,并且计算时间与MEC相比明显减少.     

Chameleon算法的改进

结合Chameleon算法可以发现高质量的任意形状、大小和密度的自然簇及一趟聚类算法快速高效的特点,研究可以处理混合属性的高效聚类算法.首先简单改进Chameleon算法,使之可以处理含分类属性的数据;进而提出一种两阶段聚类算法.第一阶段使用一趟聚类算法对数据集进行初始划分,第二阶段利用改进的Chameleon算法归并初始划分而得到最终聚类.在真实数据集和人造数据集上的实验结果表明,提出的两阶段聚类算法是有效可行的.     

改进的蚂蚁聚类算法*

提出了一种改进的基于对称点距离的蚂蚁聚类算法。该算法不再采用Euclidean距离来计算类内对象的相似性,而是使用新的对称点距离来计算相似性,在处理带有对称性质的数据集时,可以有效地识别给定数据集的聚类数目和合适的划分。在该算法中,用人工蚂蚁代表数据对象,根据算法给定的聚类规则来寻找最合适的聚类划分。最后用本算法与标准的蚂蚁聚类算法分别对不同的数据集进行了聚类实验。实验结果证实了算法的有效性。     

一种处理混合型数据的层次聚类算法 *

针对字符型数据和混合型数据的聚类方法进行了研究。首先在经典粗糙集理论的基础上,通过松弛对 象之间的不可分辨和相容性条件,得到了基于和谐关系的扩展粗糙集模型;然后定义了新的个体间不可区分度、 类间不可区分度、聚类结果的综合近似精度等概念,提出了新的混合数据类型层次聚类算法。该算法不仅能处 理数值型数据,而且能处理大多数聚类算法不能处理的字符型数据和混合型数据。实验验证了算法的可行性。     

一种高维混合属性数据聚类算法

在许多应用中,很多数据集都具有数值型和分类型数据的混合特征,k-prototype是针对这类数据聚类的经典方法之一,该方法是一种基于k-means和k-mode的聚类方法。在研究了现有的混合属性数据聚类方法之后,引入了一种新算法用于混合型数据聚类,不仅改进了prototype的选取方法,而且提出了一种新的针对混合型数据的相似度度量方式,基于此又提出了一种不同于k-prototype的数据到prototype的分配方式,采用类似层次聚类中凝聚聚类的思想进行聚类,通过在四个真实的混合型数据集上测试发现：与传统算法相比,算法提高了聚类的精度和稳定性。     

一种基于划分的混合数据聚类算法

在实际应用领域,常常存在同时包含数值型和分类型特征的混合数据。然而,已有的大多数聚类算法只能处理数值型或分类型单一类型数据,因此,提出一个基于划分的混合数据聚类算法。首先给出K-Prototypes算法中分类型数据类中心的多Modes表示方式,进而将传统的欧式距离扩展到混合数据,使之能够在相同框架下更加精确地反映对象与类之间的相异性,在此基础上提出一个用于处理混合数据的划分式聚类算法。最后,在UCI数据集上的实验结果表明,与K-Prototypes算法相比,所提出的算法能够有效提高聚类质量。     

挑选聚类算法的网格连通图方法

每一种聚类算法都有其适合处理的特定分布的数据集.为了给未知分布数据集挑选合适的聚类算法,提出了一种挑选聚类算法的网格连通图方法 SCGG.SCGG通过对数据潜在类结构的分析,若含有环形结构类则选择层次聚类的单连接算法对数据聚类,否则选择k-means算法.实验显示该方法十分的有效,能够挑选到合适的聚类算法对数据聚类.     

一种基于概念的数据聚类模型

在数据挖掘研究领域,现有的大多数聚类算法都受到数据可伸缩性和结果可解释性的限制.为了解决这一难题,提出了一种基于概念的数据聚类模型.该模型从描述数据样本的数据本身出发,首先在预处理后的数据集上提取基本概念,再对这些概念进行概化,形成表示聚类结果的高层概念,最后基于这些高层概念进行样本划分,从而完成整个聚类过程.该模型能够在保证聚类准确性的基础上,很大程度地减少要处理的数据量,提高原算法的可伸缩性.另外,该模型基于概念进行知识的发现与分析,能够提高聚类结果的可解释性,便于与用户交互.实验结果表明,该模型对于聚类结果较好且复杂度较高的算法尤为有效.     

基于重叠度的层次聚类算法

选择合适的聚类数和准确划分簇间重叠的数据是聚类分析领域两个被广泛研究的问题.提出了一个基于重叠度的层次聚类算法(CCSLM),该算法基于重叠度的衡量,而且不需要预先指定聚类数,能够很好地解决以上两个问题.算法根据每两簇之间的重叠情况自动运行或停止,从而准确划分簇间重叠的数据,并自动确定最佳聚类数.通过图像分割应用表明算法的有效性和鲁棒性.还把它和其他聚类算法进行比较和分析,以证明该算法的优越性.     

一种基于网格的增量聚类算法*

分析了现有基于网格的聚类算法,该算法具有高效且可以处理高维数据的特点,但传统网格聚类算法的聚类质量受网格划分的粒度影响较大。为此,提出了一种基于网格的增量聚类算法IGrid。IGrid算法具有传统网格聚类算法的高效性,且通过维度半径对网格空间进行了动态增量划分以提高聚类的质量。在真实数据集与仿真数据集上的实验结果表明,IGrid算法在聚类准确度以及效率上要高于传统的网格聚类算法。     

多维数据集中聚类数确定算法研究

在传统确定数据集聚类数算法原理的基础上,提出一种新的算法——MHC算法。该算法采用自底向上的策略生成不同层次的数据集划分,计算每个层次的聚类划分质量,通过聚类质量选择最佳的聚类数。还设计一种新的有效性指标——BIP指标,用于衡量不同划分的聚类质量,该指标主要依托数据集的几何结构。实验结果表明,该算法能准确地确定多维数据集中的最佳聚类数。     

基于层次划分的最佳聚类数确定方法

确定数据集的聚类数目是聚类分析中一项基础性的难题.常用的trail-and-error方法通常依赖于特定的聚类算法,且在大型数据集上计算效率欠佳.提出一种基于层次思想的计算方法,不需要对数据集进行反复聚类,它首先扫描数据集获得CF(clusteringfeature,聚类特征)统计值,然后自底向上地生成不同层次的数据集划分,增量地构建一条关于不同层次划分的聚类质量曲线;曲线极值点所对应的划分用于估计最佳的聚类数目.另外,还提出一种新的聚类有效性指标用于衡量不同划分的聚类质量.该指标着重于簇的几何结构且独立于具体的聚类算法,能够识别噪声和复杂形状的簇.在实际数据和合成数据上的实验结果表明,新方法的性能优于新近提出的其他指标,同时大幅度提高了计算效率.     

多层自动确定类别的谱聚类算法

自动确定聚类数和海量数据的处理是谱聚类的关键问题。在自动确定聚类数谱聚类算法的基础上,提出了一种能处理大规模数据集的多层算法。该算法的核心思想是把大规模数据集根据一定的相关性逐级进行合并,使之成为小数据集,再对分组后的小数据集用自动确定类别的谱聚类算法聚类,最后逐层进行拆分并微调, 完成全部数据的聚类。实验证明该算法的聚类效果很好。     

一种基于KNN的融合聚类算法

聚类是数据挖掘领域一个被广泛研究的问题.单一的算法较难获得高的聚类准确率,甚至对于特定的数据集也很难找出最佳的方法进行聚类分析.提出了一种基于KNN的融合聚类算法(KNNCE),该算法基于累积k最近邻产生数据点间相似度,并通过single-link算法构建层次聚类树得到最终的聚类划分,且能够自动确定最佳聚类数,从而很好地解决以上的问题.最后,通过常用数据测试和入侵检测方面的应用表明该算法是有效的.还把它和同类算法进行比较和分析,以证明算法的优越性.     

不确定GM-CFSFDP聚类算法在滑坡危险性预测中的应用

针对滑坡危险性预测中降雨等不确定诱发因素难以有效处理,CFSFDP算法需要人工尝试设置密度阈值以及对大规模数据集无法进行准确聚类等问题,为了提高滑坡危险性预测准确度,提出一种基于网格与类合并的不确定CFSFDP （简称不确定GM-CFSFDP）聚类算法.该算法首先引入不确定数据处理方法,设计了E-ML距离公式,有效刻画降雨不确定因素;其次通过网格划分的思想把大规模数据集划分到多个网格空间中,实现大规模数据有效编码;计算网格平均密度,建立网格密度阈值分布模型,动态获得网格密度阈值;最后利用层次聚类思想对关联性较高的类进行合并,构建不确定GM-CFSFDP算法模型,在延安宝塔区进行滑坡实例验证.实验结果表明不确定GM-CFSFDP聚类算法获得较高的预测精度,从而验证了该算法在滑坡危险性预测中的可行性和先进性.     

IncSNN——一种基于密度的增量聚类算法

基于密度的聚类算法是一类重要的聚类算法,能发现任意形状的簇,但由于它的时间复杂度较高,因此设计有效的增量更新算法是一个重要研究方向.在SNN算法的基础上,提出一种基于密度的增量聚类算法-IncSNN.该算法将所更新对象的空间进行划分,定义了基于该划分的最近邻居的概念,进而确定了受影响对象的集合,当算法更新时,只需要对受影响的数据进行处理.由于受影响对象的集合远小于原数据集合,因此显著提高了算法的效率.实验结果验证了IncSNN的有效性.     

基于扩展和网格的多密度聚类算法

提出了网格密度可达的聚类概念和边界处理技术,并在此基础上提出一种基于扩展的多密度网格聚类算法。该算法使用网格技术提高聚类的速度,使用边界处理技术提高聚类的精度,每次聚类均从最高的密度单元开始逐步向周围扩展形成聚类．实验结果表明,该算法能有效地对多密度数据集和均匀密度数据集进行聚类,具有聚类精度高等优点．