一种挖掘压缩序列模式的高效算法

计算机科学与探索 ›› 2008, Vol. 2 ›› Issue (1): 60-76.

一种挖掘压缩序列模式的高效算法

常雷^1,2+,杨冬青^1,2,王腾蛟^1,2,唐世渭^1,2

1. 北京大学信息科学技术学院，北京 100871
2. 高可信软件技术教育部重点实验室，北京 100871

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20
通讯作者: 常雷

An effective algorithm for mining compressed sequential patterns

CHANG Lei^1,2+, YANG Dongqing^1,2, WANG Tengjiao^1,2, TANG Shiwei^1,2

1. School of Electronics Engineering and Computer Science， Peking University， Beijing 100871， China
2. Key Laboratory of High Confidence Software Technologies （Peking University）， Ministry of Education， Beijing 100871， China

Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20
Contact: CHANG Lei

摘要/Abstract

摘要： 研究了如何使用SP-Feature来压缩序列模式。SP-Feature是一种简洁表示序列模式的新颖结构。一种新的相似性度量被用来聚类SP-Feature，同时也给出了SP-Feature的合并方法。基于层次聚类框架，设计了一种有效的挖掘压缩序列模式的算法CSP。在真实和模拟数据上的大量实验表明CSP能够快速有效地压缩序列模式（在稠密数据集上的恢复误差小于4%）。

关键词: 数据挖掘, 序列模式压缩, SP-Feature

Abstract: The problem of how to compress sequential patterns using SP-Features（Sequential Pattern Features） is examined. SP-Feature is a novel structure for representing a set of sequential patterns succinctly. A new similarity measure is proposed for clustering SP-Features and a SP-Feature combination method is designed. Based on the hierarchical clustering framework， an effective algorithm CSP is developed to mine compressed sequential patterns. Extensive experimental results on both real and synthetic datasets show that CSP can compress sequential patterns efficiently and effectively with low restoration error （less than 4% on dense datasets）.

Key words: data mining, sequential pattern compression, SP-Feature

常雷1,2+ ,杨冬青1,2 ,王腾蛟1,2 ,唐世渭1,2 . 一种挖掘压缩序列模式的高效算法[J]. 计算机科学与探索, 2008, 2(1): 60-76.

CHANG Lei^1,2+, YANG Dongqing^1,2, WANG Tengjiao^1,2, TANG Shiwei^1,2. An effective algorithm for mining compressed sequential patterns[J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(1): 60-76.

[1]	孙冬璞, 曲丽. 时间序列特征表示与相似性度量研究综述[J]. 计算机科学与探索, 2021, 15(2): 195-205.
[2]	王光耀, 王丽珍, 杨培忠, 陈红梅. 极小负co-location模式及有效的挖掘算法[J]. 计算机科学与探索, 2021, 15(2): 366-378.
[3]	储传鑫，王丽珍，周丽华，李旭阳. 恶性肿瘤与工业污染之间的模糊关系挖掘[J]. 计算机科学与探索, 2020, 14(12): 2061-2071.
[4]	王素琴，吴子锐. 利用LSTM网络和课程关联分类的推荐模型[J]. 计算机科学与探索, 2019, 13(8): 1380-1389.
[5]	周凯文，杨智慧，马会心，何震瀛，荆一楠，王晓阳. 面向特定划分的主题模型的设计与实现[J]. 计算机科学与探索, 2018, 12(7): 1036-1046.
[6]	舒敏，刘华文，郑忠龙，徐晓丹. 结合局部敏感哈希和随机游走的异常检测算法[J]. 计算机科学与探索, 2018, 12(12): 1950-1960.
[7]	韩楠，乔少杰，李天瑞，宫兴伟，舒红平，元昌安. 面向复杂网络的中药方剂配伍规律挖掘算法[J]. 计算机科学与探索, 2017, 11(7): 1159-1165.
[8]	陆莉莉，张永潘，谈海宇，季一木. 大数据分类挖掘算法及其概念漂移应用研究[J]. 计算机科学与探索, 2016, 10(12): 1683-1692.
[9]	沈琰辉，刘华文，徐晓丹，赵建民，陈中育. 基于邻域离散度的异常点检测算法[J]. 计算机科学与探索, 2016, 10(12): 1763-1772.
[10]	李亚芳，贾彩燕，于剑. 应用非负矩阵分解模型的社区发现方法综述[J]. 计算机科学与探索, 2016, 10(1): 1-13.
[11]	王虹旭，吴斌，刘旸. 基于Spark的并行图数据分析系统[J]. 计算机科学与探索, 2015, 9(9): 1066-1074.
[12]	米允龙，米春桥，刘文奇. 海量数据挖掘过程相关技术研究进展[J]. 计算机科学与探索, 2015, 9(6): 641-659.
[13]	刘冶，印鉴，邓泽亚，王智圣，潘炎. 基于低秩和局部约束矩阵估计的链接预测方法[J]. 计算机科学与探索, 2015, 9(3): 279-291.
[14]	曹科研，王国仁，韩东红，李硕儒. 不确定数据流上Top-k异常点查询算法[J]. 计算机科学与探索, 2015, 9(2): 172-181.
[15]	魏秀参，慕鑫，杨杨 . 二次集成学习在医疗数据挖掘中的应用[J]. 计算机科学与探索, 2014, 8(9): 1113-1119.