一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

用于网络重叠社区发现的粗糙谱聚类算法

针对绝大多数社区发现算法都存在着网络节点仅隶属于一个社区的假设,引入谱图理论与粗糙集理论来分析复杂网络社区,提出一种用于网络重叠社区发现的粗糙谱聚类算法RSC,该算法用上下近似来刻画网络节点的社区归属,边界表示社区之间共享的节点,通过优化重叠社区结构模块度来实现重叠社区发现.通过3个不同类型真实网络的仿真实验,结果验证了该方法的可行性与有效性.     

一种基于粗糙集理论的谱聚类算法

谱聚类算法利用特征向量构造简化的数据空间,在降低数据维数的同时,使得数据在子空间中的分布结构更加明显.现有谱聚类算法的聚类结果多为精确集,而真实数据集中重叠现象广泛存在.基于粗糙集理论提出了一种新的谱聚类算法,其主要思想是对谱聚类算法进行粗糙集扩展,使得聚类结果成为具有下近似和上近似定义的、类与类之间存在重叠区域的结构.实验表明,该算法与现有的谱聚类算法相比,稳定性和准确率都有一定的提高.     

基于边密度聚类的重叠社区发现算法

基于边聚类的社区发现算法以边为聚类对象,自然发现重叠社区,但也存在生成的社区集边界归属模糊、社区结构过度重叠等问题.基于此种情况,文中提出基于边密度聚类的重叠社区发现算法.首先,以边为研究对象,通过密度聚类检测连接紧密的核心边社区.然后,根据边界边归属策略将边界边划分到离它最近的核心边社区.针对孤立边,提出基于边的度与边的社区归属的孤立边处理策略,进一步处理未划分的孤立边,避免社区结构过度重叠的问题.最后,将边社区还原为节点社区,实现重叠社区的发现.在人工数据集和真实数据集上的实验表明,文中算法可以快速准确地检测复杂网络中的重叠社区.     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于谱聚类的动态网络社区演化分析算法

针对复杂网络社区受到个体兴趣和迁移的影响随着时间推移而演化的问题,提出一种基于谱聚类的动态网络社区演化分析算法,试图揭示动态网络社区结构随时间的演变过程.算法融合当前时刻快照拓扑结构和上一时刻社区结构两个因素,并用随机分块模型和Dirichlet分布分别对上述两个因素建模,从而将社区演化分析形式化为优化问题.从理论上验证了社区演化分析与谱聚类是等价的,为利用谱聚类解决社区演化分析奠定理论基础.在合成数据集上的实验结果表明,相比于以规格化割为目标的谱聚类,所提方法能显著提升动态社区检测的准确性和稳定性.     

多样性引导的深度多视图聚类算法

多视图聚类旨在从不同视图的多样性信息中, 学习到更加全面和准确的共识表示, 以提高模型的聚类性能. 目前大部分多视图聚类算法采用希尔伯特-施密特独立性准则(HSIC)或自适应加权方法从全局考虑各视图的多样性, 忽略了各视图样本之间的局部多样性信息学习. 针对上述问题, 提出了多样性引导的深度多视图聚类算法. 首先, 提出了融合多头自注意力机制的软聚类模块, 多头自注意力机制用来学习全局多样性, 软聚类模糊C均值算法用来学习局部多样性; 其次, 在深度图自编码器网络结构中引入软聚类模块, 以达到多样性信息引导潜在表示生成的目的; 然后, 将得到的各视图潜在表示进行加权融合得到共识表示, 并采用谱聚类算法对共识表示进行聚类; 最后, 在3个常用数据集上进行了对比实验和消融实验. 实验结果表明, 提出的聚类算法具有良好的聚类效果, 以及提出的多样性信息学习模块可以有效提高算法聚类性能.     

复杂网络社区挖掘——-基于聚类融合的遗传算法

