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

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

一种基于区域划分的数据流子空间聚类方法

数据流子空间聚类的主要目的是在合理的时间段内准确找到数据流特征子空间中的聚类.现有的数据流子空间聚类算法受参数影响较大,通常要求预先给出聚类数目或特征子空间,且聚类结果不能及时反映数据流的变化情况.针对以上缺陷,提出一种新的数据流子空间聚类算法SC-RP,SC-RP无需预先给出聚类数目或特征子空间,对孤立点不敏感,可实现快速聚类,通过区域树结构记录数据流的变化并及时更新统计信息,进而根据数据流的变化调整聚类结果.通过在真实数据集与仿真数据集上的实验,证明了SC-RP在聚类精度和速度上优于现有的数据流子空间聚类算法,且对聚类数目及数据维度均具有良好的伸缩性.     

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

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

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

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

高维Turnstile型数据流聚类算法

现有数据流聚类算法只能处理Time Series和Cash Register型数据流,并且应用于高维数据流时其精度不甚理想。提出针对高维Turnstile型数据流的子空间聚类算法HT-Stream,算法对数据空间进行网格划分,在线动态维护网格单元信息,采用倾斜时间窗口存储统计信息,根据用户指定时间跨度离线输出聚类结果。基于真实数据集与仿真数据集的实验表明,算法具有良好的适用性和有效性。     

一种基于时态密度的倾斜分布数据流聚类算法

