求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n2),对Laplacian矩阵特征分解的时间复杂度一般为O(n3),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n2).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.

熵加权多视角核K-means算法

在基于视角加权的多视角聚类中,每个视角的权重取值对聚类结果的精度都有着重要的影响。针对此问题,提出熵加权多视角核K-means(EWKKM)算法,通过给每个视角分配一个合理的权值来降低噪声视角或无关视角对多视角聚类的影响,进而提高聚类的精度。EWKKM算法中,首先用核矩阵表示不同的视角,给每个视角分配一个权重;然后,利用信息熵计算出各个视角的熵权重;最后,按照定义的目标函数对各个视角的权重进行优化,使用核K-means进行多视角聚类。在UCI数据集及人工数据集进行实验,实验结果表明熵加权多视角核K-means算法能够为每个视角分配一个最优的权重值,聚类的精确度优于已有的聚类算法,具有更稳定的聚类结果。

面向众核处理器的阴阳K-means算法优化

传统阴阳K-means算法处理大规模聚类问题时计算开销十分昂贵。针对典型众核处理器的体系结构特征,提出了一种阴阳K-means算法高效并行加速实现。该实现基于一种新内存数据布局,采用众核处理器中的向量单元来加速阴阳K-means中的距离计算,并面向非一致内存访问(non-unified memory access, NUMA)特性进行了针对性的访存优化。与阴阳K-means算法的开源多线程实现相比,该实现在ARMv8和x86众核平台上分别获得了最高约5.6与8.7的加速比。因此上述优化方法在众核处理器上成功实现了对阴阳K-means算法的加速。

一种基于抽样改进加权核K-means的大数据谱聚类算法

经典谱聚类将数据聚类转化为加权图划分问题,在分析Normalized Cut目标函数与加权核K-means函数等价基础上,设计了一种基于抽样改进加权核K-means算法的大规模数据谱聚类算法。算法通过Leaders进行初始聚类预处理,以控制后续随机抽样的数据规模及对原始数据类别的覆盖,通过抽样子集内加权核K-means迭代优化,避免Laplacian矩阵特征分解的大量资源占用,从而以部分核矩阵的使用避免全部核矩的时间、空间复杂度。试验结果表明,改进算法在保持与经典算法相近聚类精度基础上,大幅提高了聚类效率。

核k-means聚类检测复杂网络社团算法

为揭示复杂系统中的结构与功能之间的联系,复杂网络中的社团发现成为一项最基本的任务。最近,李等人提出了一种用来评估社团质量的函数,称之为模块密度函数(即D值),并利用一个核矩阵给出了模块密度目标函数与核k-means方法之间的等价性。基于这种等价性,通过过渡操作的核矩阵来优化模块密度函数并提出了一种新的核k-means算法。实验结果表明,这种算法在发现复杂网络社团上是有效的。

基于特征分箱和K-Means算法的用户行为分析方法

针对网购用户所产生的购物行为进行分析,首先通过数据处理构建客户关系管理模型(RFM模型),在此模型的基础上采用特征分箱法和K-Means聚类两种方法对用户进行细分,并对2种模型结果进行比较分析,讨论二者的差异性和具体的应用范围和意义.其中,基于特征分箱法的RFM模型将变量转化到相似的尺度上并将变量离散化,使得用户分类标签更加清晰,也可依据各类标签分类出不同类型的用户.K-Means算法通过轮廓系数评估聚类算法质量以至于选取最优K值.本文实验分析结果可为运营商提供更加可靠直观的数据,使得运营商可以根据不同用户的不同行为进行市场细分,进而进行精准营销和服务设置.

基于K-means聚类和特征空间增强的噪声标签深度学习算法

深度学习中神经网络的性能依赖于高质量的样本,然而噪声标签会降低网络的分类准确率。为降低噪声标签对网络性能的影响,噪声标签学习算法被提出。该算法首先将训练样本集划分成干净样本集和噪声样本集,然后使用半监督学习算法对噪声样本集赋予伪标签。然而,错误的伪标签以及训练样本数量不足的问题仍然限制着噪声标签学习算法性能的提升。为解决上述问题,提出基于K-means聚类和特征空间增强的噪声标签深度学习算法。首先,该算法利用K-means聚类算法对干净样本集进行标签聚类,并根据噪声样本集与聚类中心的距离大小筛选出难以分类的噪声样本,以提高训练样本的质量;其次,使用mixup算法扩充干净样本集和噪声样本集,以增加训练样本的数量;最后,采用特征空间增强算法抑制mixup算法新生成的噪声样本,从而提高网络的分类准确率。并在CIFAR10、CIFAR100、MNIST和ANIMAL-10共4个数据集上试验验证了该算法的有效性。

基于改进K-means数据聚类算法的网络入侵检测

