集群环境下的并行聚类算法之研究

本文的目的就是通过理论分析和试验,探讨集群环境下并行聚类算法的设计思想。作为一种低成本、通用并行系统,集群系统的通讯能力相对于节点的计算能力是一个瓶颈。所以本文提出,在集群环境下设计并行聚类算法时,应采用数据并行的思想。本文首先从理论上,对采用数据并行思想后影响加速比的因素和通讯策略的选择进行了分析,然后实现了一个新的并行聚类算法——PARC算法。通过PARC算法的实验,证明了理论分析的正确性,并且表明并行聚类算法可以得到良好的聚类质量。本文的研究结果可以为以后设计更好的数据并行聚类算法提供一定的理论依据。     

复杂分布数据的半监督阶段聚类

半监督聚类是一种用先验信息完善聚类过程的机器学习方法。通过将元胞自动机(cellular automata,CA)距离变换算法引入到半监督聚类过程中,采用平面距离变换算法将数据集划分为若干子类,获得聚类数和约束信息,并作为下一阶段聚类的先验信息。利用半监督K-means聚类算法对第一阶段的聚类结果做进一步划分,可以获得完整的聚类中心和聚类数,并由此提出CA-K-means二阶段聚类算法。采用3组人工数据集和3组标准UCI数据集进行对比仿真实验,将CA-K-means二阶段聚类算法与半监督K-means聚类算法、遗传Kmeans聚类算法和单纯的CA层次聚类算法进行对比,结果显示,该算法对复杂分布数据的聚类准确率较高,聚类性能更加优良。     

基于算法选择和结果评估的自动聚类方法

文章提出了一种基于算法选择和结果评估的自动聚类方法。对给定数据集,该方法首先通过分析数据集的潜在簇结构,并依据所发现的簇结构为数据集挑选一种合适的备选聚类算法集;然后利用聚类有效性指标对这个算法集的算法聚类结果进行评估,以确保得到高质量聚类结果。实验结果表明该方法能够自动地挑选适合数据集的聚类算法,并获得高质量的聚类结果。     

一种改进的模糊C均值聚类算法

针对数据集中若存在孤立点或者是噪声数据会影响模糊C均值聚类算法(FCM)的聚类性能问题,本文将离群点的辨认方法与FCM算法相结合,提出一种改进的FCM聚类算法。该算法有效地降低了孤立点或噪声数据对正常数据的影响,提高了FCM算法的聚类精度。将该算法在入侵检测系统中进行实验验证,通过与FCM算法进行对比分析,证明了该算法的有效性和可行性。     

基于K-means的最佳聚类数确定方法研究

确定数据集的最佳聚类数是聚类研究中的一个重要难题。为了更有效地确定数据集的最佳聚类数,该文提出了通过改进K-means算法并结合一个不依赖于具体算法的有效性指标Q(c)对数据集的最佳聚类数进行确定的方法。理论分析和实验结果证明了该方法具有良好的性能和有效性。     

一种新型的基于密度和栅格的聚类算法*

针对网格和密度方法的聚类算法存在效率和质量问题,给出了密度和栅格相结合的聚类挖掘算法,即基于密度和栅格的聚类算法DGCA（density and grid based clustering algorithm）。该算法首先将数据空间划分为栅格单元,然后把数据存储到栅格单元中,利用DBSCAN密度聚类算法进行聚类挖掘;最后进行聚类合并和噪声点消除,并将局部聚类结果映射到全局聚类结果。实验通过人工数据样本集对该聚类算法进行理论上验证,表明了该算法在时间效率和聚类质量两方面都得到了提高。     

基于CA模型的凝固聚类算法

聚类是数据挖掘领域的重要研究内容之一。参考基于元胞自动机距离变换算法模型,构建了基于CA模型的凝固聚类算法,该算法在CA模型演化的过程中,可以产生完整的层次聚类结果,同时对簇间的距离实现了度量,能够处理形状复杂的聚类对象,具有较好的向高维空间的推广能力以及并行计算的特性。最后通过两组聚类数据进行了实证研究,验证了该算法的有效性。     

基于自动机的微博在线突发话题检测算法

提出一种基于状态自动机的突发特征检测算法,针对微博数据长度小,语言不规范,噪声大,数据量大的特点,优化预处理过程和状态自动机模型参数;提出一种突发话题聚类算法,对特征词的词频向量表示进行改进,并引入基于词激活力(WAF)的词法特征,使得聚类效果更加准确,得到的突发话题可读性更强.最后通过实验方法验证了算法的可行性.     

