基于符号熵的序列相似性度量方法

Sequence Similarity Measurement Method Based on Symbol Entropy

现有序列相似性度量算法在子序列相似性度量中仅考虑其局部相似度,忽略了其所属序列的整体结构信息。为此,提出一种以单个符号的熵为基础的序列相似性度量方法,根据同一序列中相同符号的位置及个数信息得出符号熵。通过凝聚型层次聚类结果验证序列相似性度量方法,在多个领域的符号序列数据集上的实验结果表明,与现有的基于子序列局部相似性方法相比,该相似性度量方法有效提高了聚类结果质量。

Existing sequence similarity measurement algorithms only consider the local similarity of subsequences, ignoring global structure information. Thus,a similarity measurement method based on the entropy of single symbol for sequences is proposed. The entropy of a symbol is computed according to the positions and numbers of all the same symbols in a sequence. Through verifying the validity of the new sequence similarity measurement method by agglomerative hierarchical clustering, experimental results on a plurality of datasets show that, compared with the existing methods based on local similarity of substring, the new similarity measurement method can improve the clustering accuracy significantly.