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

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

文本聚类集成问题中的谱算法

聚类集成中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果.引入谱聚类算法解决该问题,提出了基于相似度矩阵的谱算法(SMSA),但该算法高昂的计算代价使其不适合大规模文本集.进一步研究了谱聚类算法的特性,对超边的相似度矩阵进行谱分析.提出了基于超边相似度矩阵的元聚类算法(HSM-MCLA).真实文本数据集的实验结果表明:SMSA和HSM-MCLA比其他基于图划分的集成算法更优越;HSM-MCLA可获得与SMSA相当的结果,而计算需求却明显低于SMSA.     

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

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

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

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

复杂分布数据的半监督阶段聚类

半监督聚类是一种用先验信息完善聚类过程的机器学习方法。通过将元胞自动机(cellular automata,CA)距离变换算法引入到半监督聚类过程中,采用平面距离变换算法将数据集划分为若干子类,获得聚类数和约束信息,并作为下一阶段聚类的先验信息。利用半监督K-means聚类算法对第一阶段的聚类结果做进一步划分,可以获得完整的聚类中心和聚类数,并由此提出CA-K-means二阶段聚类算法。采用3组人工数据集和3组标准UCI数据集进行对比仿真实验,将CA-K-means二阶段聚类算法与半监督K-means聚类算法、遗传Kmeans聚类算法和单纯的CA层次聚类算法进行对比,结果显示,该算法对复杂分布数据的聚类准确率较高,聚类性能更加优良。     

基于投票机制的融合聚类算法

以一趟聚类算法作为划分数据的基本算法,讨论聚类融合问题.通过重复使用一趟聚类算法划分数据,并随机选择阈值和数据输入顺序,得到不同的聚类结果,将这些聚类结果映射为模式间的关联矩阵,在关联矩阵上使用投票机制获得最终的数据划分.在真实数据集和人造数据集上检验了提出的聚类融合算法,并与相关聚类算法进行了对比,实验结果表明,文中提出的算法是有效可行的.     

基于集成学习的改进深度嵌入聚类算法

近年来深度学习的迅速发展为聚类研究提供了一个有力的工具,并衍生出了许多基于深度神经网络的聚类方法.在这些方法中,深度嵌入聚类(DEC)因其可对深度表示学习和聚类分配同时进行优化的优势而日益受到关注.但是,深度嵌入聚类的一个局限性在于其超参数λ的敏感性,而往往需要诉诸人工调节来解决.对此,提出一种基于集成学习的改进深度嵌入聚类(IDECEL)方法.相较于寻求单个最优超参数的常规做法,提出以多样化超参数λ构建一组具有差异性的基聚类,并结合熵理论对基聚类集合的簇不确定性进行评估与加权,进而在簇与样本之间构建一个局部加权二部图模型,再将之高效划分以得到一个更优聚类结果.在多个数据集上的实验结果表明,提出的IDECEL方法不仅可缓解常规DEC算法超参数敏感性的问题,同时也表现出比其他多个深度聚类和集成聚类方法更为鲁棒的聚类性能.     

基于过滤模型的聚类算法

合理的聚类原型是正确聚类的前提.针对现有聚类算法原型选取不合理、计算聚类个数存在偏差等问题,提出基于过滤模型的聚类算法(CA-FM).算法以提出的过滤模型去除干扰聚类过程的边界和噪声对象,依据核心对象之间的近邻关系生成邻接矩阵,通过遍历矩阵计算聚类个数;然后,按密度因子将数据对象排序,从中选出聚类原型;最后,将其余对象按照距高密度对象的最小距离划分到相应的簇中,形成最终聚类.在人工合成数据集、UCI数据集以及人脸识别数据集上的实验结果验证了算法的有效性,与同类算法相比,CA-FM算法具有较高的聚类精度.     

基于残差分析的混合属性数据聚类算法

针对混合属性数据聚类结果精度不高、聚类结果对参数敏感等问题, 提出了基于残差分析的混合属性数据聚类算法(Clustering algorithm for mixed data based on residual analysis) RA-Clust.算法以改进的熵权重混合属性相似性度量对象间的相似性, 以提出的基于KNN和Parzen窗的局部密度计算方法计算每个对象的密度, 通过线性回归和残差分析进行聚类中心预选取, 然后以提出的聚类中心目标优化模型确定真正的聚类中心, 最后将其他数据对象按照距离高密度对象的最小距离划分到相应的簇中, 形成最终聚类.在合成数据集和UCI数据集上的实验结果验证了算法的有效性.与同类算法相比, RA-Clust具有较高的聚类精度.     

基于视图互信息加权的多视图集成聚类算法

现有的多视图聚类算法往往缺乏对各视图可靠度的评估和对视图进行加权的能力,而一些具备视图加权的多视图聚类算法则通常依赖于特定目标函数的迭代优化,其目标函数的适用性及部分敏感超参数调优的合理性均对实际应用有显著影响。针对这些问题,提出一种基于视图互信息加权的多视图集成聚类（MEC-VMIW）算法,主要过程可分为两个阶段,即视图互加权阶段与多视图集成聚类阶段。在视图互信息加权阶段,对数据集进行多次随机降采样,以降低评估加权过程的问题规模,进而构建多视图降采样聚类集合,根据不同视图的聚类结果之间的多轮互评得到视图可靠度评估,并据此对视图进行加权;在多视图集成聚类阶段,对各个视图数据构建基聚类集合,并将多个基聚类集合加权建模至二部图结构,利用高效二部图分割算法得到最终多视图聚类结果。在若干个多视图数据集上的实验结果验证了所提出的多视图集成聚类算法的鲁棒聚类性能。     