针对当前研究复杂网络社区挖掘的热点问题, 提出了一种基于聚类融合的遗传算法用于复杂网络社区挖掘. 该算法将聚类融合引入到交叉算子中, 利用父个体的聚类信息辅以网络拓扑结构的局部信息产生新个体, 避免了传统交叉算子单纯交换字符块而忽略了聚类内容所带来的问题. 为使聚类融合的作用得以充分发挥, 本文提出了基于马尔科夫随机游走的初始群体生成算法, 使初始群体中的个体具有一定聚类精度并有较强的多样性. 初始群体生成算法与基于聚类融合的交叉算子互相配合, 有效地增强了算法的寻优能力. 此外, 算法将局部搜索机制用于变异算子, 通过迫使变异节点与其多数邻居在同一社区内, 有针对性地缩小了搜索空间, 从而加快了算法收敛速度. 在计算机生成网络和真实世界网络上进行了测试, 并与当前具有代表性的社区挖掘算法进行比较, 实验结果表明了该算法的可行性和有效性.     

基于遗传理论的复杂网络模糊聚类算法

研究基于模糊聚类的遗传算法应用于复杂网络社区挖掘,该算法将聚类融合引入到交叉算子中,利用父个体的聚类信息产生新个体,避免了传统交叉算子单纯交换字符串而忽略聚类内容所带来的问题。该算法采用混沌序列策略进行种群生成,使初始种群中的个体具有一定聚类精度并有较强的多样性,并将局部搜索机制用于变异算子,有效地缩小搜索空间,加快算法收敛速度。该算法与当前具有代表性的社区挖掘算法进行比较,并在仿真网络和现实网络上验证测试,实验结果表明了该算法的可行性和有效性。     

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

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

基于密度的划分式聚类过程参数选择算法

为确定??-means 等聚类算法的初始聚类中心, 首先由样本总量及其取值区间长度确定对应维上的样本密度统计区间数, 并将满足筛选条件的密度峰值所在区间内的样本均值作为候选初始聚类中心; 然后, 根据密度峰值区间在各维上的映射关系建立候选初始聚类中心关系树, 进一步采用最大最小距离算法获得初始聚类中心; 最后为确定最佳聚类数, 基于类内样本密度及类密度建立聚类有效性评估函数. 针对人工数据集及UCI 数据集的实验结果表明了所提出算法的有效性.

     

不确定数据的最优?? 近邻和局部密度聚类算法

传统聚类算法一般针对的是确定数据, 无法解决不确定数据的聚类问题; 现有基于密度的不确定数据聚类算法存在参数敏感且计算率低的问题. 对此, 在引进新的不确定数据相异度函数、最优?? 近邻、局部密度和互包含概念的基础上, 提出解决不确定数据聚类问题的不确定数据的最优?? 近邻和局部密度聚类(OLUC) 算法. 该算法不仅能降低参数敏感性, 提高计算效率, 而且具有动态自适应优化?? 近邻, 快速发现聚类中心和除噪优化的能力. 实验结果表明, 所提出的算法对无论是否存在噪声的不确定数据集都效果良好.

     

基于维度最大熵数据流聚类的异常检测方法

针对传统数据流聚类算法聚类信息损失大、不准确的缺点, 提出一种基于维度最大熵的数据流聚类算法. 采用动态数据直方图将数据维度划分为不同的维度组, 计算各维度最大熵划分维度空间簇, 将相同维度簇的数据聚集成微簇, 通过比较微簇的信息熵大小及其分布特点实现数据流的异常检测. 该方法提升了聚类速度, 克服了传统数据流聚类算法信息丢失的缺点. 实验结果表明, 所提出算法能够提高数据流异常检测的准确性和有效性.

     

无线传感器网络拓扑三级分簇优化算法

针对大规模分布式传感器网络提出一种拓扑三级分簇结构优化算法. 通过引入传感器休眠模式, 并考虑到分簇数目较多的情况, 对多个簇头节点采用生成最小刚性图的方法进行拓扑优化, 以实现传感器网络整体能量均衡,使传感器网络具有较好的连通性和鲁棒性. 仿真实验表明, 与已有相关算法相比, 采用所提出的算法可使网络延缓出现节点死亡现象, 有利于实现网络负载均衡, 并且网络中节点整体存活时间较长, 从而延长网络的生命周期.

     

解决文本聚类集成问题的两个谱算法

