基于聚类的复杂网络社团发现算法

对基于聚类技术的复杂网络社团发现算法进行研究,分析网络中结点间的相似性度量方法,提出把复杂网络中的结点转化为向量的顶点到向量映射(MVV)算法,把网络中的结点转化成适合聚类算法的数据结构形式.对不同聚类算法及相似性度量方法的性能进行比较分析,结果表明,MVV算法可以提高发现复杂网络中社团的能力.     

改进的蚂蚁聚类算法*

提出了一种改进的基于对称点距离的蚂蚁聚类算法。该算法不再采用Euclidean距离来计算类内对象的相似性,而是使用新的对称点距离来计算相似性,在处理带有对称性质的数据集时,可以有效地识别给定数据集的聚类数目和合适的划分。在该算法中,用人工蚂蚁代表数据对象,根据算法给定的聚类规则来寻找最合适的聚类划分。最后用本算法与标准的蚂蚁聚类算法分别对不同的数据集进行了聚类实验。实验结果证实了算法的有效性。     

基于距离度量学习的集成谱聚类

无监督学习聚类算法的性能依赖于用户在输入数据集上指定的距离度量,该距离度量直接影响数据样本之间的相似性计算,因此,不同的距离度量往往对数据集的聚类结果具有重要的影响。针对谱聚类算法中距离度量的选取问题,提出一种基于边信息距离度量学习的谱聚类算法。该算法利用数据集本身蕴涵的边信息,即在数据集中抽样产生的若干数据样本之间是否具有相似性的信息,进行距离度量学习,将学习所得的距离度量准则应用于谱聚类算法的相似度计算函数,并据此构造相似度矩阵。通过在UCI标准数据集上的实验进行分析,结果表明,与标准谱聚类算法相比,该算法的预测精度得到明显提高。     

基于半监督自动谱聚类算法的网络故障检测

针对网络故障检测中利用先验知识不足和多数谱聚类算法需事先确定聚类数的问题,提出一种新的基于成对约束信息传播与自动确定聚类数相结合的半监督自动谱聚类算法。通过学习一种新的相似性测度函数来满足约束条件,改进NJW聚类算法,对非规范化的Laplacian矩阵特征向量进行自动谱聚类,从而提高聚类性能。在UCI标准数据集和网络实测数据上的实验表明,该算法较相关比对算法聚类准确率更高,可满足网络故障检测的实际需要。     

一种基于流形距离核的谱聚类算法

针对标准谱聚类算法中,基于欧氏距离的相似性度量不能完全反映数据聚类复杂的空间分布特性的问题,提出了一种基于流形距离核的谱聚类算法.它能充分挖掘数据集中的内在结构信息,较好地反映局部和全局一致性,并且可以很好地防止"桥"噪声点的影响,提高算法的聚类性能.与传统的聚类算法和常见谱聚类算法进行了比较,在人工数据集和UCI数据集上的实验都验证了本算法能够获得更好的聚类效果.     

一种基于聚类集成技术的混合型数据聚类算法

提出了一种基于集成技术和谱聚类技术的混合数据聚类算法CBEST。它利用聚类集成技术产生混合数据间的相似性,这种相似性度量没有对数据特征值分布模型做任何的假设。基于此相似性度量得到的待聚类数据的相似性矩阵,应用谱聚类算法得到混合数据聚类结果。大量真实和人工数据上的实验结果验证了CBEST的有效性和它对噪声的鲁棒性。与其它混合数据聚类算法的比较研究也证明了CBEST的优越性能。CBEST还能有效融合先验知识,通过参数的调节来设置不同属性在聚类中的权重。     

一种基于约束的中垂面相似度准则