基于多层二部图的高光谱模糊聚类算法

针对传统模糊聚类算法对初始聚类中心非常敏感以及对高光谱图像处理效果不佳的问题,为减少聚类数据的复杂度、降低聚类过程的计算成本以提升聚类性能,提出了一种基于多层二部图的高光谱模糊聚类算法。首先使用SuperPCA预处理方法对超像素分割得到的每个同质区域进行PCA来学习HSI数据不同区域的固有低维特征,从而获得高光谱数据的低维表示;其次,构造一个多层二部图矩阵来描述数据点和锚点之间的关系,降低了计算复杂度;最后,在模糊聚类中加入基于多层二部图的非负正则项来约束模糊隶属度矩阵的解空间。在Indian Pines和Pavia University数据集上进行的实验表明,所提算法能提高聚类效果与性能。     

基于k-频繁子图聚类的二分图匿名方法

针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全（c1,c2）-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图（c1,c2）-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。     

Distributed Tip Decomposition on Large Bipartite Graphs

Tip decomposition has a pivotal role in mining cohesive subgraphs in bipartite graphs. It is a popular research topic with wide applications in document clustering, spam group detection, and analysis of affiliation networks. With the explosive growth of the bipartite graph data scale in these scenarios, it is necessary to use distributed methods to realize its effective storage. For this reason, this paper studies the problem of the tip decomposition on a bipartite graph in the distributed environment for the first time. Firstly, a new relay-based communication mode is proposed to realize effective message transmission when the given bipartite graph is decomposed in a distributed environment. Secondly, the Distributed Butterfly Counting (DBC) algorithm and the Distributed Tip Decomposition (DTD) algorithm are designed. In particular, a controllable parallel vertex activation strategy is proposed to solve the problem of memory overflow when DBC decomposes large-scale bipartite graphs. Finally, the message pruning strategy based on vertex priority and message validity pruning strategy are introduced to further improve the efficiency of the algorithm by reducing redundant communication and computing overhead. The experiment is deployed on the high-performance distributed computing platform of the National Supercomputing Center. The effectiveness and efficiency of the proposed algorithms are verified by experiments on several real datasets.     

面向大规模二部图的分布式Tip分解算法

Tip分解作为图数据管理领域的热点研究问题,已被广泛应用于文档聚类和垃圾邮件组检测等实际场景中.随着图数据规模的爆炸式增长,单机内存已无法满足其存储需求,亟需研究分布式环境下Tip分解技术.现有分布式图计算系统的通信模式无法适用于二部图,为此,首先提出一种基于中继的通信模式,以实现分布式环境下处理二部图时消息的有效传递;其次,提出分布式butterfly计数算法(DBC)和tip分解算法(DTD),特别地,为解决处理大规模二部图时DBC面临的内存溢出问题,提出了一种可控的并行顶点激活策略;最后,引入基于顶点优先级的消息剪枝策略和消息有效性剪枝策略,通过减少冗余通信和计算开销,进一步提高算法效率.实验平台部署于国家超算中心高性能分布式集群上,在多个真实数据集上的实验结果验证了所提算法的有效性和高效性.     

基于概念模型的个性化搜索引擎研究

在对用户兴趣模型探讨的基础上,提出了一种基于概念的用户兴趣模型,用于区别用户兴趣的大小.讨论了基于链接的查询聚类算法,并针对该算法的不足提出了一种基于概念的聚类算法,该算法根据用户兴趣模型建立查询-概念二分图,然后计算图中查询顶点间的概念相似度,并将概念相似度最高的查询顶点进行合并以实现聚类.设计实现了一个基于Web数据挖掘的个性化搜索引擎系统,对系统的个性化查询进行了测试,并对比分析了链接聚类和概念聚类的实验结果.     

基于数据流的概念聚类

分析二部图的二元组和概念聚类问题之间的关系，在此基础上结合数据流的特点，提出一种适用于对象属性为布尔型的数据流概念聚类算法。将数据流分段，对每一批到来的数据流，生成局部的近似极大ε二元组集合，对全局的近似极大ε二元组集合进行更新，从而有效地对整个数据流进行聚类。实验结果表明，该算法具有良好的时间效率和空间效率。     

A parallel improvement algorithm for the bipartite subgraph problem

The authors propose the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that the algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the K-partite subgraph problem where no algorithm has been proposed.     

符号图下含扰动的多智能体系统预定时间二分一致性

研究符号图下具有扰动的多智能体系统二分一致性控制问题.考虑了线性系统、非线性不确定系统以及切换拓扑的情况,分别提出相应的预定时间控制器,各控制器可使系统在预定时间内实现二分一致性.通过Lyapunov稳定性理论、代数图论和矩阵分析等验证算法的准确性;仿真对比实验验证了所提算法的可行性和有效性;相较于有限时间控制算法,所提算法的收敛时间不依赖于初始状态,可以通过选择单一时间参数设定系统收敛时间上界;相较于固定时间控制算法,所提算法预设收敛时间与控制算法参数无关,设定简单,具有更低的保守性.     

基于二分图的协作通信中继选择技术*

合理的中继选择对于提升协作通信系统的能效具有重要意义。针对多用户多中继协作通信系统,为获得较高的系统能效并降低系统的复杂度,提出了基于二分图的中继选择策略,将协作通信系统中继选择问题转化为带权二分图的最大匹配问题。首先将用户节点与待选择的中继节点建模为二分图的顶点,根据中继的协作范围确定二分图的边集,然后将不同的协作组合所产生的能效给各边赋权,最后通过KM算法求解该带权二分图的最大匹配。仿真结果表明,相比于其它中继选择算法,该策略能够有效提高系统能效,同时具有低复杂度的优点。