聚类集成中的关键问题是如何根据不同的聚类器组合为最终的更好的聚类结果. 本文引入谱聚类思想解决文本聚类集成问题, 然而谱聚类算法需要计算大规模矩阵的特征值分解问题来获得文本的低维嵌入, 并用于后续聚类. 本文首先提出了一个集成算法, 该算法使用代数变换将大规模矩阵的特征值分解问题转化为等价的奇异值分解问题, 并继续转化为规模更小的特征值分解问题; 然后进一步研究了谱聚类算法的特性, 提出了另一个集成算法, 该算法通过求解超边的低维嵌入, 间接得到文本的低维嵌入. 在TREC和Reuters文本数据集上的实验结果表明, 本文提出的两个谱聚类算法比其他基于图划分的集成算法鲁棒, 是解决文本聚类集成问题行之有效的方法.     

基于混合蛙跳与阴影集优化的粗糙模糊聚类算法

针对粗糙模糊聚类算法对初值敏感、易陷入局部最优和聚类性能依赖阈值选择等问题, 提出一种混合蛙跳与阴影集优化的粗糙模糊聚类算法(SFLA-SRFCM). 通过设置自适应调节因子, 以增加混合蛙跳算法的局部搜索能力; 利用类簇上、下近似集的模糊类内紧密度和模糊类间分离度构造新的适应度函数; 采用阴影集自适应获取类簇阈值. 实验结果表明, SFLA-SRFCM 算法是有效的, 并且具有更好的聚类精度和有效性指标.

     

基于矩阵谱分析的文本聚类集成算法

聚类集成技术可有效提高单聚类算法的精度和稳定性,其中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果.文中引入谱聚类算法解决文本聚类集成问题,设计基于正则化拉普拉斯矩阵的谱算法(NLM-SA).该算法基于代数变换,通过求解小规模矩阵的特征值和特征向量间接获得正则化拉普拉斯矩阵的特征向量,并用于后续聚类.进一步研究谱聚类算法的关键思想,设计基于超边转移概率矩阵的谱算法(HTMSA).该算法通过求解超边的低维嵌入间接获得文本的低维嵌入,并用于后续K均值算法.在TREC和Reuters文本集上的实验结果验证NLMSA和HTMSA的有效性,它们都获得比其它基于图划分的集成算法更为优越的结果.HTMSA获得的结果比NLMSA略差,而时间和空间需求则比NLMSA低得多.     

大数据集快速均值漂移谱聚类算法及其在图像分割中的应用

均值漂移谱聚类(MSSC)算法为模式识别聚类任务提供了一种较新的方案.然而由于其内嵌均值漂移过程的时问复杂度与样本容量呈平方关系,其在大数据集环境的实用性受到大大削弱.利用快速压缩集密度估计器(FRSDE)替代Parren窗密度估计式(PW)并融合基于图的松弛聚类(GRC)方法,提出了快速均值漂移谱聚类(FMSSC)算法.相比原MSSC,该算法的总体渐进时间复杂度与样本容量呈线性关系,并具有自适应性和便捷性.     

基于密度调整的改进自适应谱聚类算法

针对谱聚类存在构造相似度矩阵时对尺度参数敏感以及处理多重尺度数据集效果不理想的缺陷, 提出一种基于密度调整的改进自适应谱聚类算法. 该算法将样本点所处领域的密度引入谱聚类, 利用密度差来调整样本点之间的相似度, 使其更符合实际簇类中样本点间的内在关系, 在一定程度上解决了多尺度聚类问题; 同时, 通过样本点的近邻距离自适应得到尺度参数, 使算法对尺度参数相对不敏感. 仿真实验验证了所提出算法的有效性和优越性.

     

基于改进流形距离和人工蜂群的二阶段聚类算法

以改进的流形距离为相似度测度, 结合人工蜂群算法, 提出一种二阶段聚类算法. 首先根据局部密度、最大最小距离和近邻选择对数据集初步归类并得到簇代表点; 然后将聚类归属为优化问题, 通过改进的蜂群算法对簇代表点及没归类的样本点较快地搜索到最优聚类中心, 同时根据流形距离的全局一致性特征, 对样本进行精确的类别划分; 最后将两阶段算法综合归类. 实验结果表明, 所提出的算法可以获得良好的聚类效果.