基于启发式确定类数的NJW谱聚类算法

基于图论理论的NJW谱聚类算法的核心思想是将数据点映射到特征空间后再利用K-means算法进行聚类,从而得到原始数据的聚类结果。NJW算法是K-means算法的推广,并且在任意形状的数据上都具有较好的聚类效果,从而有着广泛的应用。但是,类数C和高斯核函数中的尺度参数σ较大程度地影响着NJW的聚类性能;另外,K-means对随机初始值的敏感性也影响着NJW的聚类结果。为此,一种基于启发式确定类数的谱聚类算法(记为DP-NJW)被提出。该算法先根据数据的密度分布确定类中心点和类数,这些类中心点作为特征空间中K-means聚类的初始类中心,然后用NJW进行聚类。文中通过实验将DP-NJW算法和经典聚类算法在7个公共数据集上进行测试和对比,其中DP-NJW算法在5个数据集上的聚类精度高于NJW的平均聚类精度,在另2个数据集上二者持平。对比DPC算法,所提算法在5个数据集上也有不俗的聚类精度,而且DP-NJW的计算消耗较小,在较大的数据集aggregation上表现更为突出。实验结果表明,文中所提的DP-NJW算法更具优势。     

基于人工免疫网络的聚类可行解求解算法

网络特征数据集中可能包含未知的入侵模式,因此不能预先设定聚类簇的数量,为了在保持聚类分析精度的前提下提高动态聚类算法的效率,提出了可划分聚类数据集的聚类可行解的概念,设计了一种基于人工免疫网络的聚类可行解的获取算法,并对算法获得聚类可行解的条件和概率进行了一定的理论分析。     

基于目标协同规划的网络入侵特征聚类仿真

在网络入侵检测优化的研究中,对网络入侵特征进行准确检测,由于在复杂的网络环境中会存在大量噪声,传统的方法只是单一的入侵特征聚类方法,难以在包含大量噪声的复杂网络环境中进行入侵特征聚类.提出一种基于目标协同规划思想的网络入侵特征聚类方法.利用标准化处理过程和归一化处理过程对对网络入侵数据进行预处理,能够将原始的网络入侵特征属性映射到标准属性空间.提取入侵特征构成数据集合,并进行降维处理,为入侵特征的聚类提供了准确数据基础,将可能性模糊聚类算法和聚类中心分离的模糊聚类算法进行入侵特征聚类目标的协同规划,能够得到准确的聚类中心.实验结果表明,改进算法能够提高网络入侵聚类的准确率.     

分布式环境中聚类问题算法研究综述

传统的集中式聚类是对集中存放在单个站点的数据集进行聚类,但不能解决数据分布存储环境下的聚类问题,而分布式聚类算法是从分布存储的数据集中提取分类模式,因此能满足此需求。针对分布式聚类算法进行综述和分析。首先对现有的分布式聚类算法进行了分类,然后对每类算法的基本思想和优缺点进行了比较,最后采用Iris和Wine两个数据集对几种分布式聚类算法从聚类精度和聚类时间两方面进行了比较。     

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

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

对自动化网络聚类的思考

聚类算法是自动化网络运行的基础,解决传统聚类算法精度差的问题是当前自动化网络技术的发展方向。从电阻网络的异构数据系统聚类算法以及传统聚类算法改进两个方面探讨了其在自动化网络中的应用,改进后的算法计算效率明显提高,计算精度得到增加。     

基于电阻网络的异构数据协同聚类算法

传统聚类方法处理的是同构数据,无法满足异构数据同时聚类的应用需求,聚类结果的准确率较低,标签可读性较差。针对上述问题,提出一种基于电阻网络的异构数据协同聚类算法。该算法将异构关联数据抽象为多部图形式的电阻网络,进行特征计算及聚类。在对异构数据进行协同聚类后,可以得到一种聚类结构,其中每一类包含多种异构数据,它们之间可以互为标签,标签可读性高。实验结果证明,该方法是一种切实可行且效果优异的数据聚类算法。     

