一种基于空间映射及尺度变换的聚类框架

传统聚类算法通常建立在显式的模型之上,很少考虑泛化模型以适应不同的数据,由此导致了模型不匹配问题。针对此问题,该文提出了一种基于空间映射(Mapping)及尺度变换(Rescaling)的聚类框架(简称M-R框架)。具体而言,M-R框架首先将语料映射到一组具有良好区分度的方向所构建的坐标系中,以统计各个簇的分布特性,然后根据这些分布特性对各个坐标轴进行尺度变换,以归一化语料中各个类簇的分布。如上两步操作伴随算法迭代执行,直至算法收敛。该文将M-R框架应用到K-means算法及谱聚类算法上以验证其性能,在国际标准评测语料上的实验表明,应用了M-R框架的K-means及谱聚类在所有语料集上获得了全面的性能提升。     

基于重新标度的中文短信文本聚类方法

选择一组具有良好区分度的方向构建了CMAS坐标系,又根据初始簇的分布特性,构造出各个坐标轴的重新标度函数以提高聚类决策的有效性。其算法CMAS以迭代的方式收敛得到了最终解。CMAS算法的时间复杂度与K-Means保持在同一量级上。实验结果表明,CMAS算法有较好的聚类质量。     

基于自适应算法的BA网络模型及其聚类分析

BA模型是经典的无标度网络模型,具有一定小世界特性,但聚类系数随着点数增多趋近于零。为进一步优化BA网络模型的平均路径长度和聚类系数的特性,设计了一种基于自适应算法的无标度网络改进模型。改进模型优化了系统与网络节点的关联度,通过计算得到关联度的最优值及此时网络各参数的值,从而获得理想的网络模型。通过对自适应算法中关联度的数学分析,可知系统平均路径长度呈带有条件的收敛状态。仿真结果表明,改进后网络模型在平均路径长度和聚类系数方面,有进一步优化。不同于BA无标度网络的是,改进模型优化后具有较明显的聚类特性,更符合小世界网络特性。     

初始化簇类中心和重构标度函数的文本聚类*

根据文本集的中心和初始簇的中心,选择一组具有良好区分度的方向构建IMIC坐标系,在该坐标系下构造出各坐标轴的重新标度函数用于提高聚类决策的有效性。算法IMIC经过多次迭代,收敛到最终解。IMIC算法的时间复杂度与K-means保持在同一量级上。实验结果表明,IMIC算法有较好的聚类质量。     

改进的OPTICS算法及其在文本聚类中的应用

基于密度的OPTICS聚类算法以可视化的结果输出方式直观呈现语料结构,但由于其结果组织策略在处理稀疏点时的局限性,算法实际性能未能得到充分发挥。本文针对此缺陷提出一种有效的结果重组织策略以辅助稀疏点的重新定位,并针对文本领域的特点改变距离度量方法,形成了OPTICS-Plus文本聚类算法。在真实文本分类语料上的实验表明,我们的结果重组织策略能够辅助算法产生更为清晰反映语料结构的可达图,与K-means算法的比较则证实了OPTICS-Plus具有较为良好的聚类性能。     

一种具有等级结构的无标度网络模型

无标度网络的发现,使人类对于复杂网络的认识进入了一个新的天地.为了更好地描述真实网络的主要拓扑特性,主要研究复杂网络的演化机制,提出了一种通过边的迭代方式生成一种等级网络模型的方法.在此模型的基础上对网络的统计特性进行了理论推导,并通过计算机编程仿真了它的统计特性.理论计算和数值仿真结果可知,迭代生成的网络具有等级结构,度分布服从幂律分布,幂指数在2到3之间可调,平均路径长度以网络规模呈对数形式增长和较大的聚类系数.从而有效地论证了具有等级结构的网络模型很好地符合实际网络,说明实际网络的无标度和高聚类是等级网络自组织的结果.     

基于初始中心迭代收敛的文本聚类方法

利用两三次的K-Means迭代得到初始簇的中心,选择一组具有良好区分度的方向构建IMIC坐标系,在该坐标系下,构造出各坐标轴的重新标度函数用以提高聚类决策的有效性。算法IMIC经过多次迭代,最后收敛到最终解。IMIC算法的时间复杂度与K-Means保持在同一量级上。实验结果表明,IMIC算法有较好的聚类质量。     

基于多模板隐马尔可夫模型的文本信息抽取算法

