面向热点话题时间序列的有效聚类算法研究

被引：31

作者：

韩忠明 ^{[1
]}

陈妮 ^{[1
]}

乐嘉锦 ^{[2
]}

段大高 ^{[1
]}

孙践知 ^{[1
]}

机构：

[1] 北京工商大学计算机与信息工程学院

[2] 东华大学计算机科学与技术学院

来源：

计算机学报 | 2012年 / 35卷 / 11期

关键词：

聚类; 时间序列; 热点话题; 小波;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

聚类热度时间序列是揭示和建模网络热点话题形成与发展的重要过程.Leskovec等人在2010年提出面向话题时间序列的KSC聚类算法,其精确度较高且能较好地刻画话题内在发展趋势特征.但KSC算法具有对初始类矩阵中心高度敏感、高时间复杂度等特性,使其难以在实际高维大数据集上应用.文中结合小波变换技术,提出一个新的迭代式聚类算法WKSC,主要提出两个创新:（1）用Haar小波变换将原始时间序列进行压缩,降低原始时间序列的维度,从而降低了算法的时间复杂度;（2）在Haar反小波变换中,将低维聚类返回得到的矩阵中心作为高维聚类的初始矩阵中心,在迭代聚类过程中优化了对初始矩阵中心高敏感性的问题,提高了聚类的效果.文中分别采用国内外3个数据集作为测试样本,进行了大量的实验.实验结果表明WKSC算法能显著降低聚类的时间复杂度,同时改进聚类效果.WKSC算法可很好的应用于大量高维热点话题的模式分析.

引用

页码：2337 / 2347

页数：11

共 8 条

[1] 基于整体和局部相似性的序列聚类算法 [J].

戴东波 ;

汤春蕾 ;

熊赟 .

软件学报, 2010, 21 (04) :702-717

[2] 时间序列分类问题的算法比较 [J].

杨一鸣 ;

潘嵘 ;

潘嘉林 ;

杨强 ;

李磊 .

计算机学报, 2007, (08) :1259-1266

[3] 基于斜率提取边缘点的时间序列分段线性表示方法 [J].

詹艳艳 ;

徐荣聪 ;

陈晓云 .

计算机科学, 2006, (11) :139-142+161

[4] 在线分割时间序列数据 [J].

李爱国 ;

覃征 .

软件学报, 2004, (11) :1671-1679

[5] 面向数据挖掘的时间序列符号化方法研究 [J].

李斌 ;

谭立湘 ;

章劲松 ;

庄镇泉 .

电路与系统学报, 2000, (02) :9-14

[6] Predicting the Popularity of Online Content [J].

Szabo, Gabor ;

Huberman, Bernardo A. .

COMMUNICATIONS OF THE ACM, 2010, 53 (08) :80-88

[7]

On the Bursty Evolution of Blogspace[J] . Ravi Kumar,Jasmine Novak,Prabhakar Raghavan,Andrew Tomkins.World Wide Web . 2005 (2)

[8]

On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration[J] . Eamonn Keogh,Shruti Kasetty.Data Mining and Knowledge Discovery . 2003 (4)

← 1 →