基于SOM神经网和K-均值算法的图像分割

提出了一种基于SOM神经网络和K-均值的图像分割算法。SOM网络将多维数据映射到低维规则网格中,可以有效地用于大型数据的挖掘;而K-均值是一种动态聚类算法,适用于中小型数据的聚类。文中算法利用SOM网络将具有相似特征的象素S点映射到一个2-D神经网上,再根据神经元间的相似性,利用K-均值算法将神经元聚类。文中将该算法用于彩色图像的分割,并给出了经SOM神经网初聚类后,不同K值下神经元聚类对图像分割的结果及与单纯K-均值分割图像进行对比。     

蛋白质相互作用网络的蜂群信息流聚类模型与算法

蛋白质相互作用网络的聚类算法研究是充分理解分子的结构、功能及识别蛋白质的功能模块的重要方法.很多传统聚类算法对于蛋白质相互作用网络聚类效果不佳.功能流模拟算法是一种新型聚类算法,但该算法没有考虑到距离的作用效果并且需要人为地设置合并阈值,带有主观性.文中提出了一种新颖的基于蜂群优化机理的信息流聚类模型与算法.该方法中,数据预处理采用结点网络综合特征值的排序来初始化聚类中心,将蜂群算法的蜜源位置对应于其聚类中心,蜜源的收益度大小对应于模块间的相似度,采蜜蜂结点的所有邻接点按照结点网络综合特征值的降序排列,作为侦察蜂的搜索邻域.采用正确率、查全率等指标对聚类效果做出客观评价,并对算法的一些关键参数进行仿真、对比与分析.结果表明新算法不仅克服了原功能流模拟算法的缺点,且其正确率和查全率的几何平均值最高,能够有效地识别蛋白质功能模块.     

社团挖掘的并行化AP聚类方法

采用AP聚类算法进行复杂网络社团挖掘,提高了社团挖掘的精度,但在处理海量数据时算法速率明显下降,其中一个重要原因是单台计算机的计算性能无法满足海量数据的计算需求。为了提高社团挖掘AP聚类在处理海量数据时的速率,设计出一种在Hadoop框架下进行的社团挖掘的并行化AP聚类方法;将传统单机模式下的社团挖掘AP聚类算法在分布式平台上分布进行并行化。实验表明,社团挖掘的并行化AP聚类方法在社团挖掘精度不下降的情况下提高了海量数据的社团挖掘速率。     

基于空间结构的符号数据仿射传播算法*

由于符号型数据缺乏清晰的空间结构,很难构造一种合理的相似性度量,从而使诸多数值型聚类算法难以推广至符号型数据聚类.基于此种情况,文中引入一种空间结构表示方法,把符号型数据转化为数值型数据,能够在保持原符号型数据的结构特征的基础上重新构造样本之间的相似度.基于此方法,将仿射传播(AP)聚类算法迁移至符号数据聚类中,提出基于空间结构的符号数据AP算法(SBAP).在UCI数据集中若干符号型数据集上的实验表明,SBAP可以使AP算法有效处理符号型数据聚类问题,并且可以提升算法性能.     

半监督聚类的若干新进展

半监督聚类方法利用少量标记数据提高聚类算法的性能,已逐渐发展成为模式识别及相关领域的研究热点.文中首先综述了半监督聚类算法的一些新进展,包括基于约束的方法、基于距离的方法和基于距离与约束的融合方法.然后提出一种基于约束的半监督模糊C-means聚类算法.实验表明,该算法与传统的模糊C-means及半监督K-means方法相比,具有更好的聚类精度.     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

Empirical comparison of fast partitioning-based clustering algorithms for large data sets

