二分k-means锚点提取的快速谱聚类

光谱聚类(spectral clustering,SC)由于在无监督学习中的有效性而受到越来越多的关注。然而其计算复杂度高,不适用于处理大规模数据。近年来提出了许多基于锚点图方法来加速大规模光谱聚类,然而这些方法选取的锚点通常不能很好地体现原始数据的信息,从而导致聚类性能下降。为克服这些缺陷,提出了一种二分k-means锚点提取的快速谱聚类算法(fast spectral clustering algorithm based on anchor point extraction with bisecting kmeans,FCAPBK)。该方法利用二分k-means从原始数据中选取一些具有代表性的锚点,构建基于锚点的多层无核相似图;然后通过锚点与样本间的相似关系构造层次二部图。最后在5个基准数据集上分别进行实验验证,结果表明FCAPBK方法能够在较短的时间内获得良好的聚类性能。

基于二分K-means的无线传感器网络分簇方法

好的分簇方法可以通过有效提高网络能量利用率均衡网络负载延长网络生命周期,文章提出一种基于二分K-means的均匀分簇算法(uniform clustering optimization algorithm,UCOA)。该算法首先基于对网络能耗的理论分析确定网络最优簇头数目,然后基于最优簇头数目利用二分K-means算法对整个网络均匀分簇,加入节点剩余能量和距离因子改进簇头选举阈值公式,并且在簇头与基站通信时采用单跳和多跳相结合的数据传输方式。仿真实验表明UCOA分簇算法能有效提高节点耗能均衡性,延长网络生存时间。

基于iForest+Biscting K-means的驾驶风格辨识方法研究

提出了一种基于iForest+Biscting K-means模型的客运驾驶员驾驶风格辨识方法。该方法针对在Bisceting Kmeans模型中,聚类质心严重影响聚类结果问题,采用iForest模型训练聚类中心候选集作为聚类质心集的方法加以改进。通过考察某城际客运线路30位客车职业驾驶员,在直线道路行驶工况下,90余天约400万条客车行驶数据开展模型验证。试验表明:在加速度标准差和超速倾向系数作为聚类指标的情况下,客运驾驶员驾驶风格聚类为谨慎型、普通型和激进型3类,其中谨慎型11人,普通型19人,激进型0人。

基于部分实例重判的二分K-means算法

针对二分K-means算法存在的误判实例无法再参与后续划分并降低了聚类的精度的问题.提出一种基于部分实例重判的二分K-means算法,通过区分目标簇和候选簇,过滤出候选簇中的召回实例,对召回实例所应归属的簇进行重判,实现了误判实例的正确聚类.实验结果表明,改进算法对三个实验数据集都是有效的,在不同程度上提高了聚类的准确性,同时对算法的运行速度也有小幅度的提升.

基于二分K-means的测试用例集约简方法

测试用例集约简是软件测试中的重要研究问题之一,目的是以尽量少的测试用例达到测试目标。为此,提出一种新的测试用例集约简方法。应用二分K-means聚类算法对回归测试的测试用例集进行约简,以白盒测试的路径覆盖为准则,对每个测试用例进行量化,使每个用例变成一个点。以黑盒测试的功能需求数作为聚类数,在聚类结果的每一簇中,按照离中心点的距离进行排序,依次从每一簇中选择测试用例,直至满足所有测试需求,得到约简的测试用例集。实验结果表明,该方法能有效地减小测试用例集的规模,降低用例集检错率。

基于距离和密度的PBK-means算法

K-means算法初始中心点选择的随机性以及对噪声点的敏感性,使得聚类结果易陷入局部最优解,为获得最佳初始聚类中心,提出一种基于距离和密度的并行二分K-means算法。计算数据集的平均样本距离,根据数据点之间的距离计算数据的权重,选择最大权重数据点作为第一个中心点,小于平均样本距离的数据点不参加下一次聚类,将剩余数据点的权重与中心点距离相乘,选择值最大的数据点作为下一个中心点,得到两个中心点后按照距离对数据进行分配,将每个中心点代表的类分为两类后在每类上继续重复上述步骤。通过模仿细胞分裂的方法对数据进行切分,构建一棵满二叉树,当叶子结点数超过类别数k时停止聚类,合并叶子结点得到k个初始聚类中心执行K-means算法。在UCI公开数据集上进行测试,结果表明,对比传统K-means算法、Canopy-Kmeans算法、二分K-means算法、WK-means算法、MWK-means算法和DCK-means算法,该算法效率更高,具有较好的聚类效果。

K-means算法中k的自动确定

K-means算法在无监督学习中有着广泛的应用。然而,K-means算法有两个主要缺点,一是容易陷入局部极小,二是需要用户事先指定参数k。二分K-means算法的提出解决局部极小的问题。利用二分K-means算法过程中每次分裂产生的新质心间距离的变化规律可以对二分K-means算法做进一步的改进,从而将实际类别个数k的确定自动化。

