关键词: 点击流相似度，算法设计，计算复杂度

Abstract: Clickstream is widely used in Web usage mining. Clickstream similarity is usually used to classify or cluster Web user sessions. SSK(string subsequence kernel) is an approach for computing string similarity originally. Then it is introduced to compute chckstream similarity and becomes one of the most popular methods. It selects all subsequences of length k of two strings to generate the feature space. A single value of k may cause a problem that the number of features is not enough to get an accurate clickstrcam similarity. So, a new approach to compute clickstream similarity ESSK (extended string subsequcnce kernel) was proposed. ESSK generates the feature space by all subsequences to solve the problem of SSK. To reduce the complexity of computation, an effective algorithm to compute ESSK was proposed. An experiment indicates that ESSK is more accurate than SSK and has a higher discrimination than other approaches. So it is more suitable to compute clickstrcam similarity.

Key words: Clickstream similarity, Design of algorithm, Computation complexity