随着入侵手段的不断更新和升级,传统入侵检测方法准确率下降、检测时间延长,无法满足网络防御要求。为此,提出一种经过改进K均值(K-means)数据聚类算法,以应对不断升级的网络入侵行为。先以防火墙日志为基础转换数值,然后基于粒子群算法求取最优初始聚类中心,实现K-means数据聚类算法的改进;最后以计算得出的特征值为输入项,实现对网络入侵行为的精准检测。结果表明:K-means算法改进后较改进前的戴维森堡丁指数更小,均低于0.6,达到了改进目的。改进K-means算法各样本的准确率均高于90%,相对更高,检测时间均低于10 s,相对更少,说明该方法能够以高效率完成更准确的网络入侵检测。

基于改进K-means算法的物流配送中心选址研究

针对传统K-means算法需要主观设定K值及无法处理类别型数据问题,文章运用肘部法及轮廓系数法确定合理K值,对类别型数据采取独热编码(One-Hot Encoding)转换为可以处理的连续型数据,并将其运用到在物流配送中心选址中;并综合考虑多种类别的影响因素,构建了相应的影响因素指标体系,提出的模型能够识别输入数据的数值型及类别型数据,实现样本的有效聚类。相关的案例分析结果表明,相比传统K-means聚类,文章的改进K-means算法选址结果可使物流总成本降低8.76%,运营成本降低14.85%,固定成本降低8.09%,效果显著。

基于K-means算法的建筑群震害分析模型缩减方法

基于建筑群模型和弹塑性时程分析的精细化城市震害模拟技术能够为防震减灾及应急救援决策提供必要的依据和参考。为了减小城市建筑群震害模拟的计算量和计算时间,本文提出一种基于聚类算法的建筑群模型缩减方法。该方法采用K-means聚类算法,首先基于建筑结构属性向量对建筑群进行聚类,将相似的建筑结构聚为一组;然后从每组选取一个代表建筑组成建筑群缩减模型,通过减少需要分析的建筑结构数量来减少建筑群震害模拟的计算量。本文对传统的K-means算法进行改进,通过设定组内建筑结构的差异上限自动调整聚类分组数量;提出将具体地震动作用下结构地震损伤指数作为结构属性向量进行聚类,并通过算例对比分别采用两种缩减模型,即基于损伤指数聚类的缩减模型与基于结构力学模型参数聚类的缩减模型,计算结构损伤状态准确程度。对比结果表明:在聚类分组数量相同的情况下,基于损伤指数的分组明显优于基于模型参数的分组,采用模型缩减方法能够在保证足够计算精度前提下显著减少建筑群震害模拟计算量和计算时间。

基于改进K-means聚类和遗传算法的混合算法求解异构车辆路径问题

由于目前单一车型配送存在资源浪费和效率低下等问题,选取确定数量的不同车型对各客户点进行配送服务往往可以得到更优的配送路径方案。针对这一点,描述了一种异构车辆路径问题,并建立了具有固定车辆数且考虑固定成本、可变成本以及时间窗惩罚成本的混合整数规划模型。同时,提出了一种基于改进K-means聚类和遗传算法的混合算法对模型进行求解。实验仿真先求解不考虑时间窗的问题初步证明混合算法的有效性,再在带时间窗的问题中求解不同规模算例的单一及异构车型结果,以证明异构车型配送更优。最后,对该混合算法的求解结果与其他混合算法的求解结果进行对比分析,证明了混合算法的优越性。研究结果表明:该混合算法求解的异构车型结果优于单一车型,并且比其他混合算法求解的异构车型结果更优,异构车辆配送使用的配送车辆数更少,总成本也更低,该混合算法具有更好的效率和性能。

基于蚁群算法的三支k-means聚类算法

在聚类分析中,三支k-means聚类算法较具有较强的处理边界不确定数据的能力,但仍然存在对初始聚类中心敏感的问题.通过将蚁群算法和三支k-means聚类算法相结合,给出了一种基于蚁群算法的三支k-means聚类算法来解决这一问题.利用蚁群算法中随机概率选择策略和信息素的正负反馈机制,动态调整权重的方法,对三支k-means聚类算法进行优化.在UCI数据集上实验证明,该方法对聚类结果的性能指标有所提高.

基于核化K-means和SVM分类回归的Wi-Fi室内定位算法

针对目前指纹室内定位系统指纹库管理效率低、实时性差和定位精度低的问题,提出了一种新的基于核化K-means和SVM分类回归的无线定位算法。首先利用核化K-means算法将输入的预处理后的RSS(Received Signal Strength)信号进行无监督聚类,将聚类后的数据信息存入指纹特征数据库,然后通过SVM回归的机器学习算法对特征数据库的数据进行训练,得到一种最优的拟合位置函数的数学模型。并且采用粒子群算法对参数进行寻优,进行实验仿真。实验结果表明,该算法有效地提升了定位精度,优于KNN、WKNN、SVR等室内定位算法。

