基于后缀树词序列核挖掘Web文档

通过将文档表示为一棵后缀树,文章提出一种基于后缀树索引计算文档相似度的词序列核.首先根据文档的词序列构造出后缀树,然后根据后缀树词序列核计算文档间的相似度,最后利用支持向量机对文档进行分类.理论分析表明后缀树词序列核的计算只与比较文档的长度成线性关系,大大减少了序列核的计算时间.在reuters21578文档集上将后缀树词序列核与词序列核、多项式核进行比较,实验结果表明在改善速度的同时,后缀树词序列核可达到与词序列核相当的性能,优于多项式核,更适于Web文档挖掘等应用.

Suffix-Tree Word Sequence Kernel for Web Document Mining

The use of string kernel (SK) and word sequence kernel (WSK) are novel ways of computing document similarity based on matching non-consecutive subsequences of characters, but the computing time of those kernels is expensive. This paper presents suffix tree word sequence kernel (STWSK), a modified word sequence kernel to compute the similarity of documents. To compute the new kernel, at first, suffix trees of documents are constructed with suffix tree constructing algorithm, and then the word sequence kernel is computed based on the suffix trees. With STWSK, the documents can be categorized using Support Vector Machine fast and efficiently. The theory analysis shows that the computing time of STWSK is linear to the length of the compared documents, which is less than that of SK and WSK obviously. We compare the classification performance of STWSK with WSK and polynomial kernel (PK) on Reuters-21578 text dataset. The experiment results show that STWSK is better than PK, and is not worse than WSK. So STWSK is more appropriate to the real Web documents mining tasks.