基于整体和局部相似性的序列聚类算法

被引：16

作者：

戴东波

汤春蕾

熊赟

机构：

[1] 复旦大学计算机科学技术学院

来源：

软件学报 | 2010年 / 21卷 / 04期

关键词：

序列数据; 相似性; 聚类;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

现有的很多序列聚类算法是基于"局部特征可以表征整个序列"的假设来进行的,即不区分实际应用中序列的整体相似性和局部相似性.这对存在保守子模式的序列,如DNA和蛋白质序列是适用的,但对一些注重整体序列相似性的应用领域,如:在交易数据库中用户购买行为的比较,时间序列数据中全局模式的匹配等,由于难以产生频繁子模式,用基于全局相似性的度量方法进行聚类显得更为合理.此外,在基于局部相似性的序列聚类算法中,选取的局部子模式表征序列的能力也有待进一步提高.由此,针对不同应用领域,分别提出基于整体相似性的序列聚类算法GSClu和基于局部相似性的序列聚类算法LSClu.GSClu和LSClu分别利用带剪枝策略的二分k均值算法和基于有gap约束的强区分度子模式方法对各自领域的序列数据进行聚类.实验采用交易序列数据和蛋白质序列数据,实验结果表明,GSClu和LSClu对各自领域的序列数据具有较快的处理速度和良好的聚类质量.

引用

页码：702 / 717

页数：16

共 7 条

[1] DNA序列数据挖掘技术 [J].

朱扬勇 ;

熊赟 .

软件学报, 2007, (11) :2766-2781

[2] Clustering DNA sequences by feature vectors [J].

Liu, Libin ;

Ho, Yee-kin ;

Yau, Stephen .

MOLECULAR PHYLOGENETICS AND EVOLUTION, 2006, 41 (01) :64-69

[3]

SWORDS: A statistical tool for analysing large DNA sequences[J] . Probal Chaudhuri,Sandip Das.Journal of Biosciences . 2002 (1)

[4] Statistical analysis of large DNA sequences using distribution of DNA words [J].

Chaudhuri, P ;

Das, S .

CURRENT SCIENCE, 2001, 80 (09) :1161-1166

[5]

The power of amnesia: Learning probabilistic automata with variable memory length[J] . Dana Ron,Yoram Singer,Naftali Tishby.Machine Learning . 1997 (2)

[6]

The String-to-String Correction Problem[J] . Robert A. Wagner,Michael J. Fischer.Journal of the ACM (JACM) . 1974 (1)

[7]

Introduction to data mining .2 Tan PN,Steinbach M,Kumar V. Addison-Wesley . 2005

← 1 →