基于超图的稀疏属性选择算法*

针对噪声或者离群点通常会增加矩阵的秩的问题,提出一个在低秩限制下的基于超图的稀疏属性选择算法。具体地,该算法首先利用其他属性稀疏地表达每一个属性来获得属性自表达系数矩阵。然后,利用超图正则化因子获取数据的局部结构将子空间学习嵌入到属性选择的框架中。同时,利用范数惩罚自表达系数矩阵和损失函数,挖掘出属性之间的关系和样本间的关系来帮助算法有效地进行属性选择,最终提高模型的预测能力。在UCI数据集上的实验结果表明,该算法相比其它对比算法,能更有效地选取重要属性,并取得很好的分类效果。     

基于属性自表达的低秩超图属性选择算法*

针对高维数据具有低秩形式和属性冗余等特点,提出一种基于属性自表达的无监督超图属性选择算法。具体地,该算法首先利用属性自表达特点用其他属性稀疏地表达每个属性,此自表达形式使用低秩假设寻找高维数据的低秩表示,然后建立超图正则化因子保持高维数据的局部结构,最后利用稀疏正则化因子进行属性选择。属性自表达特性确定属性的重要性,低秩表示相当于考虑数据的全局信息进行子空间学习,超图正则化因子考虑数据的局部结构对数据进行子空间学习。该算法实际上考虑数据全局和局部信息进行子空间学习,更是一种嵌入了子空间学习的属性选择算法。实验结果表明,该算法相比其它对比算法,能更有效地选取属性,并能取得很好的分类效果。     

基于聚类系数的推荐算法*

摘 要：针对于标准二分图网络推荐算法（NBI）的物质扩散机制过于简单的问题,基于聚类系数的改进NBI算法（简称NBICC）被提出。在文章中,推荐系统可以被抽象为一个有向加权二分图网络。在物质扩散的过程中,考虑到聚类系数因素的影响,重新定义了商品之间的相似度的计算公式,进而获得了更加精确的推荐结果。Ranking score,precison,recall等评价指标被应用在本文提出的新算法中,实验结果表明,这三样重要指标上,NBICC算法都强于标准NBI算法。     

基于谱聚类与多因子融合的协同过滤推荐算法*

针对传统协同过滤算法面临数据稀疏、忽略用户时间上下文信息及对兴趣物品偏好程度等问题,本文提出基于谱聚类与多因子融合的协同过滤推荐算法。首先将FCM聚类融入到谱聚类算法的关键步骤,并通过聚类有效性指数对用户聚类个数进行优化,以降低生成最近邻的时耗;然后将Salton因子、时间衰减因子、用户偏好因子进行融合,从而对相似度进行改进;最后获取系统当前时间为目标用户生成推荐列表。Movielens上的实验结果表明,本文提出的算法在推荐精度、覆盖率及新颖度指标上有较大改善,提升了推荐性能。     

基于超图切割的半监督学习和聚类算法

本文针对超图切割上的半监督学习和聚类算法进行了研究;首先,通过对超图切割和超边展开法及其切割函数的讨论,引入了超图上的总变异作为超图切割的洛瓦兹扩展,并在此基础上提出了一组正则化函数,它对应于图上的拉普拉斯型正则化;然后,基于正则化函数族提出了半监督学习方法,并基于平衡超图切割提出了谱聚类方法;为了求解这两个学习问题,将它们转化为求解凸优化问题,并为此提出了一种主要组成部分为近端映射的可扩展算法,从而实现半监督学习和聚类;仿真实验结果表明,本文提出的基于超图切割实现的半监督学习和聚类方法相比于经典的超边展开法和其他图切割方法有更好的标准偏差和聚类误差性能。     

基于无向超图的多蚁群聚类组合算法

介绍了一种基于无向超图的多蚁群聚类组合算法,该算法将单蚁群聚类算法的结果聚类组合成多蚁群聚类算法,用无向超图表示,结合超图划分算法Hmetis得到最终的聚类结果。文中给出了实验数据集和实验结果,证明该算法可以提高聚类效果并且减少孤立点。     

基于聚类SURF特征的商品识别算法*

图像存在遮挡、尺度缩放、多干扰时,传统加速鲁棒特征(SURF)算法会产生错误匹配问题,提出一种基于匹配角度聚类的匹配算法。算法先提取SURF特征点,利用特征点的主方向信息进行图像角度矫正,再统计并聚类粗匹配对的匹配角度信息,依据类中元素数目和类簇数目进行两级筛选,剔除异常角度信息的误匹配对。本文算法与随机抽样一致性算法(RANSAC)进行实验对比,表明该算法能有效提高匹配正确率和保证低误剔除率,提高了商品图像的识别率。     