二分K-FCM结合算法在交通运行状态判别中的应用

正确判别交通运行状态是交通运营管理的理论依据。以高速公路交通状态判别为研究对象,综合考虑交通流三参数(流量、速度、占有率)的基础上,应用模糊C均值(FCM)与二分K均值结合算法对交通运行状态进行判别。首先,对交通数据集分布特征及交通运行状态特征进行分析,确定以V05~V85为最小欧氏距离判别的数据范围。其次,为解决算法收敛较慢及任意初始化质心对聚类结果的不良影响,对传统模糊C均值聚类算法进行了改进,将运行二分K均值算法的聚类结果矩阵作为FCM的初始聚类中心。经检验,改进的FCM可以有效减少算法迭代次数,得到的目标路段交通状态判别矩阵能较精准地划分高速公路不同的交通状态。

基于二分K-均值的SVM决策树自适应分类方法

分析和研究了自适应降维算法在高维数据挖掘中的应用。针对已有数据挖掘算法因维灾难导致的在处理高维数据时准确率和聚类质量都较低的情况,将二分K-均值聚类和SVM决策树算法结合在一起,提出了一种适用于高维数据聚类的自适应方法 BKM-SVMDT。该算法能保证二分K-均值聚类是在低维数据空间中进行,其结果再反过来帮助SVM在高维空间中的执行,这样反复执行以取得较好的分类精度和效率。标准数据集的实验结果证明了该方法的有效性。

无线信道建模中二分K均值聚类多径分簇算法

为了对无线信道中的多径分量进行合理分簇,提出了一种毫米波信道二分K均值聚类多径分簇方法,解决了传统的K均值聚类分簇方法只能实现局部最优分簇的问题.采用马氏距离(Mahalanobis distance,MD)衡量多径分量距离(multi-path component distance,MCD),以簇分裂和迭代计算的方式对多径进行分簇.采用毫米波室内信道实验测试数据,验证了所提算法的有效性和可行性.结果表明,所提算法比传统K均值聚类分簇方法获得的分簇结果更合理,能将信道中多径参数相似度较高的多径有效且唯一地分配到同一簇.

基于VSM和Bisecting K-means聚类的新闻推荐方法

针对海量新闻数据给用户带来的困扰,为提升用户阅读新闻的个性化体验,提出了融合向量空间模型和Bisecting K-means聚类的新闻推荐方法.首先进行新闻文本向量化,使用向量空间模型和TF-IDF算法构建出新闻特征向量;采用Bisecting K-means聚类算法对新闻特征向量集进行聚类;然后将已聚类的新闻集分为训练集和测试集,根据训练集构建"用户—新闻类别—新闻"三层层次结构的用户兴趣模型;最后采用余弦相似度方法得出新闻推荐结果,并与测试集进行对比分析.实验以基于用户的协同过滤算法、基于物品的协同过滤算法、结合向量空间模型和K-means聚类的推荐方法为基准,实验结果表明,该方法具有可行性,在准确率、召回率和F值上都有所提高.

基于密度和中心指标的Canopy二分K-均值算法优化

针对二分K-均值算法由于随机选取初始中心及人为定义聚类数而造成的聚类结果不稳定问题,提出了基于密度和中心指标的Canopy二分K-均值算法SDC_Bisecting K-Means。首先计算样本中数据密度及其邻域半径;然后选出密度最小的数据并结合Canopy算法的思想进行聚类,将得到的簇的个数及其中心作为二分K-均值算法的输入参数;最后在二分K-均值算法的基础上引入指数函数和中心指标对原始样本进行聚类。利用UCI数据集和自建数据集进行模拟实验对比,结果表明SDC_Bisecting K-Means不仅使得聚类结果更精确,同时算法的运行速度更快、稳定性更好。

基于差分隐私保护的二分k均值聚类算法研究

针对差分隐私保护k均值聚类算法(DP k-means)随机选取初始点,导致算法往往收敛于局部最优,进而影响聚类效果的问题,本文结合差分隐私的相关理论以及层次聚类的思想提出了一种基于差分隐私保护的二分k均值聚类算法(DP Bi-k-means)。首先,以得到全局最优为目标,将随机选取初始点的过程进行改进,由上至下对目标数据集进行二分;其次,在迭代过程实现基于拉普拉斯机制的差分隐私保护。经安全性分析以及实验结果证明:该算法与传统差分隐私保护k均值算法(DP k-means)相比,可以避免聚类结果受初始点的影响陷入局部最优解,从而优化聚类效果,并为聚类分析提供了有效的隐私保护能力。

基于邻域平均距离的离群点检测算法

