基于混合差分进化的滑动窗口数据流聚类算法研究

针对传统的基于滑动窗口的数据流聚类算法存在的算法执行效率低、聚类质量较差等缺点,提出了一种基于混合差分进化的滑动窗口数据流聚类算法。该算法将数据流聚类过程分为两个部分：在线的时序窗口数据信息微簇特征向量生成和离线阶段的聚类优化。对在线生成的微簇进行微簇集合的更新与维护,利用改进的粒子群算法对离线的微簇数据信息进行适应度值的计算,将种群分为优势子种群和普通子种群,然后利用个体适应度值和平均适应度值的判别来生成当前个体环境的最优候选解,并迭代地对个体进行进化,输出具有最优适应度值的聚类集合,完成对数据流的聚类。仿真实验结果表明,算法在对数据流执行聚类时具有较高的执行效率,并且最后聚类的质量较好,算法实用性强。     

一种基于网格方法的高维数据流子空间聚类算法

基于对网格聚类方法的分析，结合由底向上的网格方法和自顶向下的网格方法，设计了一个能在线处理高维数据流的子空间聚类算法。通过利用由底向上网格方法对数据的压缩能力和自顶向下网格方法处理高维数据的能力，算法能基于对数据流的一次扫描，快速识别数据中位于不同子空间内的簇。理论分析以及在多个数据集上的实验表明算法具有较高的计算精度与计算效率。     

一种基于质量估算的空间数据流聚类算法研究

针对传统的基于网格密度的数据流聚类方法丢失数据的空间位置特性的缺陷,提出了一种基于质量估算（mass estimation）的空间数据流聚类方法。通过 树进行空间划分,可将到达数据映射到不同的划分区域,在树得到质量（mass）的基础上,进行各子区域的密度推算的同时引入衰减因子,以及在线动态维护微簇,可精确反映空间数据流的演化信息。该方法在真实数据与模拟数据的综合试验中验证了算法的聚类效果与高效率性,并通过与传统数据流聚类算法的对比,进一步体现出其在聚类效果上的优势。该方法能够在保证较低的时间复杂度的基础上,更好的保留了数据的空间位置特性,因而能够更好的适应空间数据流聚类的需求。     

一种基于数据流的软子空间聚类算法

针对高维数据的聚类研究表明,样本在不同数据簇往往与某些特定的数据特征子集相对应.因此,子空间聚类技术越来越受到关注.然而,现有的软子空间聚类算法都是基于批处理技术的聚类算法,不能很好地应用于高维数据流或大规模数据的聚类研究中.为此,利用模糊可扩展聚类框架,与熵加权软子空间聚类算法相结合,提出了一种有效的熵加权流数据软子空间聚类算法——EWSSC(entropy-weighting streaming subspace clustering).该算法不仅保留了传统软子空间聚类算法的特性,而且利用了模糊可扩展聚类策略,将软子空间聚类算法应用于流数据的聚类分析中.实验结果表明,EWSSC 算法对于高维数据流可以得到与批处理软子空间聚类方法近似一致的实验结果.     

基于微簇进化学习的数据流快速聚类算法研究

为了解决滑块窗口的数据流聚类算法中的聚类质量和算法执行效率问题,提出了基于微簇进化学习的数据流快速聚类算法.首先在在现阶段以时间滑块窗口的时间快照窗口周期为时间单位进行数据流粒度快照获取,并进行微簇的实时生成,依据微簇更新机制进行微簇维护;然后在离线阶段对微簇数据信息进行实时获取,利用改进的粒子群算法对数据进行聚类,根据粒子速度进行粒距划分和粒子权重系数的映射与调整,并计算粒子的适应度值;最后迭代地对粒子的局部极值和全局极值进行更新,输出聚类好的类别.实验证明改进算法具有较好的算法执行效率,并且有较优的负载能力.     

基于密度的优化数据流聚类算法

为了解决数据流聚类算法中有效处理离群点这一关键问题,改进了基于密度的数据流聚类算法,在DenStream算法基础上提出了具有双检测时间策略DDTS(double derection time strategy)的基于密度的数据流聚类算法.该策略在数据流流速波动的情况下,结合时间与流数据数量两方面因素对微簇进行测试.通过在线动态维护和删减微簇,保存可能升级的离群点来改善聚类效果.实验结果表明,改进算法具有良好的适用性和有效性,能够取得较高的聚类质量.     

基于相对密度的数据流模糊聚类算法

提出的基于相对密度的数据流模糊聚类算法结合了相对密度聚类和模糊聚类的优点,能形成任意形状、多密度分辨率的层次聚类结果.同时,利用微簇空间位置重叠关系,定义了微簇集合间的差运算,从而有效地支持了用户指定时间窗口内的数据流聚类要求.通过与CluStream算法在聚类质量和处理时间两个方面的比较分析,发现基于相对密度的数据流模糊聚类算法具有明显的优势.     