启发式k-means聚类算法的改进研究

启发式k-means聚类算法通过在k-means第一次迭代后查看附近的集群来预测每个数据点可能会被划分到的集群子集,有效地加快了算法的运行速度。但由于启发式算法存在随机选择初始聚类中心以及无法有效识别数据集中离群点的缺陷,导致聚类结果的误差平方和较大并且轮廓系数偏小。针对这一问题,提出了CHk-means算法,该算法引入仔细播种方法,克服了启发式k-means算法随机选择初始聚类中心带来的局部最优解问题;该算法引入局部异常因子LOF算法对离群点进行检测,降低了离群点数据对聚类结果的影响。在多个数据集上对3种算法进行对比试验,结果表明CHk-means算法可有效降低聚类结果的误差平方和,增强聚类的轮廓系数,使聚类质量得到明显改善。

粗糙核k-means聚类算法

通过研究核聚类算法,以及粗糙集,提出了一个新的用于聚类分析的粗糙核聚类方法。通过mercer核映射把输入空间中的样本映射到Hilbert空间,使样本空间中没有显现的特征在特征空间中突现出来,在这种样本差异加大的基础上,结合粗糙集的思想,把样本分别划到相应聚类中心的上、下近似中,上、下近似中的样本按照一定的比例来共同决定新的聚类中心。这样不但聚类精度大大提高,而且算法收敛速度也较快。仿真实验的结果表明该算法的可行性和有效性。

基于马氏距离和Canopy改进K-means的交通聚类算法

在对交通数据的研究中经常会使用到聚类算法,且不同的聚类算法有不同的特性。K-means作为其中的一种聚类算法,具有较高的准确性和实用性,但其准确性易受主观选取K值和确定初始聚类中心的影响。为了优化聚类中心和K值的选取问题,提出MC-Kmeans算法。在所提方法中,首先通过Canopy算法选取K值,然后依据马氏距离的计算准则来确定初始聚类中心,最后将K值和聚类中心的值作为K-means的参数进行聚类。将MC-Kmeans算法应用到某时间段的纽约出租车交通数据中进行实际的验证。结果表明,与K-means算法比较,所提方法准确度更高,与实际交通情况更加相匹配,更能反映区域内的交通热点情况。

一种融合乌鸦搜索算法的K-means聚类算法

传统的K-均值聚类算法(K-means)对初始聚类中心的选择敏感,容易陷入局部最优解,并且需要预先设定聚类数量K,这在实际操作中往往难以实现。为了解决这些问题,提出了一种融合乌鸦搜索算法的K-means聚类算法。该算法利用乌鸦搜索算法的全局搜索能力,自动确定最佳的聚类数目K,从而提高聚类的质量和效率。通过在Seeds数据集进行实验计算卡林斯基-哈拉巴斯(Calinski-Harabasz)指数等评价指标,发现该算法聚类效果明显优于传统的K-means算法。

基于BBO优化K-means算法的WSN分簇路由算法

针对无线传感器网络中传感器节点能量有限、网络生存期短的问题,提出一种基于生物地理学算法优化K-means的无线传感器网络分簇路由算法BBOK-GA。成簇阶段,通过生物地理学优化算法改进K-means算法,避免求解时陷入局部最优。根据能量因子和距离因子设计了新的适应度函数选举最优簇首,完成分簇任务。数据传输阶段,则利用遗传算法为簇首节点搜寻到基站的最佳数据传输路径。仿真结果表明,相较于LEACH、LEACH-C、K-GA等算法,BBOK-GA降低了网络能耗,提高了网络吞吐量,延长了网络生存周期。

基于改进K-means聚类算法的网络异常数据挖掘与分类方法

为了解决网络异常数据挖掘过程中漏报率、误报率较高的问题,文章提出一种基于改进K-means聚类算法的网络异常数据挖掘与分类方法。文章通过构建并行化频繁项集挖掘环境加速数据处理,利用局部离群点检测剔除异常值,同时引入K-means聚类对数据的最大最小距离展开计算,融合隶属度函数与密度峰值优化算法,改进聚类初始中心选择及簇边界调整,从而提高异常识别准确性和分类效率。通过实验结果证明,该方法能够明显改善聚类效果与性能。

基于随机森林算法和K-means算法的网络攻击识别方法

5G网络与核电的深度融合能够提升核电厂生产安全管控水平,减少人为事故,促进核电行业安全和经济发展。但由于网络的接入,为核电安全生产带来了一定的安全风险,恶意攻击者会通过向核电5G网络发起攻击进而破坏核电生产。为了解决核电5G网络场景下面临的网络异常和恶意攻击的问题,提出了一种在核电5G网络场景下基于随机森林算法和K-means算法的实时网络异常检测和网络攻击识别方法,对于提高核电网络安全具有重要的意义。