离群点检测是数据挖掘领域的一个热点问题,离群点检测可以有效地识别出数据集中的离群点,为数据分析提供方便。为提高数据分析精度,有效筛选离群点,提出一种基于邻域平均距离的离群点检测算法。首先计算误差平方和并使用肘部法确定最佳聚类个数K,然后将K代入K-Means的优化算法二分K-Means中对数据集进行聚类处理,从而得到K个数据簇,最后分别计算每个簇中质心ε邻域的邻域平均距离,将与质心距离大于阈值距离的样本点作为离群点集。实验结果表明,在标准数据集UCI上,该算法的检测率有较好的表现。

二分K均值聚类算法优化及并行化研究

二分K均值聚类算法在二分聚类过程中的初始质心选取速度方面存在不足。为此,提出以极大距离点作为二分聚类初始质心的思想,提升算法的运行速度。研究如何在群集系统中进行快速聚类,根据二分K均值聚类算法的特性,采用数据并行的思想和均匀划分的策略,对算法进行并行化处理。实验结果表明,改进后的算法能获得比较理想的加速比和较高的使用效率。

改进的二分K均值聚类算法

K均值算法是一种常用的基于原型的聚类算法。但该算法要求用户随机选择初始质心,使得K均值算法受初始化影响较大。二分K均值算法虽然改善了这个问题,但仍然要求用户指定聚类个数,影响了聚类效果。用层次聚类对二分法进行改进,解决了二分K均值算法受用户指定的聚类个数的影响的问题。并结合Chameleon算法,合并划分过细簇,优化聚类结果。仿真实验证明改进的聚类算法的抱团性和分离性优于二分K均值聚类算法。

基于FKNN算法的风电功率短期预测

风电场输出功率预测精度的提高能够极大的减轻风力发电对电网的冲击,提高风电并网的安全性和可靠性。针对KNN(K-Nearest Neighbor algorithm)算法存在的不足进行改进,提出了FKNN(Fast K-Nearest Neighbor algorithm)算法并将其应用到风电短期功率预测当中。首先,FKNN算法基于相似数据原理,针对每个预测样本,只需遍历一次训练样本集,得出K值最大时的相似历史样本优先级队列。然后,通过逐渐缩减优先级队列的长度,产生其他K值对应的相似样本优先级队列。其次,从产生的优先级队列中获取多数类样本,并应用其输出功率的平均值对预测样本的输出功率进行预测。最后,通过对吉林省某风电场的大量历史数据进行预测分析,充分证明该算法的简单性和实用性。

Spark平台下聚类算法的性能比较

通过实验,从运行时间、加速比、可扩展性和规模增长性4个方面比较了Spark平台中3种典型的聚类算法即K-means聚类算法、二分K-means聚类算法和高斯混合聚类算法的性能。实验结果表明:1)随着节点个数的增加,3种算法对百兆以上规模数据集聚类的运行时间明显减少;2)当数据集规模大于500MB时,3种算法的加速比均有明显提高,且随着节点个数的增加,加速比近似于线性增长;3)3种算法的可扩展性随着节点个数的增加而降低,当数据集规模大于500MB时,相对于K-means和高斯混合算法,二分K-means算法的可扩展性最差;4)当数据集规模大于100MB时,高斯混合算法的规模增长性远高于K-means和二分K-means算法。

基于聚类和K近邻算法的井下人员定位算法

针对现有基于指纹模的井下定位算法存在的计算量大、实时性低、定位精度较低的问题,提出了基于聚类和K近邻算法的井下人员定位算法。用二分k-means聚类算法对采集的RSSI数据进行分类,建立离线指纹数据库;无线移动终端和动态修正器实时采集RSSI值,分别存储到在线定位数据库和动态修正数据库;根据待测点和动态修正器的离线数据和实时数据,采用软硬件动态修正加权K近邻算法计算权重值,结合离线指纹数据库中待测点的物理位置信息估算其实时位置。实验分析结果表明,所提定位算法的最小标准误差为0.46m,最大标准误差为3.26m,平均误差为1.62m。对比分析结果表明,与未进行聚类分析的算法相比,本文算法的精度更高,实时性更好;与未动态修正权重值的算法相比,本文算法的运算时间略有增加,但定位精度提高了37.21%。

基于内聚度和耦合度的二分K均值方法

聚类分析是数据挖掘中最重要的技术之一,它在社会经济的各个领域都具有重要作用,并被广泛应用。K均值算法是最经典、应用最广泛的聚类方法之一,但其缺点是过度依赖初始条件和聚类数目难以确定,这制约了其应用范围。引入簇的内聚度和耦合度的定义与度量方法,基于"高内聚低耦合"的原理,在二分K均值聚类过程中对得到的簇进行不断的分裂和合并,并判断聚类结果是否满足要求以确定聚类的次数和簇的个数,从而实现对二分K均值聚类过程的改进。在Iris数据集上的实验测试与分析表明该算法不仅更加稳定,而且其聚类结果的正确率也较高。