基于衰减模型的混合属性数据流离群检测

数据流离群检测因内存容量限制和实时检测需求而成为离群检测的一个难点。介绍了一种快速混合属性数据流离群检测算法。在衰减模型下增量聚类数据流,生成代表数据分布的聚类特征集合,半径阈值动态变化;当接收到检测请求时,计算满足条件的每个簇的离群因子,具有高离群因子的簇作为结果输出。同时提出了一种可有效区分离群簇与数据进化初始阶段的方法。算法的时间与空间复杂度同数据流规模近似成线性关系,在真实数据集上的实验结果显示,该算法可有效检测混合属性数据流中的离群点。     

一种不确定数据流子空间聚类算法

针对不确定数据流上的聚类问题提出一种不确定数据流子空间聚类算法UDSSC.该算法使用滑动窗口机制接收新到达的数据,剔除陈旧的数据;还引入子空间簇生成策略和新型离群点机制;系统建立了三个缓冲区分别存储新到来的元组、要进行聚类的元组和离群点元组,以此获得高质量的聚类结果.实验表明,UDSSC算法与同类型算法相比,具有更好的聚类效果、更低的时间复杂度和更强的扩展性.     

一种基于属性相关度的子空间聚类算法

与在所有特征空间寻找聚类不同,子空间聚类的目标是找到嵌在不同子空间的簇,是实现高维数据聚类的有效途径.传统聚类算法主要采用基于距离测量的方法进行聚类,难以处理高维数据.提出一种能够处理高维数据的子空间聚类算法(Attribute relevancy-based subspace clustering algorithm,ARSUB),将属性转化为频繁模式中的项集,将聚类问题转化为频繁模式挖掘问题,然后基于项目对间强相关的关系建立关系矩阵,以衡量任意两个项集之间的相关度,进而得到强相关的候选子空间.最后利用候选子空间进行聚类得到存在于不同子空间中的簇.在合成数据集与真实数据集的实验结果表明,这种方法具有较高的准确度和效率.     

基于概率数据流的有效聚类算法

提出一种在概率数据流上进行聚类的有效方法P-Stream.P-Stream针对数据流上的概率元组提出强簇、过渡簇和弱簇的概念,设计一种有效的在线候选簇选择策略,为每个不断到达的数据元组合理地找到可能归属的簇,并在每个检查点存储微簇快照,以便离线进一步高层聚类和演化分析.最后设计一个“积极”的二层聚类模型来判断现有的第1层聚类模型是否还适应数据流中最近到达的概率元组.实验采用KDD-CUP’98和KDD-CUP’99真实数据集以及变换高斯分布的人工数据集构造概率数据流.实验结果表明,P-Stream具有良好的聚类质量、较快的处理速度,能够有效地适应数据演化情况.     

A novel attribute weighting algorithm for clustering high-dimensional categorical data

Due to data sparseness and attribute redundancy in high-dimensional data, clusters of objects often exist in subspaces rather than in the entire space. To effectively address this issue, this paper presents a new optimization algorithm for clustering high-dimensional categorical data, which is an extension of the k-modes clustering algorithm. In the proposed algorithm, a novel weighting technique for categorical data is developed to calculate two weights for each attribute (or dimension) in each cluster and use the weight values to identify the subsets of important attributes that categorize different clusters. The convergence of the algorithm under an optimization framework is proved. The performance and scalability of the algorithm is evaluated experimentally on both synthetic and real data sets. The experimental studies show that the proposed algorithm is effective in clustering categorical data sets and also scalable to large data sets owning to its linear time complexity with respect to the number of data objects, attributes or clusters.     

基于双层网格和密度的数据流聚类算法

传统的基于网格的数据流聚类算法在同一粒度的网格上进行聚类,虽然提高了处理速度,但聚类准确性较低。针对此问题,提出一种新的基于双层网格和密度的数据流聚类算法DBG Stream。在2种粒度的网格上对数据流进行聚类,并借鉴CluStream算法的思想,将聚类过程分为2个阶段。在线过程中利用粗粒度的网格单元形成初始聚类,离线过程中在细粒度网格单元上,对位于簇边界的网格单元进行二次聚类以提高聚类精度,并实现了关键参数的自动设置,通过删格策略提高算法效率。实验结果表明,DBG Stream算法的聚类精确度较D Stream算法有较大提高,有效解决了传统基于网格聚类算法的聚类精度较低的问题。     

一种基于密度的空间数据流在线聚类算法

