符号序列的概率向量聚类方法*

针对符号序列聚类中表示模型及序列间距离度量定义的困难问题,提出一种基于概率向量的表示模型及基于该模型的符号序列聚类算法。该模型引入符号序列的概率分布表示法,定义了一种基于概率分布差异的符号序列距离度量及该模型的目标函数,最后给出了一种符号序列K-均值型聚类算法,并在来自不同领域的实际应用序列集上进行了实验验证。实验结果表明,与基于子序列表示模型的符号序列聚类算法相比,所提方法在DNA序列和语音序列等具有较多符号的实际数据上,有效提高聚类精度的同时降低聚类时间50%以上。     

基于趋势的时间序列相似性度量和聚类研究

由于时间序列的长度很大,并且不确定时间序列在每个采样点的取值具有不确定性,导致时间序列在相似性匹配和聚类挖掘中时间复杂度很高,为了解决该问题,提出了基于趋势的时间序列相似性度量方法和聚类方法.其中基于趋势的相似性度量方法根据时间序列的整体变化趋势,将时间序列映射为短的趋势符号序列,并利用各趋势的一阶连接性指数和塔尼莫特系数完成相似性度量;基于趋势的聚类方法通过定义趋势高度,并对趋势符号序列迭代进行区间划分和趋势判断,并以此构建趋势树,最后将趋势树根节点中趋势符号相同的序列聚集为一类.实验结果表明:a)五种趋势符号的一阶连接性指数可唯一地表示一条时间序列;b)基于趋势的相似性度量方法在多项式时间内可有效完成时间序列的相似性匹配;c)基于趋势的聚类方法将序列的相似性度量和聚类过程集中在一起,聚类效果显著.     

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

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

流聚类模型及其统一表示

数据流是带有时间属性、持续到达的数据序列,实际中有不同的应用形式。采用应用驱动的研究思路,从具体应用中抽象出4种不同的数据流模型,提取出数据维数和子流个数等2个参数,将各种数据流模型在表示形式上统一起来,分析不同数据流模型的聚类方法,探索并给出一个基于滑动窗口的统一数据流模型聚类挖掘框架。     

RPAA：一种基于时间特性的时间序列建模表示

滑动聚集平均近似PAA（Piecewise Aggregate Approximation）是一种表示时间序列的方法，它通过时间序列上滑动一个等宽的滑动窗口将时间序列分成小的区段。考虑到时间序列的时间特性q-不同区段的影响，本文提出了一种改进表示RPAA（Reversed Piecewise Aggregate Approximation）。RPAA表示对处于不同时间段的序列赋以不同的影响因子，具有线性时间复杂度，并且证明了RPAA满足下界定理，因而能够进行实际的查询。最后的实验表明该表示是有效的。     

基于动态可调衰减滑动窗口的变速数据流聚类算法

在数据流聚类算法中,滑动窗口技术可以及时淘汰历史元组、只关注近期元组,从而改善数据流的聚类效果。如果同时数据流流速无规律地随时间动态变化,原来单纯的滑动窗口技术在解决这类问题时存在缺陷,所以,在充分考虑了滑动窗口大小和数据流流速之间关系的前提下,提出了基于动态可调衰减滑动窗口的变速数据流聚类算法。该算法对历史元组和近期元组分别赋予一定的权重进行处理,然后依据数据流流速的不同函数改变窗口的大小,从而实现数据流的聚类。提出了该数据流聚类算法的数据结构——变异数据流聚类的数据结构。通过真实数据和模拟数据来构造动态变速数据流从而作为验证算法的原始数据。实验结果表明,与Clu Stream聚类算法相比,该方法具有较高的聚类质量、较小的内存开销和较少的聚类处理时间。     

基于变尺度滑动窗口的流数据聚类算法*

针对流数据聚类处理中数据采集的有效性问题,提出了一种基于变尺度滑动窗口的流数据聚类算法。该算法采用动态变化的滑动窗口来采集流数据,以及带有平均时间戳与平均权值的混合指数直方图来支持数据处理,从而能更好地捕获动态变化的流数据。而且增加了聚类的标准,使得流数据的聚类质量得到提高。实验结果表明,该算法提高了流数据的聚类质量。     

基于LDA符号表示的时间序列分类算法

近年来,基于符号表示的时间序列分类方法受到广泛关注,大部分现有方法对原始数据进行符号表示时,没有使用类别的标签信息。提出基于线性判别分析(LDA)的时间序列符号表示方法,考虑最大化类间区分度,使用LDA对原始数据集进行维数约减。再利用信息增益寻找降维后数据的符号投影区间,采用多重系数分箱(MCB)技术将维数约简后数据表示成符号序列。该方法在20个时间序列数据集上的分类效果好于已有方法,有监督的符号表示方法能有效提高分类性能。     

多数据流的增量聚类实现与应用

针对时间序列数据流的增量聚类研究较少的现状,采用多维时态子空间聚类对数据流的增量聚类进行探究。多维时态子空间聚类是指在连续一段时间内,数据流中的值的距离小于2α,它的另一个要求是最后的聚类结果必须包含一定数量的数据流。聚类结果随时间的演变能持续增量地更新,这个更新机制采用滑动窗口的形式,把最早时刻的数据删除后,添加入新到达的数据。采用股票数据对算法进行测试与验证,实验证明,该算法效果较好。     