基于谱聚类的聚类集成算法

谱聚类是近年来出现的一类性能优越的聚类算法,能对任意形状的数据进行聚类, 但算法对尺度参数比较敏感,利用聚类集成良好的鲁棒性和泛化能力,本文提出了基于谱聚类的聚类集成算法.该算法首先利用谱聚类算法的内在特性构造多样性的聚类成员; 然后,采用连接三元组算法计算相似度矩阵,扩充了数据点之间的相似性信息;最后,对相似度矩阵使用谱聚类算法得到最终的集成结果. 为了使算法能扩展到大规模应用,利用Nystrm采样算法只计算随机采样数据点之间以及随机采样数据点与剩余数据点之间的相似度矩阵,从而有效降低了算法的计算复杂度. 本文算法既利用了谱聚类算法的优越性能,同时又避免了精确选择尺度参数的问题.实验结果表明:较之其他常见的聚类集成算法,本文算法更优越、更有效,能较好地解决数据聚类、图像分割等问题.     

基于超图的关联规则可视化方法*

针对传统的关联规则可视化方法缺乏多模式关联规则展现形式、无法展示关联规则的内部信息以及分布情况、属性值重要程度突出不明显等问题,提出了基于超图的关联规则表示方法。首先,基于超图中BF-超边基础理论,给出了BF规则图的定义,并且设计了基于超图的一对一、一对多、多对一、多对多关联规则表示原型;接着,结合“沙漏”结构,设计了基于超图的关联规则可视化布局算法;然后,基于交互理论及其相关技术,设计并实现了交互式关联规则可视化系统。最后,以某省全员人口数据为基础,对算法进行了具体实现和分析。实验结果表明,所提出的可视化形式和已有成果相比具有良好的展现效果。     

基于图收缩的半监督聚类算法

为了在只有少量已知标记的数据集中获得较好的聚类效果,提出了一种基于图收缩的半监督聚类算法。首先将整个样本空间中的数据表达为一个带权图,再根据给出的must-link约束,对图进行边收缩的修改,进而增强must-link约束。在此基础上引入图拉普拉斯算子,结合cannot-link约束将样本空间投影到一个特征子空间。最后在子空间上进行聚类分析。实验结果表明,该方法不仅提高了对复杂数据的聚类结果,而且在约束对数量较少时也能获得较好的结果。     

谱聚类算法对输入数据顺序的敏感性*

结合矩阵分析知识,还原了实施谱聚类算法过程中的矩阵表示.发现了不同数据输入顺序使得相应的Affinity矩阵及Laplacian矩阵是相似的.这样,Laplacian矩阵的特征向量生成的矩阵Y也是相似的;而以Y的行向量作为输入数据的K-平均算法依赖于初始的k个对象的选择.由此给出了导致谱聚类算法对数据输入顺序敏感的原因.     

Hypergraph Models and Algorithms for Data-Pattern-Based Clustering

In traditional approaches for clustering market basket type data, relations among transactions are modeled according to the items occurring in these transactions. However, an individual item might induce different relations in different contexts. Since such contexts might be captured by interesting patterns in the overall data, we represent each transaction as a set of patterns through modifying the conventional pattern semantics. By clustering the patterns in the dataset, we infer a clustering of the transactions represented this way. For this, we propose a novel hypergraph model to represent the relations among the patterns. Instead of a local measure that depends only on common items among patterns, we propose a global measure that is based on the cooccurences of these patterns in the overall data. The success of existing hypergraph partitioning based algorithms in other domains depends on sparsity of the hypergraph and explicit objective metrics. For this, we propose a two-phase clustering approach for the above hypergraph, which is expected to be dense. In the first phase, the vertices of the hypergraph are merged in a multilevel algorithm to obtain large number of high quality clusters. Here, we propose new quality metrics for merging decisions in hypergraph clustering specifically for this domain. In order to enable the use of existing metrics in the second phase, we introduce a vertex-to-cluster affinity concept to devise a method for constructing a sparse hypergraph based on the obtained clustering. The experiments we have performed show the effectiveness of the proposed framework.     

基于谱结构融合的多视图聚类

多视图聚类需要将多个视图的数据信息进行融合表示,是一项重要且具有挑战的任务.至今仍存在2个难解的问题：1)如何将多视图信息有效融合,减少信息丢失;2)如何将图学习和谱聚类同时进行,避免2步策略带来次优化结果.由于数据本身存在噪声并且各视图数据差异较大,在数据空间进行融合可能会造成重要信息的损失;另外,考虑到不同视图的数据应具有相同的聚类结构.为此提出基于谱结构融合的多视图聚类模型,将各视图信息在谱嵌入阶段实施融合,一方面避免了噪声和各视图数据差异的影响,另一方面融合的部位和方式更自然,减少了融合阶段信息的丢失.另外,该模型利用子空间自表示进行图学习,有效地将图学习和谱聚类整合到统一框架中进行联合优化学习.在5个真实数据集上的实验表明了模型的有效性和优越性.     