为了解决空间数据流中任意形状簇的聚类问题,提出了一种基于密度的空间数据流在线聚类算法(On-line density-based clustering algorithm for spatial datastream,OLDStream),该算法在先前聚类结果上聚类增量空间数据,仅对新增空间点及其满足核心点条件的邻域数据做局部聚类更新,降低聚类更新的时间复杂度,实现对空间数据流的在线聚类.OLDStream算法具有快速处理大规模空间数据流、实时获取全局任意形状的聚类簇结果、对数据流的输入顺序不敏感、并能发现孤立点数据等优势.在真实数据和合成数据上的综合实验验证了算法的聚类效果、高效率性和较高的可伸缩性,同时实验结果的统计分析显示仅有4%的空间点消耗最坏运行时间,对每个空间点的平均聚类时间约为0.033 ms.     

高通信效率的分布式流数据聚类算法

传感器节点的资源是有限的,高的通信开销会消耗大量的电量。为了减小分布式流数据分类算法的通信开销,提出一种高效的分布式流数据聚类算法。该算法包含在线局部聚类和离线全局协同聚类两个阶段。在线局部聚类算法将每个流数据源进行局部聚类,并将聚类后的结果通过序列化技术发往协同节点;协同节点得到来自不同流数据源的局部聚类信息后进行全局聚类。从实验中可以看出,当不断增加窗口的大小时,算法用于数据发送的时间恒定不变,算法的聚类时间和总的时间呈线性增长,即所提出算法的执行时间不受滑动窗口宽度和聚类个数的影响;同时该算法与集中式算法的准确性接近,并且通信开销远远小于相关的分布式算法。实验结果表明,该算法具有很好的可扩展性,可应用于对大规模分布式流数据源进行聚类分析。     

Validation indices for projective clustering

Cluster validation is a major issue in cluster analysis of data mining, which is the process of evaluating performance of clustering algorithms under varying input conditions. Many existing validity indices address clustering results of low-dimensional data. Within high-dimensional data, many of the dimensions are irrelevant, and the clusters usually only exist in some projected subspaces spanned by different combinations of dimensions. This paper presents a solution to the problem of cluster validation for projective clustering. We propose two new measurements for the intracluster compactness and intercluster separation of projected clusters. Based on these measurements and the conventional indices, three new cluster validity indices are presented. Combined with a fuzzy projective clustering algorithm, the new indices are used to determine the number of projected clusters in high-dimensional data. The suitability of our proposal has been demonstrated through an empirical study using synthetic and real-world datasets.     

An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data

This paper presents a new k-means type algorithm for clustering high-dimensional objects in sub-spaces. In high-dimensional data, clusters of objects often exist in subspaces rather than in the entire space. For example, in text clustering, clusters of documents of different topics are categorized by different subsets of terms or keywords. The keywords for one cluster may not occur in the documents of other clusters. This is a data sparsity problem faced in clustering high-dimensional data. In the new algorithm, we extend the k-means clustering process to calculate a weight for each dimension in each cluster and use the weight values to identify the subsets of important dimensions that categorize different clusters. This is achieved by including the weight entropy in the objective function that is minimized in the k-means clustering process. An additional step is added to the k-means clustering process to automatically compute the weights of all dimensions in each cluster. The experiments on both synthetic and real data have shown that the new algorithm can generate better clustering results than other subspace clustering algorithms. The new algorithm is also scalable to large data sets.     

Visualization of fuzzy clusters by fuzzy Sammon mapping projection: application to the analysis of phase space trajectories

Since in practical data mining problems high-dimensional data are clustered, the resulting clusters are high-dimensional geometrical objects, which are difficult to analyze and interpret. Cluster validity measures try to solve this problem by providing a single numerical value. As a low dimensional graphical representation of the clusters could be much more informative than such a single value, this paper proposes a new tool for the visualization of fuzzy clustering results. By using the basic properties of fuzzy clustering algorithms, this new tool maps the cluster centers and the data such that the distances between the clusters and the data-points are preserved. During the iterative mapping process, the algorithm uses the membership values of the data and minimizes an objective function similar to the original clustering algorithm. Comparing to the original Sammon mapping not only reliable cluster shapes are obtained but the numerical complexity of the algorithm is also drastically reduced. The developed tool has been applied for visualization of reconstructed phase space trajectories of chaotic systems. The case study demonstrates that proposed FUZZSAMM algorithm is a useful tool in user-guided clustering.     

高维数据流子空间聚类发现及维护算法

近年来由于数据流应用的大量涌现,基于数据流模型的数据挖掘算法研究已成为重要的应用前沿课题.提出一种基于Hoeffding界的高维数据流的子空间聚类发现及维护算法--SHStream.算法将数据流分段（分段长度由Hoeffding界确定）,在数据分段上进行子空间聚类,通过迭代逐步得到满足聚类精度要求的聚类结果,同时针对数据流的动态性,算法对聚类结果进行调整和维护.算法可以有效地处理高雏数据流和对任意形状分布数据的聚类问题.基于真实数据集与仿真数据集的实验表明,算法具有良好的适用性和有效性.