基于二分K-均值的SVM决策树自适应分类方法

分析和研究了自适应降维算法在高维数据挖掘中的应用。针对已有数据挖掘算法因维灾难导致的在处理高维数据时准确率和聚类质量都较低的情况,将二分K-均值聚类和SVM决策树算法结合在一起,提出了一种适用于高维数据聚类的自适应方法 BKM-SVMDT。该算法能保证二分K-均值聚类是在低维数据空间中进行,其结果再反过来帮助SVM在高维空间中的执行,这样反复执行以取得较好的分类精度和效率。标准数据集的实验结果证明了该方法的有效性。     

基于区域比例的聚类方法

为了改善DBSCAN参数敏感性和对密度分布不均数据对象聚类质量不高的问题,提出了一种基于DBSCAN算法的改进聚类方法。算法使用K最近邻的均值距离度量密度,中心点选取当前密度最大点,并以中心点为核心点扩展种子队列,直至由给定的密度比例因子所决定的密度边缘。为了改善聚类质量,提出了候选核心点,并使用给定的半径比例因子发现核心点。在实验中,利用数据集对该算法进行了测试,测试结果证明了该改进算法的参数鲁棒性,和在聚类密度分布不均数据集时的较好性能。     

A new data clustering approach: Generalized cellular automata

This paper is devoted to a novel stochastic generalized cellular automata (GCA) for self-organizing data clustering in enterprise computing. The GCA transforms the data clustering process into a stochastic process over the configuration space on a GCA array. The GCA-based approach to data clustering has many advantages in terms of the real-time performance and the ability to effectively deal with a variety of data sets, including noise data, dynamical data, multi-type and multi-distribution data, high-dimensional and large-scale data set. The GCA clustering approach also has the learning ability, and the better feasibility for hardware implementation with VLSI systolic technology. The simulations and comparisons have shown the effectiveness of the proposed GCA for the data clustering in enterprise computing.     

广义细胞自动机的结构及其硬件实现

该文作者曾提出了广义细胞自动机(GCA)的原理和并行算法．并且应用于网络快速包交换等动态优化问题．该文进一步讨论了这种新的广义细胞自动机的体系结构、算法的硬件实现及其电路设计。它们对于GCA的实际应用有重要意义．GCA结构不同于Hopfield神经网络(HNN)和细胞神经网络(CNN)，GCA由多层次多粒度宏细胞组成塔形结构．它具有多粒度的宏细胞动力学特征．相同粒度宏细胞之间没有交互，但不同粒度宏细胞之间存在一定程度的交互或反馈．分析和实验表明．在问题求解的优化性、实时性、硬件实现复杂性等方面．该文给出的GCA结构和硬件实现．与HNN和CNN相比有诸多优点．     

基于单元区域的高维数据聚类算法

高维数据空间维数较高,数据点分布稀疏、密度平均,从中发现数据聚类比较困难,而用基于距离的方法进行高维数据聚类,维数的增多会使得计算对象间距离的时间开销增大. CAHD(clustering algorithm of high-dimensional data)算法首先采用双向搜索策略在指定的n维空间或其子空间上发现数据点密集的单元区域,然后采用逐位与的方法为这些密集单元区域进行聚类分析.双向搜索策略能够有效地减少搜索空间,从而提高算法效率,同时,聚类密集单元区域只用到逐位与和位移两种机器指令,使得算法效率得到进一步提高.算法CAHD可以有效地处理高维数据的聚类问题.基于数据集的实验表明,算法具有很好的有效性.     

大规模多视图数据的自降维K-means算法

为了提升传统多视图K-means算法在高维数据中的聚类性能,提出了一种鲁棒性大规模多视图数据的自降维K-means算法RMSKMC（robust multi-view subKmeans clustering）,通过寻找单个视图上的最优子空间实现高维数据的自降维,利用非负矩阵分解（NMF）对损失函数进行重构,使不同视图共享相同的聚类指示矩阵从而实现多视图信息互补,完成大规模多视图数据的聚类。实验结果表明,在大规模多视图数据集上,该算法比其他多视图聚类算法资源消耗更小,并且能够进行更为准确的聚类。     