为解决倾斜分布的数据流聚类这一难题,提出了时态密度概念,给出其度量,揭示了其包括可增量计算在内的一系列数学性质;设计了时态密度树结构,提高了聚类时的存储和检索效率;设计了能够以实时或异步方式捕捉数据倾斜分布的数据流时态特征的聚类算法TDCA(temporal density based clustering algorithm),其时间复杂度为O(c(m(lgm).实验结果表明,该算法不仅有较强的功能,而且具有较好的规模可伸缩性.     

基于仿射传播的进化数据流在线聚类算法

为提高数据流聚类的精度和时效性,提出一种具有时态特征与近邻传播思想的高效数据流聚类算法(TCAPStream).该算法利用改进的WAP将新检测到的类模式合并到聚类模型中,同时利用微簇时态密度表征数据流的时态演化特征,并提出在线动态删除机制对微簇进行维护,使算法模型既能体现数据流的时态特征,又能反映数据流的分布特性,得到更精确的聚类结果.实验结果表明,该算法在多个人工数据集和真实数据集上不仅具有良好的聚类效果,而且具有较好的伸缩性和可扩展性.     

云计算环境下高复杂度动态数据的增量密度快速聚类算法研究

针对传统的聚类算法存在开销大、聚类质量差、聚类速度慢等问题,提出一种新的云计算环境下高复杂度动态数据的增量密度快速聚类算法。首先,依据密度对云计算环境下高复杂度动态数据进行聚类,从数据空间中找到部分子空间,使得数据映射至该空间后可产生高密度点集区域,将连通区域的集合看作聚类结果;其次,通过DBSCAN算法进行增量聚类,并对插入或删除数据导致的原聚类合并或分裂进行研究;最后,在更新的过程中通过改变核心状态数据的邻域中含有的全部核心数据进行处理,从插入或删除数据两方面进行增量聚类分析。实验结果表明,所提算法开销低、聚类速度快、聚类质量高。     

基于k均值分区的流数据高效密度聚类算法

数据流聚类是数据流挖掘研究的一个重要内容,已有的数据流聚类算法大多采用k中心点(均值)方法对数据进行聚类,不能对数据分布不规则以及高维空间数据流进行有效聚类.论文提出一种基于k均值分区的流数据密度聚类算法,先对数据流进行分区做k均值聚类生成中间聚类结果(均值参考点集),随后对这些均值参考点进行密度聚类,理论分析和实验结果表明算法可以有效解决数据分布不规则以及高维空间数据流聚类问题,算法是有效可行的.     

DEN-Stream:一种分布式数据流聚类方法

现有的数据流聚类方法很难兼顾数据稀疏和子空间聚类等高维数据难题,而分布式数据流对数据流聚类提出包括在线计算效率、通信开销以及多路数据的融合等更多挑战。提出分布式数据流聚类方法,采用全局统一的网格划分和衰退时间以支持多路数据流融合,并周期性检查和删除过期网格来控制概要规模。通过对多路高维数据流的一遍扫描,发现高维数据流子空间任意形状的聚类,并反映数据分布随时间的演化。在线组件效率高开销低,概要信息简洁,通信代价低。实验表明,该方法能够对分布式数据流正确聚类并演进,在线组件效率高,概要规模小。     

基于近邻传播的文本数据流聚类算法研究

随着大数据时代的到来,网络上产生了大量非结构化文本数据流,这些文本数据流具有动态、高维、稀疏等特征。针对这些特点,首先将传统的AP算法及流式文本数据特征相结合,然后提出文本数据流聚类算法——OAP-s算法。该算法通过在AP算法上引入衰减因子,对聚类中心结果进行衰减,同时将当前时间窗口的聚类中心带入到下一时间窗口中进行聚类。针对OAP-s算法的不足,又提出了OWAP-s算法。该算法在OAP-s算法模型的基础上定义了加权相似度,并通过引入吸引度因子,使得历史聚类中心更具吸引性,得到更精确的聚类结果。同时,两种算法均采用滑动时间窗口模式,使算法既能体现数据流的时态特征,又能反映数据流的分布特征。实验结果表明,两种算法在聚类精确度、稳定性方面均高于OSKM算法,而且具有较好的伸缩性和可扩展性。     

基于衰减滑动窗口数据流聚类算法研究

数据流具有数据流量大、流量连续且快速、难以存储和恢复等特性,其挖掘质量和效率是检验挖掘算法的重要标准.传统的数据流聚类挖掘算法是基于界标窗口、滑动窗口和衰减窗口模型,其算法的聚类质量较差,时间复杂度高等不足,就此类问题,研究一种滑动衰减窗口的数据流聚类算法,并对算法进行了设计与实现,有效的改善传统数据流算法聚类质量和时间效率的问题.仿真实验结果表明了该算法的有效性,达到了较满意的效果.     

有限通信资源下多数据流连接的降载算法

针对数据源节点通信资源十分有限的缺陷,提出一种基于直方图的多数据流滑动窗口连接查询的降载策略。该算法综合中心处理节点和数据源节点的负载情况,给出降载比例计算公式,通过使用聚类技术构建中心直方图和数据源直方图,给出降载策略。结果证明该算法能够产生精确连接结果的极大子集,对多数据流窗口连接降载是高效的。     

数据流最大频繁项挖掘方法

提出基于事务矩阵挖掘最大频繁项集的方法AFMI,该方法采取迭代精简事务矩阵的方式求解所有事务中的最大频繁项集,从精简后的事务向量交集的子集中搜索最大频繁项集,并运用逻辑运算和剪枝方法提高挖掘效率。基于AFMI方法,研究挖掘滑动窗口数据流最大频繁项集算法AFMI+,该算法可使用户周期性地挖掘当前窗口中的最大频繁项集。实验结果表明,AFMI和AFMI+算法均具有较好的性能。     

基于形态特征的数据流聚类方法研究

在聚类过程中为保留数据的重要形态与趋势特征,提出一种基于形态特征的数据流聚类方法。在初始化阶段提取重要特征点表示序列分段,在在线更新阶段使用部分动态时间弯曲方法计算子序列距离,基于动态滑动窗口思想保证多条数据流中数据的同步,在用户触发聚类阶段提出数据流聚类方法。通过对仿真数据和实际股票数据的分析结果表明,在参数设置合理的情况下,该方法可以获得接近0.95的聚类演化精度。     

滑动窗口数据流聚类算法在IDS中的应用

针对传统入侵检测系统难于适应日益增长数据量对实时处理能力的需求问题,运用滑动窗口、数据流聚类技术,设计了基于滑动窗口数据流聚类算法,并构建了基于该算法的IDS网络安全防御模型。通过对该模型仿真验证,证明该网络安全防御模型能较好地适应高速网络的入侵检测需求。     

面向海量数据流的基于密度的簇结构挖掘算法

提出一种基于密度的簇结构挖掘算法(mining density-based clustering structure over data streams,简称MCluStream),以解决数据流密度聚类中输入参数选择困难和重叠簇识别等问题.首先,设计了一种树拓扑CR-Tree索引结构,将直接核心可达的一对数据点映射成树结构中的父子关系,蕴含了数据点依赖关系的CR-Tree涵盖了一系列subEps参数下的基于密度的簇结构;其次,MCluStream算法采用滑动窗口的方式更新CR-Tree,在线维护当前窗口上的簇结构,实现了对海量数据流的快速演化聚类分析;再次,设计了一种快速从CR-Tree提取簇结构的方法,根据可视化的簇结构,选择合理的聚类结果;最后,在真实和合成海量数据上的实验验证了MCluStream算法具有有效的挖掘效果、较高的聚类效率和较小的空间开销.MCluStream可适用于海量数据流应用中自适应的密度聚类演化 分析.     

Co-clustering over multiple dynamic data streams based on non-negative matrix factorization

Clustering multiple data streams has become an active area of research with many practical applications. Most of the early work in this area focused on one-sided clustering, i.e., clustering data streams based on feature correlation. However, recent research has shown that data streams can be grouped based on the distribution of their features, while features can be grouped based on their distribution across data streams. In this paper, an evolutionary clustering algorithm is proposed for multiple data streams using graph regularization non-negative matrix factorization (EC-NMF) in which the geometric structure of both the data and feature manifold is considered. Instead of directly clustering multiple data streams periodically, EC-NMF works in the low-rank approximation subspace and incorporates prior knowledge from historic results with temporal smoothness. Furthermore, we develop an iterative algorithm and provide convergence and correctness proofs from a theoretical standpoint. The effectiveness and efficiency of the algorithm are both demonstrated in experiments on real and synthetic data sets. The results show that the proposed EC-NMF algorithm outperforms existing methods for clustering multiple data streams evolving over time.     

动态滑动窗口的数据流聚类方法

数据流聚类是聚类分析中的重要问题。针对数据流的流速是变化的问题,在两阶段聚类框架基础上提出基于动态滑动窗口的数据流聚类算法。在线阶段,引入微聚类特征来存储数据流的概要信息,利用存储的概要信息动态调整滑动窗口规模,并计算数据点与微聚类中心的距离,以维护微聚类特征;离线阶段,对在线聚类阶段的聚类结果采用K-means算法进行宏聚类,生成最终聚类。实验结果表明,该算法具有较高的聚类质量和较好的伸缩性。     

一种基于变尺度滑动窗口的数据流频繁集挖掘算法

基干传统滑动窗口机制的数据流频繁集挖掘算法较多地考虑快速且精确的效果,而较少考虑数据流的时变特性,对传统的滑动窗口机制进行改进.同时考虑数据流的海量特性和时变特性,提出一种基于变尺度滑动窗口机制的数据流频繁集挖掘算法V-Stream.该算法采用事务链表组的概要数据结构.能够根据数据流的数据分布变化自适应调整窗口大小.Eclipse上的仿真实验结果表明,V-Stream相比Manku算法提高了挖掘数据流频繁集的时间与空间效率.