在数据挖掘和机器学习的基于距离的各种技术中,例如基于距离的聚类和基于距离的分类,如何度量数据间的相似性已经成为一项基础任务.对于某一具体问题,采用合适的相似性度量,会使问题得到更有效的解决.越来越多的研究表明,通过对成对约束(正约束和负约束)的充分利用,从而得到与问题相匹配的相似性度量,能够大幅度地提升算法性能.目前基于约束的相似性度量研究主要是基于约束的距离度量学习,通过对约束信息的利用,学习一个距离度量矩阵,然后再进行分类或者聚类.通过对成对约束尤其是负约束的挖掘,提出一种基于成对约束的相似性度量准则,然后将此准则应用于聚类和分类任务中,分别提出聚类和分类算法,最后在大量标准数据集上将这些算法的性能与目前流行的算法进行实验比较,并据此得出了一些经验性的启示.     

权吸引子传播算法及其在文本聚类中的应用

吸引子传播算法(affinity propagation, AP)是一种新的高效聚类算法.由于AP算法简单易用,它已被广泛应用到数据挖掘的各个领域.在AP算法中,相似性度量具有重要作用.另一方面,传统的文本挖掘常采用向量空间模型和满足欧氏空间的相似性度量.这种方法的优点是简单且易于实现,但随着数据规模的膨胀,向量空间将变得高维稀疏并将导致计算复杂度快速增长.为解决此问题,给出了相似特征集、排斥特征集和仲裁特征集的概念,在这些概念的基础上提出了一种能够包含文本结构信息的非欧空间相似性度量方法.并提出了一种新的聚类算法,称之为权吸引子传播算法(weight affinity propagation, WAP).为检验提出算法的聚类效果,选用标准数据集Reuters-21578进行了验证.实验结果表明WAP明显优于k-means聚类算法、具备非线性特征的SOFM聚类算法和采用经典相似性度量的吸引子传播算法等3种经典聚类算法.     

一种具有方向特点的网络对象聚类算法

对分别采用欧氏距离和网络距离作为相似性测度的聚类方法进行分析,并从空间网络中对象间着手,提出一种具有方向特点的网络对象聚类算法.算法利用空间网络的邻接关系,将两种距离结合起来作为聚类的相似性测度以提高聚类的精度.算法分析和实验证明,该算法的聚类效果优于单一度量的聚类方法.     

基于流形结构的多聚类中心近邻传播聚类算法

多聚类中心近邻传播聚类算法（MEAP）,在处理任意形状具有流形分布结构的数据时,往往得不到理想的聚类结果。为此,基于流形学习的思想,设计了一种全新的相似性度量,该相似性度量能够扩大位于同一流形中数据点间的相似性,同时缩小处于不同流形上数据点间的相似性,从而使得相似性矩阵能够准确地反映数据集内在的流形分布结构。将该相似性度量与MEAP相结合,提出基于流形结构的多聚类中心近邻传播聚类算法MS-MEAP（Manifold Structure based Multi-Exemplar Affinity Propagation）,从而有效地拓展了算法处理任意形状具有流形分布结构数据集的能力,同时提高了算法的运行效率。在人工数据集与USPS手写体数据集上进行了实验,仿真实验结果及算法有效性分析证明,MS-MEAP算法相比于原算法在处理任意形状具有流形分布结构的数据时,具有更好的聚类性能。     

高维数据的增量式聚类算法的距离度量选择研究

合适的距离度量函数对于聚类结果有重要的影响。针对大规模高维数据集,使用增量式聚类算法进行距离度量的选择分析。SpFCM算法是将大规模数据集分成小样本进行增量分批聚类,可在有限的计算机内存中获得较好的聚类结果。在传统的SpFCM算法的基础上,使用不同的距离度量函数来衡量样本之间的相似性,以得出不同的距离度量对SpFCM算法的影响。在不同的大规模高维数据集中,使用欧氏距离、余弦距离、相关系数距离和扩展的杰卡德距离来计算距离。实验结果表明,后3个距离度量相对于欧氏距离可以很大程度地提高聚类效果,其中相关系数距离可以得到较好的结果,余弦距离和扩展的杰卡德距离效果比较一般。     

基于改进Hausdorff距离的轨迹聚类算法

以整条轨迹为目标的聚类方法存在轨迹较长的问题。为此,提出一种以轨迹子段为聚类目标的聚类算法CTIHD。给出一种新的轨迹子段距离度量方法,用以消除轨迹子段之间的公共偏差。利用特征点概念将轨迹划分成轨迹子段集,计算轨迹子段之间的相似度,由此实现聚类。实验结果表明,该算法相比同类算法具有更好的轨迹聚类效果。     

一种融合变异系数的k-mean聚类分析方法

K-means聚类算法的性能依赖于距离度量的选择,k-means算法将欧几里德距离作为最常用的距离度量方法。欧氏距离认为所有属性在聚类中作用是相同的,但是这种距离度量方法并不能准确反映样本间的相异性。针对这种不足,提出了融合变异系数的k-means聚类分析方法（CV-k-means）,利用变异系数权重向量来减少不相关属性的影响。实验结果表明,该方法的聚类结果优于k-means算法。     

一种基于DBSCAN算法的代码包层次重构改进方法

在包层次的代码重构研究中,为了得到"高内聚、低耦合"的软件结构,层次聚类算法因其简单有效、聚类精度高等特点被认为是一种较好的软件聚类方法.但是,层次聚类算法时间复杂度高,不利于处理较大规模的软件.而基于密度聚类的DBSCAN算法则与之相反,具有较快的聚类速度,但是精度却较低.因此,提出一种基于DBSCAN的软件层次聚类...     

Task assignment in heterogeneous computing systems

The problem of task assignment in heterogeneous computing systems has been studied for many years with many variations. We consider the version in which communicating tasks are to be assigned to heterogeneous processors with identical communication links to minimize the sum of the total execution and communication costs. Our contributions are three fold: a task clustering method which takes the execution times of the tasks into account; two metrics to determine the order in which tasks are assigned to the processors; a refinement heuristic which improves a given assignment. We use these three methods to obtain a family of task assignment algorithms including multilevel ones that apply clustering and refinement heuristics repeatedly. We have implemented eight existing algorithms to test the proposed methods. Our refinement algorithm improves the solutions of the existing algorithms by up to 15% and the proposed algorithms obtain better solutions than these refined solutions.     

文本聚类技术的有效性验证

讨论了利用分类测试集进行聚类量化评价的标准。在此基础上选择k-Means聚类算法、STC（后缀树聚类）算法和基于Ant的聚类算法进行了实验对比。实验表明，STC聚类算法在处理文本时充分考虑了文本的特性，其聚类效果较好；基于Ant的聚类算法在聚类的划分时效果受参数输入的影响较大，其聚类结果与STC相比并不具有优势；在Ant聚类算法中引入文本特性后，可以提高文本聚类的效果。     

三种谱聚类算法及其应用研究

聚类分析是数据挖掘领域中一个重要研究内容,谱聚类(Spectral Clustering, SC)由于具有计算简便,性能优越等特点,已经成为最流行的聚类算法之一。本文利用四类几何结构数据,对规范化割(Normalized Cut, NCUT)、稀疏子空间聚类(Sparse subspace clustering, SSC)和谱曲率聚类(Spectral Curvature Clustering, SCC)三种谱聚类算法进行了分析和比较。实验结果表明,针对本文实验数据三种算法的聚类结果各有差异,但每类数据都可以找到相对最有效的聚类算法,方便读者对算法的选择和使用。NCUT无法处理相交的数据,适用性较差,但对于不相交的二次曲线聚类精度较高,并且优于SSC和SCC算法;相比NCUT算法,SSC算法适用性较强,能够实现四类几何结构数据的聚类,但在聚类过程中常出现误分现象,导致聚类精度不高;与前两种算法相比,SCC算法具有适用性强,精度高等特点,能够实现四类几何结构数据有效聚类,尤其对于实验数据中“横”和“竖”两类点组成的十字,SCC算法能够得到较好的聚类结果,解决由于数据量大SSC算法无法处理的问题。此外,针对有数据间断的两条相交螺旋线聚类问题,本文在现有SCC算法基础上进行改进,结果表明,改进后算法能够有效地实现数据聚类,具有良好的实用性。最后,文章分析了现有SCC算法存在的不足,并指出进一步研究的方向。     

