A New Suffix Tree Similarity Measure for Document Clustering

A New Suffix Tree Similarity Measure for Document Clustering

這篇論文想做的是關於文章的自動分群，使用的是結合Suffix Tree和Vector Space Document的方法，作者稱之為NSTC(new suffix tree document clustering algorithm)。

作者在論文中首先介紹了一個在1998年所提出的STC(suffix tree document clustering algorithm)，STC主要可分為三個步驟，第一是產生document的suffix tree，找出內部節點做為base cluster，第二步是base cluster 挑選，第三步是依據Jaccord coefficient來決定node是否具有direct link，最後各個connected graph即為分群的結果。換句話說，我們得到的是base cluster(相當於片語)的分群的結果, 任何文件若有包含這些片語，即會被歸為同一群，因此一個文件可能在不同群中出現．

而NSTC號稱欲將STC導入Vector Space Document，其做法於STC做完第二步後，以tfidf來算一個node在document的重要性，再以cosine來算document間的相似度，最後以這些相似度來做GAHC(Group-average Agglomerative Hierarchical Clustering)。因此其分群方法其實已經不同於STC所用的graph partitioning．好處是可以利用分群中的node來做為cluster的summary描述，但是這個好處在最後的實驗當中並不是很明顯。

最後的實驗裡，作者拿了STC和NSTC與傳統的GAHC做個比較，並以F-Measure做為評量的標準，發現NSTC確實相較於其他兩者有較好的表現。 但是終歸比較的是同樣的分群方法GAHC，只是表示方法一個是用node(片語)一個是用single term，似乎貢獻不大．　

WWW 2007 Banff, Alberta, Canada. pp. 121 - 130.