最老程序員閆濤

無論是要進(jìn)行全文檢索，還是對(duì)文章進(jìn)行自動(dòng)聚類分析，都需要將文章表示為術(shù)語向量（Term Vector），在Lucene內(nèi)部就是通過術(shù)語向量來對(duì)文章進(jìn)行索引和搜索的，但是Lucene沒有向外提供合適的術(shù)語向量計(jì)算接口，所以對(duì)術(shù)語向量計(jì)算還必須我們自己來做。

術(shù)語向量解述

眾所周知，一篇文章由一個(gè)個(gè)的單詞組成，我們?cè)谶M(jìn)行文本處理時(shí)，首先進(jìn)行中文分詞，包括去除“的、地、得”等常用停止詞，對(duì)關(guān)鍵詞加上同義詞，如縮寫和全稱，如果是英文可能還需要變?yōu)樾懀コ龔?fù)數(shù)和過去分詞等，可能還需要提取詞根，總之經(jīng)過上述步聚的預(yù)處理，文章將變成由一系列單詞組成的字符串?dāng)?shù)組。

對(duì)一系統(tǒng)中的每一篇文章，我們首先計(jì)算每個(gè)單詞的出現(xiàn)頻率（TF：TermFrequency），即該單詞出現(xiàn)的次數(shù)除以文章總單詞數(shù)，然后統(tǒng)計(jì)這個(gè)單詞的反比文檔頻率（IDF：Inverse Document Frequency），在所有文章中出現(xiàn)的次數(shù)，并用該數(shù)除文章總數(shù)，即總文章數(shù)除以出現(xiàn)該單詞文章的數(shù)目。由上面的定義可以看出，單詞越重要，他的單詞出現(xiàn)頻率TF就越高，單詞越是只在這篇文章中出現(xiàn)，很少在其它文章中出現(xiàn)，那該單詞越對(duì)本篇文章具有重要意義。通過一定的公式，可以計(jì)算出每個(gè)單詞的對(duì)每篇文章的權(quán)重，這樣所有單詞加上其對(duì)應(yīng)的權(quán)重，就形成了一個(gè)多維術(shù)語向量。

計(jì)算TF*IDF

對(duì)于術(shù)語向量的計(jì)算方法，目前還沒有特別成熟的算法，現(xiàn)在常用的只是一些經(jīng)驗(yàn)算法，一些文章中提出的號(hào)稱更加準(zhǔn)確的算法，還沒有經(jīng)過實(shí)際驗(yàn)證。我們?cè)谶@里采用的是當(dāng)前最常用的算法，根據(jù)實(shí)際需要對(duì)這些算法進(jìn)行修正也是相當(dāng)簡單的。

首先系統(tǒng)需要維護(hù)幾個(gè)全局變量：總文章數(shù)、系統(tǒng)中所有單詞以及其在文章中出現(xiàn)的次數(shù)

// 因?yàn)閱卧~出現(xiàn)在文章的不同位置重要性不同，可以設(shè)置不同的權(quán)重
public final static int TITLE_WEIGHT = 1;
public final static int KEYWORD_WEIGHT = 1;
public final static int TAG_WEIGHT = 1;
public final static int ABCT_WEIGHT = 1;
public final static int BODY_WEIGHT = 1;

private static int docsNum = 0; // 目前系統(tǒng)中的總文檔數(shù)，將來需要存在數(shù)據(jù)庫中
private static Map<String, Integer> wordDocs = null; // 每個(gè)單詞在所有的每篇文章中出現(xiàn)的文章個(gè)數(shù)（文章數(shù)）
private static Vector<Integer> termNumDoc = null; // 每篇文章的總單詞數(shù)
private static Vector<Vector<TermInfo>> termVectors = null; // 每篇文章的術(shù)語向量表示

然后是對(duì)一段文本產(chǎn)生術(shù)語原始術(shù)語向量的程序，如下所示：
/**
* 一篇文章分為標(biāo)題、關(guān)鍵字、摘要、標(biāo)志、正文幾個(gè)部分組成，每個(gè)部分的單詞具有不同的權(quán)重，通過
* 本函數(shù)進(jìn)行中文分詞，同時(shí)生成該部分的術(shù)語向量
* @param text 需要處理的文本
* @param termArray 術(shù)語向量
* @param weight 單詞在本部分的權(quán)重
* @return 本部分的單總數(shù)（用于計(jì)算單詞出現(xiàn)頻率TF）
*/
private static int procDocPart(String text, Vector<TermInfo> termArray, int weight) {
Collection<String> words = FteEngine.tokenize(text);
Iterator<String> itr = words.iterator();
String word = null;
TermInfo termInfo = null;
int termMount = 0;
while (itr.hasNext()) {
word = itr.next();
if (termArray.contains(word)) {
termInfo = termArray.get(termArray.indexOf(word));
termInfo.setMountPerDoc(termInfo.getMountPerDoc() + weight);
} else {
termInfo = new TermInfo();
termInfo.setMountPerDoc(weight);
termInfo.setTermStr(word);
termInfo.setRawWeight(0.0);
termInfo.setWeight(0.0);
termArray.add(termInfo);
}
termMount += weight;
}
return termMount;
}

下面是求出TF*IDF然后進(jìn)行歸一化生成最終術(shù)語向量的程序：

/**
* 對(duì)標(biāo)題、關(guān)鍵字、標(biāo)記、摘要、正文采用迭加方式生成術(shù)語向量
* @param docIdx 文檔編號(hào)，為-1時(shí)表示新加入的文檔
* @param text 需要處理的文本
* @param weight 本段文本單詞出現(xiàn)的權(quán)重
* @return 文檔編號(hào)
*/
public static int genTermVector(int docIdx, String text, int weight) {
Vector<TermInfo> termVector = null;
if (docIdx < 0) {
docIdx = docsNum;
termNumDoc.add(0);
termVector = new Vector<TermInfo>();
termVectors.add(termVector);
docsNum++;
}
termVector = termVectors.elementAt(docIdx);
int termMount = procDocPart(text, termVector, weight);
termNumDoc.set(docIdx, termNumDoc.elementAt(docIdx).intValue() + termMount);
// 計(jì)算所有術(shù)語的IDF
TermInfo termInfo = null;
String termStr = null;
Iterator<TermInfo> termInfoItr = termVector.iterator();
// 計(jì)算每個(gè)單詞在文章中出現(xiàn)的篇數(shù)
while (termInfoItr.hasNext()) {
termInfo = termInfoItr.next();
termStr = termInfo.getTermStr();
if (wordDocs.get(termStr) != null) {
wordDocs.put(termStr, wordDocs.get(termStr).intValue() + 1);
} else {
wordDocs.put(termStr, 1);
}
termInfo.setTf(termInfo.getMountPerDoc() / ((double)termNumDoc.elementAt(docIdx).intValue()));
}
Iterator<Vector<TermInfo>> docItr = termVectors.iterator();
// 計(jì)算TF*IDF
double rwPSum = 0.0;
while (docItr.hasNext()) {
termVector = docItr.next();
termInfoItr = termVector.iterator();
rwPSum = 0.0;
while (termInfoItr.hasNext()) {
termInfo = termInfoItr.next();
termInfo.setRawWeight(termInfo.getTf() * Math.log(((double)docsNum) /
wordDocs.get(termInfo.getTermStr()).intValue()));
rwPSum += termInfo.getRawWeight() * termInfo.getRawWeight();
}
// 對(duì)TF*IDF進(jìn)行歸一化
termInfoItr = termVector.iterator();
while (termInfoItr.hasNext()) {
termInfo = termInfoItr.next();
termInfo.setWeight(termInfo.getRawWeight() / Math.sqrt(rwPSum));
}
}
return docIdx;
}

文章相似度計(jì)算

文章的相似度就是要計(jì)處兩篇文章對(duì)應(yīng)的術(shù)語向量的距離，也就是對(duì)應(yīng)各個(gè)術(shù)語歸一化后的TF*IDF的權(quán)重差的平方合再開發(fā)，類似于二維矢量距離的計(jì)算，具體實(shí)現(xiàn)代碼如下所示：

/**
* 計(jì)算術(shù)語向量的距離，該值小則表明兩篇文章相似度高
* @param termVector1
* @param termVector2
* @return 距離
*/
public static double calTermVectorDist(Collection<TermInfo> termVector1, Collection<TermInfo> termVector2) {
double dist = 0.0;
Vector<TermInfo> tv1 = (Vector<TermInfo>)termVector1;
Vector<TermInfo> tv2 = (Vector<TermInfo>)termVector2;
Hashtable<String, TermInfo> tv2Tbl = new Hashtable<String, TermInfo>();
Iterator<TermInfo> tvItr = null;
TermInfo termInfo = null;
TermInfo ti2 = null;
double[] weights = new double [tv2.size()];
int idx = 0;
// 初始化數(shù)據(jù)
tvItr = tv2.iterator();
while (tvItr.hasNext()) {
termInfo = tvItr.next();
//weights[idx++] = termInfo.getWeight();
tv2Tbl.put(termInfo.getTermStr(), termInfo);
}
//
tvItr = tv1.iterator();
while (tvItr.hasNext()) {
termInfo = tvItr.next();
ti2 = tv2Tbl.get(termInfo.getTermStr());
if (ti2 != null) {
dist += (termInfo.getWeight() - ti2.getWeight()) * (termInfo.getWeight() - ti2.getWeight());
ti2.setWeight(0.0);
} else {
dist += termInfo.getWeight() * termInfo.getWeight();
}
}
tvItr = tv2Tbl.values().iterator();
while (tvItr.hasNext()) {
termInfo = tvItr.next();
System.out.println("######: " + termInfo.getTermStr() + "=" + termInfo.getWeight() + "!");
dist += termInfo.getWeight() * termInfo.getWeight();
}
System.out.println();

return Math.sqrt(dist);
}

下面對(duì)以下三句話進(jìn)行計(jì)算：

Java語言編程技術(shù)詳解

C++語言編程指南

同性戀網(wǎng)站變身電子商務(wù)網(wǎng)站

計(jì)算的術(shù)語向量值為：

java:0.5527962688403749
語言:0.20402065516569604
編程:0.20402065516569604
技術(shù):0.5527962688403749
詳解:0.5527962688403749
############## doc2 ############
c:0.6633689723434504 （注：我們的詞典中沒有C++）
語言:0.24482975009584626
編程:0.24482975009584626
指南:0.6633689723434504
############## doc3 ############
同性戀:0.531130184813292
網(wǎng):0.196024348194679
站:0.196024348194679
變身:0.531130184813292
電子商務(wù):0.531130184813292
網(wǎng):0.196024348194679
站:0.196024348194679

然后計(jì)算距離為：

第一篇與第二篇：1.3417148340558687

第一篇與第三篇：1.3867764455130116

因此通過計(jì)算結(jié)果系統(tǒng)會(huì)認(rèn)為第一篇和第二篇更接近，實(shí)際情況也是如此，因?yàn)榈谝黄偷诙g有兩個(gè)單詞是相同的，而第一篇和第三篇間則沒有任何相同的地方。