Rocchio算法

Rocchio 算法，是一種高效的分類算法，廣泛地被套用到文本分類，查詢擴展等領域。它通過構造原型向量的方法得到最優解

基本介紹

• 中文名：Rocchio算法
• 性質：分類算法
• 套用：文本分類，查詢擴展等領域
• 出現時間：20世紀70年代
• 出現位置：Salton的SMART系統
• 方法：構造原型向量

算法簡介

Rocchio算法是IR中通過查詢的初始匹配文檔對原始查詢進行修改以最佳化查詢的方法。Rocchio 算法。該算法（Rocchio，1971）是20 世紀70 年代左右在Salton 的SMART 系統中引入並廣泛流傳的一種相關反饋算法。

算法原理

其基本思想是使用訓練集為每個類構造一個原型向量，構造方法如下：

給定一個類，訓練集中所有屬於這個類的文檔對應向量的分量用正數表示，所有不屬於這個類的文檔對應向量的分量用負數表示，然後把所有的向量加起來，得到的和向量就是這個類的原型向量，定義兩個向量的相似度為這兩個向量夾角的餘弦，逐一計算訓練集中所有文檔和原型向量的相似度，然後按一定的算法從中挑選某個相似度作為界。給定一篇文檔，如果這篇文檔與原型向量的相似度比較大，則這篇文檔屬於這個類，否則這篇文檔就不屬於這個類。Rocchio算法的突出優點是容易實現，計算（訓練和分類）特別簡單，它通常用來實現衡量分類系統性能的基準系統，而實用的分類系統很少採用這種算法解決具體的分類問題。

其基本思想不難解釋,對於一個詞集,和一個分類,總有某些詞,這些詞一旦出現屬於這個分類的可能性就會增加,而另一些詞一旦出現屬於這個分類的可能性就會降低,那么累計這些正面的,和負面的影響因素,最後由文檔分離出的詞向量可以得到對於每個類的一個打分,打分越高屬於該類的可能性就越大.

對於某種二分類特別合適, A, ~A, 任給一個文檔,判斷屬於分類A還是分類~A,可以認為A的特徵項均給與正值,~A都給與負值,那么給定一個合理閾值,就很容易做出這種類型的分類.

算法套用

文本分類

Rocchio算法應該算是人們思考文本分類問題時最先能想到，也最符合直覺的解決方法。基本的思路是把一個類別里的樣本文檔各項取個平均值（例如把所有 “體育”類文檔中辭彙“籃球”出現的次數取個平均值，再把“裁判”取個平均值，依次做下去），可以得到一個新的向量，形象的稱之為“質心”，質心就成了這 個類別最具代表性的向量表示。再有新文檔需要判斷的時候，比較新文檔和質心有多么相像（八股點說，判斷他們之間的距離）就可以確定新文檔屬不屬於這個類。 稍微改進一點的Rocchio算法不僅考慮屬於這個類別的文檔（稱為正樣本），也考慮不屬於這個類別的文檔數據（稱為負樣本），計算出來的質心儘量靠近正樣本同時儘量遠離負樣本。

查詢擴展

Rocchio算法是IR中通過查詢的初始匹配文檔對原始查詢進行修改以最佳化查詢的方法。Rocchio 算法是相關反饋實現中的一個經典算法，它提供了一種將相關反饋信息融到向量空間模型的方法。

基本理論：假定我們要找一個最優查詢向量q ，它與相關文檔之間的相似度最大且同時又和不相關文檔之間的相似度最小。