基于数据集压缩的聚类算法性能优化研究

针对目前聚类算法对大数据集的聚类分析中存在时间花费过大的问题,提出了一种基于最近邻相似性的数据集压缩算法。通过将若干个相似性最近邻的数据点划分成一个数据簇并随机选择簇头构成新的数据集,大大缩减了数据的规模。然后分别采用k-means算法和AP算法对压缩后的数据集进行聚类分析。实验结果表明,压缩后的数据集与原始数据集的聚类分析相比,在保证聚类准确率基本一致的前提下有效降低了聚类的花费时长,提高了算法的聚类性能,证明该数据集压缩算法在聚类分析中的有效性与可靠性。     

一种基于数据垂直划分的分布式密度聚类算法

聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDBSCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.     

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

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

基于向量内积不等式的分布式k均值聚类算法

聚类分析是数据挖掘领域的一项重要研究课题．随着数据量的急剧增加,针对大数据集的聚类分析成为一个难点．虽然k均值算法具有易实现、复杂度与数据集大小成线性关系的优点,将其应用于大数据集时仍然存在效率低的问题．分布式聚类是解决这一问题的有效方法．在已有分布式聚类算法k—DMeans基础上,结合向量内积不等式关系对算法加以优化,提出分布式聚类算法k—DCBIP．理论分析和实验结果表明,算法k—DCBIP优于k-DMeans,可以有效地解决大数据集聚类问题,算法是有效可行的．     

聚类算法研究

对近年来聚类算法的研究现状与新进展进行归纳总结.一方面对近年来提出的较有代表性的聚类算法,从算法思想、关键技术和优缺点等方面进行分析概括;另一方面选择一些典型的聚类算法和一些知名的数据集,主要从正确率和运行效率两个方面进行模拟实验,并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析.最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题.上述工作将为聚类分析和数据挖掘等研究提供有益的参考.     

一个高效的多变量时间序列聚类算法

时间序列聚类分析是数据挖掘研究的一个重要内容。已有的聚类算法大多采用k均值对低维数据进行聚类,不能对高维多变量时间序列（MTS）数据进行有效聚类。提出一种高效的多变量时间序列聚类算法PCA-CLUSTER,首先利用主成分分析对MTS数据降维;选取MTS数据的主成分序列进行K近邻聚类分析。理论分析和实验结果表明算法可以有效解决MTS数据聚类问题。     

一种基于符号关系图的快速符号数据聚类算法

由于在实际应用中有大量的符号数据生成,符号数据聚类成为了聚类分析的一个重要研究领域。目前,已有许多符号数据聚类算法被提出,但将它们应用于大数据环境时,仍然存在计算成本高、运行速度慢等问题。文中提出了一种基于符号关系图的快速符号数据聚类算法。该算法使用符号关系图替代原始数据,缩小数据集的规模,有效地解决了这一问题。大量的实验分析显示新算法相比其他算法是有效的。     

具有加权特性的弹性网络聚类算法研究

聚类分析是数据挖掘中重要内容之一,也是人们分析数据的重要工具。针对聚类分析中存在易受噪声干扰、高维数据聚类结果不佳等问题,对弹性网络进行了加权聚类方向的研究。该算法考虑到数据集中各特征属性在聚类过程中不同的重要程度,重新构造关联数据点、聚类中心点的能量函数,利用弹性网络算法的求解模式,结合极大熵原理、模拟退火思想,提出一种具有加权特性的弹性网络聚类算法。该算法无需人工指导训练,便可以自学习地求解出高质量的聚类结果。通过不同维度、不同数量级的随机数据集和UCI真实数据集仿真实验,验证了算法的有效性和稳定性。相较于传统聚类算法,该算法显著提高了聚类质量。     

高维数据流聚类及其演化分析研究

基于数据流数据的聚类分析算法已成为研究的热点．提出一种基于子空间的高维数据流聚类及演化分析算法CAStream，该算法对数据空间进行网格化，采用近似的方法记录网格单元的统计信息，并将潜在密集网格单元快照以改进的金字塔时间结构进行存储，最后采用深度优先搜索方法进行聚类及其演化分析．CAStream能够有效处理高雏数据流，并能发现任意形状分布的聚类．基于真实数据集与仿真数据集的实验表明，算法具有良好的适用性和有效性．     

