An effective algorithm for mining compressed sequential patterns

Journal of Frontiers of Computer Science and Technology ›› 2008, Vol. 2 ›› Issue (1): 60-76.

• 学术研究 • Previous Articles Next Articles

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

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

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

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

通讯作者: 常雷

Abstract

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

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

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

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

[1]	SUN Dongpu, QU Li. Survey on Feature Representation and Similarity Measurement of Time Series [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(2): 195-205.
[2]	WANG Guangyao, WANG Lizhen, YANG Peizhong, CHEN Hongmei. Minimal Negative Co-location Patterns and Effective Mining Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(2): 366-378.
[3]	CHU Chuanxin, WANG Lizhen, ZHOU Lihua, LI Xuyang. Mining Fuzzy Relationship Between Malignant Tumors and Industrial Pollution [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(12): 2061-2071.
[4]	WANG Suqin, WU Zirui. Recommendation Model Using LSTM Network and Course Association Classification [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(8): 1380-1389.
[5]	ZHOU Kaiwen, YANG Zhihui, MA Huixin, HE Zhenying, JING Yinan, WANG X. Sean. Design and Development of Partitional Topic Model [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(7): 1036-1046.
[6]	SHU Min, LIU Huawen, ZHENG Zhonglong, XU Xiaodan. Outlier Detection Algorithm Combining Locality Sensitive Hashing and Random Walks [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(12): 1950-1960.
[7]	HAN Nan, QIAO Shaojie, LI Tianrui, GONG Xingwei, SHU Hongping, YUAN Chang'an. Prescription Compatibility Mining Algorithm of Traditional Chinese Medicine over Complex Networks [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(7): 1159-1165.
[8]	LU Lili, ZHANG Yongpan, TAN Haiyu, JI Yimu. Research on Classification Algorithm and Concept Drift Based on Big Data [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(12): 1683-1692.
[9]	SHEN Yanhui, LIU Huawen, XU Xiaodan, ZHAO Jianmin, CHEN Zhongyu. Outlier Detection Algorithm Based on Dispersion of Neighbors [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(12): 1763-1772.
[10]	LI Yafang, JIA Caiyan, YU Jian. Survey on Community Detection Algorithms Using Nonnegative Matrix Factorization Model [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(1): 1-13.
[11]	WANG Hongxu, WU Bin, LIU Yang. Parallel Graph Data Analysis System Based on Spark [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(9): 1066-1074.
[12]	MI Yunlong, MI Chunqiao, LIU Wenqi. Research Advance on Related Technology of Massive Data Mining Process [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(6): 641-659.
[13]	LIU Ye, YIN Jian, DENG Zeya, WANG Zhisheng, PAN Yan. Link Prediction with Low-Rank and Local Constraint Matrix Estimation [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(3): 279-291.
[14]	CAO Keyan, WANG Guoren, HAN Donghong, LI Shuoru. Top-k Outlier Detection Algorithm on Uncertain Data Stream [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(2): 172-181.
[15]	WEI Xiushen, MU Xin, YANG Yang . An Application in Medical Data Mining Based on Twice Ensemble Learning [J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(9): 1113-1119.

An effective algorithm for mining compressed sequential patterns

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics