基于K-means的最佳聚类数确定方法研究

确定数据集的最佳聚类数是聚类研究中的一个重要难题。为了更有效地确定数据集的最佳聚类数,该文提出了通过改进K-means算法并结合一个不依赖于具体算法的有效性指标Q(c)对数据集的最佳聚类数进行确定的方法。理论分析和实验结果证明了该方法具有良好的性能和有效性。     

基于样本空间分布密度的改进次胜者受罚竞争学习算法

针对传统次胜者受罚竞争学习(RPCL)算法忽略数据集几何结构对节点权值调整的影响,以及魏立梅等提出的新RPCL算法(魏立梅,谢维信.聚类分析中竞争学习的一种新算法.电子科学学刊,2000,22(1):13-18)引入密度来对节点的权值进行调整时,密度定义的主观性,提出基于样本空间分布密度的改进RPCL算法。该算法根据数据集样本自然分布定义样本密度,将此密度引入RPCL节点权值调整;使用UCI机器学习数据库数据集以及随机生成的带有噪声点的人工模拟数据集对算法进行实验测试,对算法确定数据集类簇数目的准确率、运行时间、聚类误差平方和、聚类结果的Rand指数、Jaccard系数以及Adjust Rand index参数进行分析比较。各项实验结果显示:所提算法优于原始RPCL算法和魏立梅算法,具有更好的聚类效果,对噪声数据有很强的抗干扰性能。所提算法不仅能根据样本的自然分布确定数据集的合理类簇数目,而且能确定合适的类簇中心,提高聚类的准确性,使聚类结果尽可能快地收敛到全局最优解。     

一种隶属关系不确定的可能性模糊聚类方法

模糊聚类是聚类分析的一个重要分支,模糊C-均值聚类算法及其改进算法都是一种基于概率约束的聚类方法,所采用隶属度的取值形式体现了数据集的绝对隶属程度,常常出现不理想的聚类结果.对此,提出了不确定隶属的概念,在此基础上,通过提出两个基于相对隶属程度的判断准则参数,设计出一种新的基于隶属关系不确定的可能性模糊聚类新算法,并给出了具体算法实现.新算法将迭代过程中数据集对聚类簇隶属的可能性与不确定性关系引入目标函数中,达到明显的优化聚类结果的功效.理论分析和实验结果表明,相对其他聚类算法,新算法具有更高的聚类正确率.     

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

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

基于LPCA的谱聚类算法

针对传统谱聚类在构建关系矩阵时只考虑样本的全局特征而忽略样本的局部特征、在聚类划分时通常需要指定聚类个数、无法对交叉点进行正确划分等问题,提出了一种改进的基于局部主成分分析和连通图分解的谱聚类算法。首先自动学习挑选数据集的中心点,然后使用局部主成分分析得到数据集的关系矩阵,最后用连通图分解算法完成对关系矩阵的划分。实验结果表明提出的改进算法性能优于现有经典算法。     

自动确定聚类中心的密度峰聚类

密度峰聚类是一种新的基于密度的聚类算法,该算法不需要预先指定聚类数目,能够发现非球形簇。针对密度峰聚类算法需要人工确定聚类中心的缺陷,提出了一种自动确定聚类中心的密度峰聚类算法。首先,计算每个数据点的局部密度和该点到具有更高密度数据点的最短距离;其次,根据排序图自动确定聚类中心;最后,将剩下的每个数据点分配到比其密度更高且距其最近的数据点所属的类别,并根据边界密度识别噪声点,得到聚类结果。将新算法与原密度峰算法进行对比,在人工数据集和UCI数据集上的实验表明,新算法不仅能够自动确定聚类中心,而且具有更高的准确率。     

Chameleon算法的改进

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

障碍空间中不确定数据聚类算法

近些年,由于数据采集的不精确和数据本身的不确定性,使不确定性在位置数据中普通存在。在障碍空间中,聚类不确定数据面临新的挑战。提出了障碍空间中聚类不确定数据的OBS-UK-means(obstacle uncertain K-means)算法,并提出了分别基于R树和Voronoi图的两种剪枝策略和最近距离区域的概念,大大减少了计算量。通过实验验证了OBS-UK-means算法的高效性和准确性,同时证明了剪枝策略在不损害聚类有效性的情况下,能够有效地提高聚类效率。     

关键节点选择的快速图聚类算法

在众多聚类算法中,谱聚类作为一种代表性的图聚类算法,由于其对复杂数据分布的适应性强、聚类效果好等优点而受到人们的广泛关注.然而,由于其高计算时间复杂度难以应用于处理大规模数据.为提高谱聚类算法在大规模数据集上的可用性,提出关键节点选择的快速图聚类算法.该算法包含三个重要步骤:第一,提出一种充分考虑抱团性和分离性的快速节点重要性评价方法;第二,选择关键节点代替原数据集构建二分图,通过奇异值分解获得数据的近似特征向量;第三,集成多次的近似特征向量,提高近似谱聚类结果的鲁棒性.该算法将时间复杂度由谱聚类原有的O(n3)降低到O(t(n+2n2)),增强了其在大规模数据集上的可用性.通过该算法与其他七个具有代表性的谱聚类算法在五个Benchmark数据集上进行的实验分析,比较结果展示了该算法相比其他算法能够更加高效地识别数据中的复杂类结构.     

基于二部图的概念聚类研究

传统概念聚类算法中簇的更新和存储不仅依赖于对象数目和属性数目,而且依赖于属性值的数目,这种局限性使其不适用于大型数据集。提出一种新的基于二部图的概念聚类算法（BGBCC）,该算法通过获得二部图的近似极大ε二元组集,有效地进行数据与属性的关联聚类。实验表明,该算法能得到较好的聚类结果,且能在较短的时间内进行大型数据集的概念聚类。     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

不确定数据信任密度峰值聚类算法

密度峰值聚类算法具有简单高效、无需迭代计算和提前设定类簇数的优势,但是在划分非类中心样本时容易产生“多米诺骨牌”效应,并且不能准确划分重叠区域的样本和噪声。为了解决以上问题,提出了不确定数据信任密度峰值聚类算法。首先,该算法在密度峰值聚类算法获取类中心样本的基础上,利用非类中心样本的K近邻求出样本属于不同类的信任值,将...     

优化初始聚类中心选择的K-means算法

K-means算法的聚类效果与初始聚类中心的选择以及数据中的孤立点有很大关联,具有很强的不确定性。针对这个缺点,提出了一种优化初始聚类中心选择的K-means算法。该算法考虑数据集的分布情况,将样本点分为孤立点、低密度点和核心点,之后剔除孤立点与低密度点,在核心点中选取初始聚类中心,孤立点不参与聚类过程中各类样本均值的计算。按照距离最近原则将孤立点分配到相应类中完成整个算法。实验结果表明,改进的K-means算法能提高聚类的准确率,减少迭代次数,得到更好的聚类结果。     

基于聚合距离参数的改进K-means算法

针对传统K均值聚类（K-means）算法随机选择初始中心及K值导致的聚类结果不确定且精度不高问题,提出了一种基于聚合距离的改进K-means算法。首先,基于聚合距离参数筛选出优质的初始聚类中心,并将其作用于K-means算法。然后,引入戴维森堡丁指数（DBI）作为算法的准则函数,循环更新聚类直到准则函数收敛,最后完成聚类。改进算法提供了优质的初始聚类中心及K值,避免了聚类结果的随机性。二维数值型仿真数据的聚类结果表明,改进算法在数据样本数达到10000时仍能保持较好的聚类效果。针对Iris和Seg这两个UCI标准数据集的调整兰德系数,改进算法比传统算法性能分别提高了83.7%和71.0%,最终验证了改进算法比传统算法聚类结果的准确性更高。     

基于一致图学习的鲁棒多视图子空间聚类

针对多视图数据分析易受原始数据集噪声干扰,以及需要额外的步骤计算聚类结果的问题,提出一种基于一致图学习的鲁棒多视图子空间聚类（RMCGL）算法。首先,在各个视图下学习数据在子空间中的潜在鲁棒表示,并基于该表示得到各视图的相似度矩阵。随后,基于得到的多个相似度矩阵学习一个统一的相似度图。最后,通过对相似度图对应的拉普拉斯矩阵添加秩约束,确保得到的相似度图具有最优的聚类结构,并可直接得到最终的聚类结果。该过程在一个统一的优化框架中完成,能同时学习潜在鲁棒表示、相似度矩阵和一致图。RMCGL算法的聚类精度（ACC）在BBC、100leaves和MSRC数据集上比基于图的多视图聚类（GMC）算法分别提升了3.36个百分点、5.82个百分点和5.71个百分点。实验结果表明,该算法具有良好的聚类效果。     

基于相似图投影学习的多视图聚类

随着数据来源方式的多样化发展,多视图聚类成为研究热点。大多数算法过于专注利用图结构寻求一致表示,却忽视了如何学习图结构本身;此外,一些方法通常基于固定视图进行算法优化。为了解决这些问题,提出了一种基于相似图投影学习的多视图聚类算法(multi-view clustering based on similarity graph projection learning, MCSGP),通过利用投影图有效地融合了全局结构信息和局部潜在信息到一个共识图中,而不仅是追求每个视图与共识图的一致性。通过在共识图矩阵的图拉普拉斯矩阵上施加秩约束,该算法能够自然地将数据点划分到所需数量的簇中。在两个人工数据集和七个真实数据集的实验中,MCSGP算法在人工数据集上的聚类效果表现出色,同时在涉及21个指标的真实数据集中,有17个指标达到了最优水平,从而充分证明了该算法的优越性能。     

图的多视角一致性稀疏聚类

提出了一种新的面向图的一致性多视角稀疏聚类框架,该方法先将多视角数据分解为一致性与不一致性部分;然后采用相似性度量方法与KNN(K-nearest neighbor)算法对多视角数据进行分解与融合;再运用稀疏表示学习多视角图的一致性相似矩阵,进而通过谱聚类获取聚类结果.最后,设计并实现了一种交替迭代优化算法求解目标函数,并在八个多视角数据集上通过对比实验验证了该方法的有效性.     

基于改进花朵授粉的K-均值聚类算法

针对K-means聚类算法依赖于初始值并易陷入局部最优值的问题,提出了一种基于改进花朵授粉的K-means聚类算法。该算法首先通过混沌映射的序列作为花朵种群的初值位置,保证花朵种群在搜索空间的多样性、确定性;然后在花朵授粉的后期搜索阶段引入禁忌搜索算法以避免陷入局部最优解;最后将改进后的FPA算法用于优化K-means算法的初值。在五个聚类数据集上的实验结果表明,改进后算法的平均聚类准确率相比于花朵授粉聚类算法提高了12.2%,证明了该算法对于低维数据集具有更好的聚类效果。     

特征逐减的可能性模糊聚类算法

模糊C均值聚类（FCM）和可能性模糊C均值聚类（PFCM）没有考虑样本特征项及每个样本对聚类的贡献程度，存在对噪声较敏感的问题。特征减少的模糊聚类算法FRFCM可剔除数据集中无效特征量，且考虑了剩余特征量的权重，具有更好的聚类性能。对此，在可能性模糊C均值聚类算法（PFCM）的基础上将其与FRFCM算法相结合，提出新的特征逐减的可能性模糊C均值聚类算法（FRPFCM）。该算法解决了PFCM算法参数依赖的问题，且在迭代过程中可自动淘汰无效特征项并更新各特征项对聚类的贡献程度。对人工数据集以及UCI数据集进行测试的结果表明，提出的FRPFCM算法可得到更高的聚类准确率，所需迭代次数更少，算法收敛速度更快。     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连 接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动 态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表 明,挖掘结果在真实应用中具有实际意义.