有效距离在聚类算法中的应用

聚类分析是数据挖掘领域的重要组成部分之一,而度量学习是聚类分析中的关键性步骤。传统聚类算法中通常使用欧氏距离进行距离度量,但是欧氏距离只关注两两样本之间的距离关系,并没有顾及数据的全局性分布结构。考虑到数据的全局性结构信息,提出了一种新的具有全局性的度量方法——有效距离度量(effective distance metric),其主要思想是通过稀疏重构的方法计算数据样本之间的有效距离。进一步地,将有效距离应用到K-means、K-medoids和FCM(fuzzy C-means)3种经典聚类算法中开发了3种基于有效距离的聚类算法,即EK-means,EK-medoids和EFCM聚类算法。通过与传统聚类算法在UCI标准数据集上的实验结果进行比较,验证了基于有效距离的聚类算法能显著提高聚类效果。     

Adaptive partial graph learning and fusion for incomplete multi-view clustering

Most of existing multi-view clustering methods assume that different feature views of data are fully observed. However, it is common that only portions of data features can be obtained in many practical applications. The presence of incomplete feature views hinders the performance of the conventional multi-view clustering methods to a large extent. Recently proposed incomplete multi-view clustering methods often focus on directly learning a common representation or a consensus affinity similarity graph from available feature views while ignore the valuable information hidden in the missing views. In this study, we present a novel incomplete multi-view clustering method via adaptive partial graph learning and fusion (APGLF), which can capture the local data structure of both within-view and cross-view. Specifically, we use the available data of each view to learn a corresponding view-specific partial graph, in which the within-view local structure can be well preserved. Then we design a cross-view graph fusion term to learn a consensus complete graph for different views, which can take advantage of the complementary information hidden in the view-specific partial graphs learned from incomplete views. In addition, a rank constraint is imposed on the graph Laplacian matrix of the fused graph to better recover the optimal cluster structure of original data. Therefore, APGLF integrates within-view partial graph learning, cross-view partial graph fusion and cluster structure recovering into a unified framework. Experiments on five incomplete multi-view data sets are conducted to validate the efficacy of APGLF when compared with eight state-of-the-art methods.     

Evolutionary subspace clustering using variable genome length

Subspace clustering is a data-mining task that groups similar data objects and at the same time searches the subspaces where similarities appear. For this reason, subspace clustering is recognized as more general and complicated than standard clustering. In this article, we present ChameleoClust+, a bioinspired evolutionary subspace clustering algorithm that takes advantage of an evolvable genome structure to detect various numbers of clusters located in different subspaces. ChameleoClust+ incorporates several biolike features such as a variable genome length, both functional and nonfunctional elements, and mutation operators including large rearrangements. It was assessed and compared with the state-of-the-art methods on a reference benchmark using both real-world and synthetic data sets. Although other algorithms may need complex parameter settings, ChameleoClust+ needs to set only one subspace clustering ad hoc and intuitive parameter: the maximal number of clusters. The remaining parameters of ChameleoClust+ are related to the evolution strategy (eg, population size, mutation rate), and a single setting for all of them turned out to be effective for all the benchmark data sets. A sensitivity analysis has also been carried out to study the impact of each parameter on the subspace clustering quality.     

A mathematical morphology based method for hierarchical clustering analysis of spatial points on street networks

Spatial clustering analysis is an important issue that has been widely studied to extract the meaningful subgroups of geo-referenced data. Although many approaches have been developed in the literature, efficiently modeling the network constraint that objects (e.g. urban facility) are observed on or alongside a street network remains a challenging task for spatial clustering. Based on the techniques of mathematical morphology, this paper presents a new spatial clustering approach NMMSC designed for mining the grouping patterns of network-constrained point objects. NMMSC is essentially a hierarchical clustering approach, and it generally consists of two main steps: first, the original vector data is converted to raster data by utilizing basic linear unit of network as the pixel in network space; second, based on the specified 1-dimensional raster structure, an extended mathematical morphology operator (i.e. dilation) is iteratively performed to identify spatial point agglomerations with hierarchical structure snapped on a network. Compared to existing methods of network-constrained hierarchical clustering, our method is more efficient for cluster similarity computation with linear time complexity. The effectiveness and efficiency of our approach are verified through the experiments with real and synthetic data sets.     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.     