Several fast algorithms for clustering very large data sets have been proposed in the literature, including CLARA, CLARANS, GAC-R³, and GAC-RAR_w. CLARA is a combination of a sampling procedure and the classical PAM algorithm, while CLARANS adopts a serial randomized search strategy to find the optimal set of medoids. GAC-R³ and GAC-RAR_w exploit genetic search heuristics for solving clustering problems. In this research, we conducted an empirical comparison of these four clustering algorithms over a wide range of data characteristics described by data size, number of clusters, cluster distinctness, cluster asymmetry, and data randomness. According to the experimental results, CLARANS outperforms its counterparts both in clustering quality and execution time when the number of clusters increases, clusters are more closely related, more asymmetric clusters are present, or more random objects exist in the data set. With a specific number of clusters, CLARA can efficiently achieve satisfactory clustering quality when the data size is larger, whereas GAC-R³ and GAC-RAR_w can achieve satisfactory clustering quality and efficiency when the data size is small, the number of clusters is small, and clusters are more distinct and symmetric.     

基于聚类假设的数据流分类算法*

获取数据流上样本的真实类别的代价很高,因此标记所有样本的方式缺乏实用性,而随机标记部分样本又会导致模型的不稳定.针对上述问题,文中提出基于聚类假设的数据流分类算法.基于通过聚类算法分到同类中的样本可能具有相同类别这一聚类假设,利用训练数据集上的聚类结果拟合样本的分布情况,在分类阶段有目的性地选取很难分类或潜在概念漂移的样本更新模型.为了训练数据集上每个类别的样本,建立各自对应的基础分类器,当数据流中样本的类别消失或重现时,只需要冻结或激活与之对应的基础分类器,而无需再重新学习之前已经掌握的知识.实验表明,文中算法能够在适应概念漂移的前提下,减少更新模型需要的样本数量,并且取得和当前数据流上的分类算法相当或更好的分类效果.     

A novel cluster center fast determination clustering algorithm

As one of the most important techniques in data mining, cluster analysis has attracted more and more attentions in this big data era. Most clustering algorithms have encountered with challenges including cluster centers determination difficulty, low clustering accuracy, uneven clustering efficiency of different data sets and sensible parameter dependence. Aiming at clustering center determination difficulty and parameter dependence, a novel cluster center fast determination clustering algorithm was proposed in this paper. It is supposed that clustering centers are those data points with higher density and larger distance from other data points of higher density. Normal distribution curves are designed to fit the density distribution curve of density distance product. And the singular points outside the confidence interval by setting the confidence interval are proved to be clustering centers by theory analysis and simulations. Finally, according to these clustering centers, a time scan clustering is designed for the rest of the points by density to complete the clustering. Density radius is a sensible parameter in calculating density for each data point, mountain climbing algorithm is thus used to realize self-adaptive density radius. Abundant typical benchmark data sets are testified to evaluate the performance of the brought up algorithms compared with other clustering algorithms in both aspects of clustering quality and time complexity.     

一种改进的k-均值聚类算法

针对k-均值(k-means)聚类算法中随机选取初始聚类中心的缺陷,提出了一种新的基于数据样本分布选取初始聚类中心的方法.实验结果表明,改进后的算法能改善其聚类性能,并能取得较高的分类准确率.     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

Clustering algorithms for maximizing the lifetime of wireless sensor networks with energy-harvesting sensors

Motivated by recent developments in wireless sensor networks (WSNs), we present several efficient clustering algorithms for maximizing the lifetime of WSNs, i.e., the duration till a certain percentage of the nodes die. Specifically, an optimization algorithm is proposed for maximizing the lifetime of a single-cluster network, followed by an extension to handle multi-cluster networks. Then we study the joint problem of prolonging network lifetime by introducing energy-harvesting (EH) nodes. An algorithm is proposed for maximizing the network lifetime where EH nodes serve as dedicated relay nodes for cluster heads (CHs). Theoretical analysis and extensive simulation results show that the proposed algorithms can achieve optimal or suboptimal solutions efficiently, and therefore help provide useful benchmarks for various centralized and distributed clustering scheme designs.