高维数据流的自适应子空间聚类算法

高维数据流聚类是数据挖掘领域中的研究热点。由于数据流具有数据量大、快速变化、高维性等特点,许多聚类算法不能取得较好的聚类质量。提出了高维数据流的自适应子空间聚类算法SAStream。该算法改进了HPStream中的微簇结构并定义了候选簇,只在相应的子空间内计算新来数据点到候选簇质心的距离,减少了聚类时被检查微簇的数目,将形成的微簇存储在金字塔时间框架中,使用时间衰减函数删除过期的微簇;当数据流量大时,根据监测的系统资源使用情况自动调整界限半径和簇选择因子,从而调节聚类的粒度。实验结果表明,该算法具有良好的聚类质量和快速的数据处理能力。     

一种基于引力的聚类方法

将万有引力的思想引入聚类分析中,提出了一种基于引力的聚类方法GCA(Gravitybased Clustering Approach),同时给出了一种计算聚类阈值的简单而有效的方法。GCA关于数据库的大小和属性个数具有近似线性时间复杂度,这使得聚类方法GCA具有好的扩展性。实验结果表明GCA可产生高质量的聚类结果。     

一种基于层次聚类的全局孤立点识别方法*

现有的孤立点检测算法在通用性、有效性、用户友好性及处理高维大数据集的性能还不完善,为此提出一种快速有效的基于层次聚类的全局孤立点检测方法。该方法基于层次聚类的结果,根据聚类树和距离矩阵可视化判断数据孤立程度,并确定孤立点数目。从聚类树自顶向下,无监督地去除孤立点。仿真实验验证了方法能快速有效识别全局孤立点,具有用户友好性,适用于不同形状的数据集,可用于大型高维数据集的孤立点检测。     

一种新的基于广义细胞自动机的网络快速包交换优化方法

实时优化求解快速包交换问题(FPS)是提高网络性能的重要手段．基于梯度下降法等数学规划方法，不能并行地实时地优化求解FPS问题，而基于Hopfield型神经网络和细胞神经网络的优化方法中，都只有单一粒度的细胞动力学方程和单一粒度细胞之间的相互作用，不仅收敛到平衡点的过程长，而且神经网络参数的选择和修正十分困难．该文提出一种新的具有多粒度宏细胞的广义细胞自动机模型和方法，广义细胞自动机中的小粒度宏细胞聚合成可以独立演化的大粒度宏细胞，通过多粒度群体的不同程度群体智能的相互作用，能够比目前其他方法更快更有效地分布并行地优化求解FPS问题和其它类似的复杂的网络优化问题．     

一种基于子空间聚类的图像分层索引方法

随着多媒体技术的发展,许多领域产生大量的高维数据集。为了有效地检索这些高维数据,高维索引成为人们研究的热点。聚类树是一种有效地支持高维数据检索的索引结构。提出了一种基于子空间聚类的聚类树结构,该索引结构基于一种改进的CLIQUE聚类算法,利用小波变换的多尺度特性对图像特征分布曲线进行不同尺度的小波变换,去除一些小的分类和可能的噪声干扰,从而得到不同粒度下的层次聚类。在层次聚类的基础上,建立起分层索引结构。由于改进的聚类算法使用爬山法确定子空间聚类,因而有效地避免了用户参数的定义。实验结果证明,该方法在不需要用户设定聚类参数下能够进行有效聚类,在不同尺度下构建的聚类结构能够有效地组织图像关系,大大提高图像的检索效率。     

基于广义细胞自动机的网络信息自组织利用方法

目前的网络信息利用模式存在着严重缺陷，它将网络上发生的海量、随机、分布、并行的信息利用行为当作是没有后效的和彼此无关的．该文提出一种新的基于网络信息自组织的信息利用模式以及基于广义细胞自动机的网络信息自组织方法．按照本文的信息利用模式，网络信息利用行为总是伴随着信息内容在网络中的扩散，网络信息利用行为成为有后效的和相关的，从而导致不同信息内容和不同内容粒度的分布式的信息自组织结构，形成基于这种信息自组织结构的网络信息利用模式．文中进而提出一种广义细胞自动机的模型、结构和算法，通过群体智能，发现网络中的信息自组织结构．分析和实验表明，基于广义细胞自动机的的网络信息自组织利用模式，在效率、自适应性和可靠性等方面优于目前的网络信息利用方法．