一种基于DTW的符号化时间序列聚类算法

提出了一种基于DTW的符号化时间序列聚类算法,对降维后得到的不等长符号时间序列进行聚类。该算法首先对时间序列进行降维处理,提取时间序列的关键点,并对其进行符号化;其次利用DTW方法进行相似度计算;最后利用Normal矩阵和FCM方法进行聚类分析。实验结果表明,将DTW方法应用在关键点提取之后的符号化时间序列上,聚类结果的准确率有较好大提高。     

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

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

Catching the Trend: A Framework for Clustering Concept-Drifting Categorical Data

Although the problem of clustering numerical time-evolving data is well-explored, the problem of clustering categorical time-evolving data remains as a challenge issue. In this paper, we propose a generalized clustering framework which utilizes existing clustering algorithms and adopts sliding window technique to detect if there is a drifting-concept or not in the incoming sliding window. The framework is composed of two algorithms: Drifting Concept Detecting (abbreviated as DCD) algorithm detecting the changes of cluster distributions between the current sliding window and the last clustering result, and Cluster Relationship Analysis (abbreviated as CRA) algorithm analyzing the relationship between clustering results at different time. In DCD, the concept is said to drift if quite a large number of outliers are found in the current sliding window, or if quite a large number of clusters are varied in the ratio of data points. The drifted sliding window will perform re-clustering to capture the recent concept. In CRA, a visualizing method is devised to facilitate the observation of the evolving clustering results. The framework is validated on real and synthetic data sets, and is shown to not only accurately detect the drifting-concepts but also attain clustering results of better quality.     

Online-HHT方法在时间序列数据流预测中的应用

在研究已有时间序列数据流预测方法的前提下,给出了一种基于滑动窗口的时间序列数据流通用预测模型,提出能有效降噪并进行多尺度滑动窗口分析,进而进行预测的新方法Online-HHT,将数据流中的滑动窗口技术与HHT方法相结合从而达到在线分析的目的。使用此模型,通过实验证实了Online-HHT方法能够有效地对时序数据流进行在线自适应趋势预测。     

图像搜索结果的滑动窗口多标记传播聚类

针对图像聚类中数据量大、部分重叠等问题,提出一种基于滑动窗口的多标记传播聚类算法。首先根据图像距离计算图像间的相似度,设定阈值将相似度转变为链接,构造出一个无向图;然后应用基于滑动窗口的多标记传播算法对无向图进行社区划分。滑动窗口可以存放多个标记,从而一个图像可以归属于多个类别。对公开网络数据和搜索引擎返回的真实图像数据进行实验,结果表明,该方法能有效发现具有重叠划分的簇,且簇的意义比较明确。     

基于核估计和区间聚类的数据流中异常模式发现

研究数据流中异常模式发现问题。为保证可以随时输出当前的异常模式,引入一种简单且有效的数据结构——三层时间区间嵌套模式(TTI),来监测数据流。对新到数据是否为异常加以判断评价的标准不是预先分配的静止阈值,而是由算法(KIC:核估计和置信区间聚类分析)计算得到的动态阈值,从而在仅占用很小内存的前提下提高了算法的准确性。设计的SWMA算法进一步降低了时间和空间复杂度。最后分别在模拟线性模型、非线性模型及带时间戳的真实数据流上对方法的准确性、可行性和时效性进行了验证。     

基于粒子群优化算法的数据流聚类算法

针对当前基于滑动窗口的聚类算法中对原始数据信息的损失问题和提高聚类质量和准确性,在现有基于滑动窗口模型数据流聚类算法的基础上,提出了一种基于群体协作的粒子群优化算法（PSO）的新数据流聚类算法。这种优化的新数据流聚类算法利用改进的时间聚类特征指数直方图作为数据流的概要结构以及应用PSO在聚类过程中对聚类质量的局部迭代优化。实验结果表明,此方法有效减少了内存的开销,解决了对原始数据信息损失的问题。与传统的数据流聚类算法相比,基于粒子群优化算法的数据流聚类算法在聚类质量和准确性上明显优于传统的数据流聚类算法。     

基于滑动窗口的XML数据流聚类算法

通过对XML数据流的聚类研究,提出一种基于滑动窗口的XML数据流聚类算法SW-XSCLS。该算法采用滑动窗口技术,以聚类特征指数直方图作为概要数据结构,能动态地淘汰“过时”的数据,较好地保存当前窗口内的数据分布状况,从而获取较高质量的聚类结果。理论分析和实验结果表明,该算法可以获得较高的聚类质量和较快的处理速度。     

基于多目标检测与跟踪的密集客流检测

针对密集交通场景中的客流检测问题,提出了基于支持向量机(SVM)多目标检测与Mean Shift跟踪相结合的方法.首先采用自适应检测窗口提取梯度方向直方图,经过SVM分类和聚类算法,得到头部图像初始假设.然后采用Mean Shift算法,对头部假设进行跟踪,得到连续的头部图像序列.通过SVM分类器对序列图像进行整体判断,得到客流信息.实验结果表明,自适应滑动窗口的方法减少了特征提取阶段的处理时间,提高了检测速度;同时,通过对得到的跟踪序列进行整体判别,客流量的检测精度得到了提高.