针对训练数据来源的多样化，提出了基于多模板隐马尔可夫模型的广本信息抽取算法。该算法利用形式的聚类方法将训练数据聚成几个类，每个类代表一个模板，在聚类的基础上利用隐马尔可丈模型进行文本的信息抽取。实验结果表明，新算法具有较高的精确度和召回率。     

聚类算法在无标度网络和云资源管理中的应用

基于最优云资源管理策略,提出了一种构建无标度网络模型的方法。网络建模为一个完全联通图的聚类应用,聚类算法实现了近似理论的度分布。能够重现现实网络权重和节点度呈幂律分布的统计特性,支持自组织,允许单个实体基于本地信息做出决策。实验结果表明,具有自我组织和自我管理属性的无标度网络,其各个核心节点可以作为计算机云的接入点,一旦形成这种集群可以实现最佳的云资源管理政策。     

隐式GPC算法在重介分选过程控制中的研究

为解决重介分选过程中重介质悬浮液密度与液位过程模型失配问题,引入隐式GPC算法对模型参数进行在线辨识,实现对重介质悬浮液的密度与液位解耦控制。仿真结果表明,针对重介分选过程模型具有大滞后、强耦合的这一特性,隐式GPC算法控制效果较好,抗干扰能力强,在模型失配的情况下,仍然保持系统的输出稳定。     

一种采用新型聚类方法的最佳类簇数确定算法

聚类分析是统计学、模式识别和机器学习等领域的研究热点.通过有效的聚类分析,数据集的内在结构与特征可以被很好地发掘出来.然而,无监督学习的特性使得当前已有的聚类方法依旧面临着聚类效果不稳定、无法对多种结构的数据集进行正确聚类等问题.针对这些问题,首先将K-means算法和层次聚类算法的聚类思想相结合,提出了一种混合聚类算法K-means-AHC;其次,采用拐点检测的思想,提出了一个基于平均综合度的新聚类有效性指标DAS（平均综合度之差,difference of average synthesis degree）,以此来评估K-means-AHC算法聚类结果的质量;最后,将K-means-AHC算法和DAS指标相结合,设计了一种寻找数据集最佳类簇数和最优划分的有效方法.实验将K-means-AHC算法用于测试多种结构的数据集,结果表明：该算法在不过多增加时间开销的同时,提高了聚类分析的准确性.与此同时,新的DAS指标在聚类结果的评价上要优于当前已有的常用聚类有效性指标.     

基于图形处理器的数据流快速聚类

在数据流环境下,聚类算法不仅需要有较高的聚类质量,同时需要有实时处理速度.因而,提出了一类基于图形处理器(graphics processing unit,简称GPU)的快速聚类方法,包括基于K-means的基本聚类方法、基于GPU的数据流聚类以及数据流簇进化分析方法.这些方法的共同特点是充分利用了GPU强大的处理能力和流水线特性.与以往具有独立框架的数据流聚类算法不同,这些基于GPU的聚类算法具有同一框架和多种聚类分析功能,为数据流聚类分析提供了统一的平台.从分析可知,数据流聚类分析的核心操作实际上就是距离计算和比较.基于这一认识,利用GPU的子素向量处理功能进行距离计算.性能验证实验是在配有Pentium IV 3.4G CPU和NVIDIA GeForce 6800 GT显卡的PC上进行的.综合分析和实验结果表明,基于GPU的数据流聚类算法比传统的CPU算法平均快7倍,从而为高速数据流应用提供了良好的支持.     

一种基于K-Means局部最优性的高效聚类算法

K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.     

基于成对约束的SubKMeans聚类数确定算法

随着数据维度的增加,传统聚类算法会出现聚类性能差的现象.SubKMeans是一种功能强大的子空间聚类算法,旨在为K-Means类算法搜索出一个最佳子空间,降低高维度影响,但是该算法需要用户事先指定聚类数目K值,而在实际使用中有时无法给出准确的K值.针对这一问题,引入成对约束,将成对约束与轮廓系数进行结合,提出了一种基于成对约束的SubKMeans聚类数确定算法.改进后的轮廓系数能够更加准确的评价聚类性能,从而实现K值确定,实验结果证明该方法的有效性.     

Semi-supervised model-based document clustering: A comparative study