基于稀疏重构的超图谱聚类方法

超图谱聚类方法由于能很好地描述数据点间的高阶信息,近年来受到了广泛的关注。不同于传统图结构,超图结构中的超边不是两两数据点间的连接,而是一组具有某种相同特性的数据子集。在实际应用中,常用K-近邻来构建超图中的超边,因此,并没有考虑到数据内在的关联性。提出一种新的基于稀疏重构的超图构建方法。对每一样本,用稀疏表示来找到与其最有关联的近邻样本,以此形成基于稀疏重构的超图模型,使得每个超边内的样本都具有很强的关联性。最后通过对超图拉普拉斯矩阵进行谱分解得到聚类结果。在人脸数据库、手写体数据库上的实验结果验证了算法的有效性。     

网格资源超图划分聚类任务调度

网格计算是当前一个活跃的研究领域,其中任务调度是实现网格计算目标的一个重要部分.为获得良好的网格任务调度性能,提出了一种基于资源超图划分聚类的网格任务调度算法RHPC.该算法根据网格环境下资源数量庞大、异构、多样的特点,在构建的网格资源超图模型基础上,预先对资源进行性能划分聚类,将任务与聚类资源相匹配并实施调度.模拟实验结果证明算法缩短了任务资源相匹配的时间,提高了任务调度的性能,是一种有效的网格任务调度算法.     

一种改进的谱聚类方法及其在文本分析中的应用

随着文本资源的激增,特别是网页文本的迅速增加,针对文本的挖掘分析日益受到重视。谱聚类是文本聚类分析较常用的一种新型方法。该文将非负约束引入到传统的谱聚类算法中,提出了一种基于非负约束的谱聚类方法。文中实验验证了所提出方法在中文文本聚类分析应用中的有效性。     

基于局部协方差矩阵的谱聚类算法

针对传统谱聚类算法没有解决簇划分过程中,簇间交叉区域样本点对聚类效果有影响这个问题,提出一种基于局部协方差矩阵的谱聚类算法,主要介绍了一种新的计算样本之间相似度亲和矩阵的方法,即通过计算样本点之间的欧氏距离划分出小子集,计算小子集的协方差,通过设定阈值剔除交叉点,由剩下的点构造相似矩阵,对相似矩阵进行特征值分解,用经典的[k]-means算法对由特征向量组成的矩阵聚类。通过在Control等真实数据集上的实验结果表明,该算法在聚类准确率、标准互信息等指标上比较对比算法获得更优秀的效果。     

基于消息传递的谱聚类算法

谱聚类将数据聚类问题转化成图划分问题,通过寻找最优的子图,对数据点进行聚类。谱聚类的关键是构造合适的相似矩阵,将数据集的内在结构真实地描述出来。针对传统的谱聚类算法采用高斯核函数来构造相似矩阵时对尺度参数的选择很敏感,而且在聚类阶段需要随机确定初始的聚类中心,聚类性能也不稳定等问题,本文提出了基于消息传递的谱聚类算法。该算法采用密度自适应的相似性度量方法,可以更好地描述数据点之间的关系,然后利用近邻传播（Affinity propagation,AP）聚类中“消息传递”机制获得高质量的聚类中心,提高了谱聚类算法的性能。实验表明,新算法可以有效地处理多尺度数据集的聚类问题,其聚类性能非常稳定,聚类质量也优于传统的谱聚类算法和k-means算法。     

谱聚类算法研究综述

聚类分析是一种常见的分析方法,谱聚类作为聚类分析的一支,因其不受样本形状约束等特点备受瞩目。为及时掌握当前谱聚类算法研究动态,通过对比分析众多谱聚类优化算法,从半监督学习、二阶段聚类算法选择、算法执行效率优化等三个角度,将谱聚类优化算法分为三类,并对每类算法的优化思想进行综述。介绍经典多路谱聚类与基本理论,并分析相似矩阵及其特征值、特征向量选取原因及影响,旨在明确特征矩阵的重要性与优化的必要性。基于算法改进策略差异,梳理并总结每类算法的改进思想、研究现状及优缺点。在UCI数据集与手写体数据集上,针对谱聚类算法与优化算法进行实验对比,并对谱聚类优化算法的未来研究方向进行展望。     

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

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