新模糊聚类有效性指标

模糊聚类是模式识别、机器学习和图像处理等领域的重要研究内容。模糊C-均值聚类算法是最常用的模糊聚类实现算法,该算法需要预先给定聚类数才能对数据集进行聚类。提出了一种新的聚类有效性指标,对聚类结果进行有效性验证。该指标从划分熵、隶属度、几何结构角度,定义了紧凑度、分离度、重叠度三个重要特征测量。在此基础上,提出了一种最佳聚类数确定方法。将新聚类有效性指标和传统有效性指标在6个人工数据集和3个真实数据集进行实验验证。实验结果表明,所提出的指标和方法能够有效地对聚类结果进行评估,适合确定样本的最佳聚类数。     

Shared farthest neighbor approach to clustering of high dimensionality, low cardinality data

Clustering algorithms are routinely used in biomedical disciplines, and are a basic tool in bioinformatics. Depending on the task at hand, there are two most popular options, the central partitional techniques and the agglomerative hierarchical clustering techniques and their derivatives. These methods are well studied and well established. However, both categories have some drawbacks related to data dimensionality (for partitional algorithms) and to the bottom-up structure (for hierarchical agglomerative algorithms). To overcome these limitations, motivated by the problem of gene expression analysis with DNA microarrays, we present a hierarchical clustering algorithm based on a completely different principle, which is the analysis of shared farthest neighbors. We present a framework for clustering using ranks and indexes, and introduce the shared farthest neighbors (SFN) clustering criterion. We illustrate the properties of the method and present experimental results on different data sets, using the strategy of evaluating data clustering by extrinsic knowledge given by class labels.     

基于动态邻域的三支聚类分析

目前,大多数聚类方法是二支聚类,即对象要么属于一个类,要么不属于一个类,聚类的结果必须具有清晰的边界。然而,将某些不确定的对象强制分配到某个类中将降低聚类结果的结构和精度。三支聚类是一种重叠聚类,它采用核心域和边界域来表示每个类别,较好地处理了具有不确定性对象的聚类问题。提出了一种使用样本邻域将二支聚类转化为三支聚类的方法。该方法利用二支聚类的结果和每个类中元素的邻域是否完全包含在该类中来对集合进行收缩,同时利用不在该类中的元素的邻域是否与该类有交集来进行扩张。收缩的区域称为核心域,扩张域和核心域的差集称为边界域。在UCI数据集上的实验结果显示,该方法在提高聚类结果的结构和F1值方面有较好的效果。     

基于迭代分类的聚类结果改进方法

综合考虑聚类、分类的特点,从聚类结果出发,学习并利用初始聚类结构信息形成训练集,结合迭代分类思想重新划分原数据集,提出一种基于迭代分类的聚类结果改进方法。实验结果表明该方法具有更高准确率,为获得良好的聚类效果提供了新思路。     

一种快速山峰聚类算法*

山峰聚类既可以对数据集进行近似聚类,又可以为其他聚类方法提供聚类所需的初始聚类中心。减法聚类是山峰聚类的改进,它避免了山峰聚类中出现的计算量随样本维数增加呈指数增长的情况。但减法聚类对处理大样本集也力不从心。引入了P-tree数据结构,对高维大样本集进行分解,然后用减法聚类对子样本集进行聚类。此算法既避免了山峰聚类的维数灾难问题,也解决了减法聚类中样本数太大的问题。实验结果证明,该算法有效地减少了运算量,提高了聚类的速度。     

基于蚁群聚类算法的优化与改进

传统的蚁群聚类算法将聚类数据的每一维属性都等同看待,而在实际的应用中各维属性对聚类的贡献率不一,具有主次之分,若将所有属性赋予相同的权重,将对聚类的效果造成影响．为了克服这个缺陷,本文将主成份分析（PCA）方法引入到蚁群聚类当中,利用PCA计算属性的贡献率并以此构建属性的权重．在此基础上,结合一个新的初始化策略,提出了一种属性带权的改进蚁群聚类算法．通过对多个UCI数据集的测试,验证了本算法的有效性．实验结果表明,合理的权重分配能够有效的提高蚁群聚类的质量．