SCALE: a scalable framework for efficiently clustering transactional data

This paper presents SCALE, a fully automated transactional clustering framework. The SCALE design highlights three unique features. First, we introduce the concept of Weighted Coverage Density as a categorical similarity measure for efficient clustering of transactional datasets. The concept of weighted coverage density is intuitive and it allows the weight of each item in a cluster to be changed dynamically according to the occurrences of items. Second, we develop the weighted coverage density measure based clustering algorithm, a fast, memory-efficient, and scalable clustering algorithm for analyzing transactional data. Third, we introduce two clustering validation metrics and show that these domain specific clustering evaluation metrics are critical to capture the transactional semantics in clustering analysis. Our SCALE framework combines the weighted coverage density measure for clustering over a sample dataset with self-configuring methods. These self-configuring methods can automatically tune the two important parameters of our clustering algorithms: (1) the candidates of the best number K of clusters; and (2) the application of two domain-specific cluster validity measures to find the best result from the set of clustering results. We have conducted extensive experimental evaluation using both synthetic and real datasets and our results show that the weighted coverage density approach powered by the SCALE framework can efficiently generate high quality clustering results in a fully automated manner.     

面向多视图聚类的低秩张量表示学习

针对现有鲁棒图学习忽略多视图间的互补信息和高阶相关性问题,提出一种面向多视图聚类的低秩张量表示学习（LRTRL-MVC）算法。利用鲁棒主成分分析的思想,在去除噪声的干净数据上计算各视图的鲁棒图和转移概率矩阵,然后构建一个包含各视图马尔可夫转移概率矩阵的张量,采用基于张量奇异值分解的核范数来确保目标张量的低秩性质。利用迭代最优化算法求解,将求得的低秩张量作为马尔可夫谱聚类算法的输入得到最终聚类结果。在4个不同类型的公开标准数据集BBCSport、NGs、Yale和MSRCv1上进行实验并与相关的最好多视图聚类算法进行对比,结果表明在3个聚类度量标准下,所提算法的聚类结果均高于其他对比算法。     

基于密度的聚类中心自动确定的混合属性数据聚类算法研究

面对广泛存在的混合属性数据,现有大部分混合属性聚类算法普遍存在聚类 质量低、聚类算法参数依赖性大、聚类类别个数和聚类中心无法准确自动确定等问题,针对 这些问题本文提出了一种基于密度的聚类中心自动确定的混合属性数据 聚类算法.该算法通过分析混合属性数据特征,将混合属性数据分为数 值占优、分类占优和均衡型混合属性数据三类,分析不同情况的特征选取 相应的距离度量方式.在计算数据集各个点的密度和距离分布图基础 上,深入分析获得规律: 高密度且与比它更高密度的数据点有较大距离的数 据点最可能成为聚类中心,通过线性回归模型和残差分析确定奇异 点,理论论证这些奇异点即为聚类中心,从而实现了自动确定聚类中心.采 用粒子群算法(Particle swarm optimization, PSO)寻找最优dc值,通过参数dc能够计算得到 任意数据对象的密度和到比它密度更高的点的最小距离,根据聚类 中心自动确定方法确定每个簇中心,并将其他点按到最近邻的更高 密度对象的最小距离划分到相应的簇中,从而实现聚类.最终将本文 提出算法与其他现有的多种混合属性聚类算法在多个数据集上进行 算法性能比较,验证本文提出算法具有较高的聚类质量.