Semi-supervised learning has become an attractive methodology for improving classification models and is often viewed as using unlabeled data to aid supervised learning. However, it can also be viewed as using labeled data to help clustering, namely, semi-supervised clustering. Viewing semi-supervised learning from a clustering angle is useful in practical situations when the set of labels available in labeled data are not complete, i.e., unlabeled data contain new classes that are not present in labeled data. This paper analyzes several multinomial model-based semi-supervised document clustering methods under a principled model-based clustering framework. The framework naturally leads to a deterministic annealing extension of existing semi-supervised clustering approaches. We compare three (slightly) different semi-supervised approaches for clustering documents: Seeded damnl, Constrained damnl, and Feedback-based damnl, where damnl stands for multinomial model-based deterministic annealing algorithm. The first two are extensions of the seeded k-means and constrained k-means algorithms studied by Basu et al. (2002); the last one is motivated by Cohn et al. (2003). Through empirical experiments on text datasets, we show that: (a) deterministic annealing can often significantly improve the performance of semi-supervised clustering; (b) the constrained approach is the best when available labels are complete whereas the feedback-based approach excels when available labels are incomplete. Editor: Andrew Moore     

Scalable Clustering Algorithms with Balancing Constraints

Clustering methods for data-mining problems must be extremely scalable. In addition, several data mining applications demand that the clusters obtained be balanced, i.e., of approximately the same size or importance. In this paper, we propose a general framework for scalable, balanced clustering. The data clustering process is broken down into three steps: sampling of a small representative subset of the points, clustering of the sampled data, and populating the initial clusters with the remaining data followed by refinements. First, we show that a simple uniform sampling from the original data is sufficient to get a representative subset with high probability. While the proposed framework allows a large class of algorithms to be used for clustering the sampled set, we focus on some popular parametric algorithms for ease of exposition. We then present algorithms to populate and refine the clusters. The algorithm for populating the clusters is based on a generalization of the stable marriage problem, whereas the refinement algorithm is a constrained iterative relocation scheme. The complexity of the overall method is O(kN log N) for obtaining k balanced clusters from N data points, which compares favorably with other existing techniques for balanced clustering. In addition to providing balancing guarantees, the clustering performance obtained using the proposed framework is comparable to and often better than the corresponding unconstrained solution. Experimental results on several datasets, including high-dimensional (>20,000) ones, are provided to demonstrate the efficacy of the proposed framework.

一种半监督K均值多关系数据聚类算法

提出了一种半监督K均值多关系数据聚类算法.该算法在K均值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法,以用于多关系数据的半监督学习.为了获取高性能,该算法在聚类过程中充分利用了标记数据、对象属性及各种关系信息.多关系数据库Movie上的实验结果验证了该算法的有效性.     

结合限制的分隔模型及K-Means算法

将数据对象间的关联限制与K-means算法结合可以取得较好的效果,但由于划分是由K个中心决定的,每一类仅由一个中心决定,分隔的表示方法限制了算法效果的进一步提高.基于数据对象间的两类限制,定义了数据对象和集合间的两类关联,以及集合间的3类关联,在此基础上给出了结合限制的分隔模型.在模型中,基于集合间的正关联,多个子集中心可以用来表示同一类,使划分的表示可以更为灵活、精细.基于此模型,给出了相应的算法CKS(constrained K-meanswith subsets)来生成结合限制的分隔.对3个UCI数据集的实验结果显示:在准确率及健壮性上,CKS显著优于另一个结合关联限制的K-means类算法COP-K-means,与另一个代表性的算法CCL相比,也有相当优势;在时间代价上,CKS也有一定优势.     

Spectral clustering with more than K eigenvectors

Spectral clustering techniques are heuristic algorithms aiming to find approximate solutions to difficult graph-cutting problems, usually NP-complete, which are useful to clustering. A fundamental working hypothesis of these techniques is that the optimal partition of K classes can be obtained from the first K eigenvectors of the graph normalized Laplacian matrix L_N if the gap between the K-th and the K+1-th eigenvalue of L_N is sufficiently large. If the gap is small a perturbation may swap the corresponding eigenvectors and the results can be very different from the optimal ones.In this paper we suggest a weaker working hypothesis: the optimal partition of K classes can be obtained from a K-dimensional subspace of the first M>K eigenvectors, where M is a parameter chosen by the user. We show that the validity of this hypothesis can be confirmed by the gap size between the K-th and the M+1-th eigenvalue of L_N. Finally we present and analyse a simple probabilistic algorithm that generalizes current spectral techniques in this extended framework. This algorithm gives results on real world graphs that are close to the state of the art by selecting correct K-dimensional subspaces of the linear span of the first M eigenvectors, robust to small changes of the eigenvalues.