自適應聚類在相關反饋檢索中的應用研究

摘要：自適應聚類就是通過相關反饋學習來提高查詢的精度。把自適應聚類應用到信息檢索中，可以進一步改進查詢結果。本文結合之前人們研究的成果，提出一種自適應聚類學習方案，并且用實驗結果證明了自適應聚類確實可以更好地聚類。

關鍵詞：自適應聚類；相關反饋；目標函數

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044(2008)11-20361-03

1 引言

隨著Internet 技術的迅速發展和進步，Web資源的更新頻率也越來越快，對于大型Web數據庫中數據集的檢索已經有了很多的研究成果，然而太多的信息量需要根據某些屬性進行聚類，聚類算法就是要在預先定義的屬性空間中找出資源的種群。一般是按照某種規則來進行聚類，由于數據集的多變的，最先設定的聚類規則有可能已經不適應變化后的數據集，這就需要利用相關反饋來進行對查詢規則的優化[1]。

相關反饋，是一種自動更新過程。其主要思想是通過來自用戶的對查詢結果進行評估來提高系統性能。對一個給定的查詢，系統給出一系列認為查詢相似（根據查詢規則）的文本或者圖像，然后，用戶挑出與查詢相關性最強的一組文本或圖像，并且讓系統使用這些查詢結果來更新查詢規則。而自適應聚類是通過相關反饋進行迭代自動更新。近年來，相關反饋技術成了各類檢索，包括文本文獻搜索和基于文本和基于內容的圖像檢索研究中最活躍的領域之一。

本文先引用已有的研究成果，然后提出一種自適應聚類方案（利用帶權距離函數和目標函數），然后以實驗證明，自適應聚類的搜索比起一般的無學習的分類聚類方法搜索的優越性。

2 聚類算法

2.1 一般聚類算法

聚類一般分成分類和類合并兩個階段。

分類后，類可以進一步聚為更大的類。類合并的基本思想是，在最初迭代過程中生成的類中，每個類只有一個點；同時考慮兩個類，如果它們不是明顯的不同，就把它們合并到一個類；然后不斷重復這個過程，直到類的數目減少到一定的限度。這個算法需要計算兩個類的相似程度，當相似度小于某個常數c時，則認為這兩個類很相似，從而把這兩個類合并成一個類[3]。

2.2 自適應聚類算法

自適應聚類算法提出對參數自適應的更新的無指導學習方法[4]。自適應聚類與一般聚類的的不同是后者使用了相關反饋，帶有自動學習更新過程。無論在分類階段與還是合并類階段，自適應聚類算法都讓這些類通過查詢結果和用戶的相關反饋進行修改。在分類的過程中，使用相關反饋的統計信息重新劃分類；在合并類的過程中，當前的類的數目被不斷減少。

2.3 聚類算法的質量分析

評測一種聚類算法優劣的最好方法就是計算它的錯誤率，也就是某個樣本被歸到錯誤的類中的可能性。因此，本文的聚類算法的質量分析如下：

由于在最終的迭代環節中，類的數目已經被確定下來，這時可以檢測，在分類過程中，樣本是不是又被分到了以前的類。假設被正確聚類的樣本的數目為C，并且所有的類中樣本的總數目為N，那么錯誤率就是1-C/N。這種方法在類的樣本數比較少的時候也適用[5]。

3 一種評測自適應聚類性能的方案

現設計一套方案來評測自適應算法的性能。 首先我們要引入目標函數[8]，通過以下目標函數，可以計算出搜索的準確度提高了多少，自適應聚類使用外部反饋來提高聚類之類，和使用之前的搜索經驗來加快運行時間。在尋找好的聚類時，在案例學習中，我們把自適應聚類使用到基于實例學習中，通過修改距離函數來實現外部反饋，該實驗主要是關于帶自適應聚類和不帶自適應聚類的1近鄰分類和最近鄰分類算法[7]所得到結果的比較。目標函數如下：

第一步，在最初的迭代中，執行最近鄰查詢。對于一次給定的查詢中，對于每個當前得到的類，計算一下類的質心，協方差和權重。計算公式如下：

根據質心定理[7]，假設第i類第k點的所占的權重的分值為Vik，那么第i類的質心和權重為

由2.1可知協方差為。

第二步，使用集合距離函數來執行k近鄰分類算法。具體做法是，從測試樣本點x開始生長，不斷地擴大區域，直到包含k個訓練樣本點或者這里區域的半徑達到d(Q，x)為止，如果在這里區域的半徑達到d(Q，x)之前就已經包含了k個訓練樣本點，則把測試樣本點x的類別歸為這最近的k個訓練樣本點中出現頻率最大的類別，此時停止查詢迭代。（本實驗用1近鄰和最近鄰分類）

第三步，如果區域的半徑達到d(Q，x)為止，還沒有包含k個樣本點則繼續查詢迭代。

第四步，對于特征空間中的一個新的查詢點，使用自適應聚類方法決定合適的類。（如果在已有的類的邊界以內，則歸入改類，否則歸入不同的類）。

第五步，對于每個當前的類，計算它的質心，協方差和權重。計算公式見第一步。

第六步，利用2.1所示的算法和公式，對于每對（兩個）類，比較它們的特征向量，判斷兩個特征向量的相似度，當相似度小于某個常數c時，則認為這兩個類有交集，從而把這兩個類合并成一個類。

第七步，根據第六步計算所得xi，wi以及Sj重新計算的Q（多查詢點集）的值，然后跳轉到第二步，開始新一輪的迭代。

4 實驗評估

本實驗的目的是為了證明自適應聚類學習方法可以更好地聚類，我們將使用自適應聚類的分類器的結果跟原始的分類器相比較。在實驗中，我們測試三組數據（1）k=C，表長度|K|=1，(2)k=C， 表長度|K|=25，(3) k=5C， 表長度|K|=50，得到以下兩個列表：

上面兩個表顯示了對于實驗中設置的數據，準確結果的標準偏離和平均偏離。

表1比較了1近鄰分類和帶有學習的1近鄰分類。首先，glass數據集隨著L的增大性能一直得以提高。其次，所有的數據集的平均值都在改進。表2比較了最近鄰分類和帶有學習的最近鄰分類。基于這些結果，可以看出自適應聚類極大地影響了分類效果。無論參數怎么變化，數據集的搜索準確度都得到了顯著的提高。

本論文實驗所用的數據集都來自UCI Machine Learning Repository (機器學習庫) [10]。

5 結論

在本文中，我們著重討論了一個自適應聚類學習怎樣改進聚類效果，然后利用目標函數，構建了一套測試方案并且用實驗證明了這一點。自適應聚類通過接受新的聚類和返回值來改變距離函數，并且支持記憶在給定內容中表現良好的類來有效地進行搜索，從而導出數據集中更好的聚類。實驗也說明了自適應聚類改進了已有的給予實例的分類器（1近鄰分類，最近鄰分類）。

本方法存在一定的局限性，有限的數據集并不能完全說明任何情況下都適合用自適應聚類。

參考文獻：

[1] 黃麗瓊，何中市．基于統計語義和結構特征的自動文摘[J ]．廣西師范大學學報：自然科學版，2006，24 (4)：1872190．

[2] I. Bartolini，P.Ciacci，and F. Waas．Feedbackbypass：A new approach to interactive similarity query processing. In Proceedings of the 27th VLDB Conference，pages 201–210．Roma，Italy，September 2001．

[3] Cox， I. J.， Minka， T. P.， Papathomas， T. V. and Yianilos， P. N. “The Bayesian Image Retrieval System， PicHunter：Theory， Implementation， and Psychophysical Experiments” IEEE Transactions on Image Processing -- special issue on digital libraries， 2000．

[4]王建會，胡運發，李榮陸．自適應確定摘要長度[J ]．計算機研究與發展，2004 ，41 (3)：3992406．

[5] Ishikawa， Y.， Subramanya R.， and Faloutsos， C.， “Mindreader: Query Databases Through Multiple

Examples，” In Proc. of the 24th VLDB Conference， (New York)，1998．

[6] X. S．Zhou and T. S. Huang．Comparing discriminating transformations and svm for learning during multimedia retrieval. In Proceedings of the 9th ACM Multimedia Conference， pages 137–146. Orlando， Florida， 2001．

[7] Rocchio， Jr.， J. J.(1971). Relevance Feedback in Information Retrieval. In The SMART Retrieval System： Experiments in Automatic Document Processing (Salton， G. eds ) pp313-323．Prentice-Hall．

[8] Stuart Russel and Peter Norvig．Artifical Intelligence: A Modern Approach. Prentice Hall， 2nd edition， 2003．

[9] Richard O.Duda，Peter E.Hart，David G.Stork．李宏東，姚天翔，等譯．模式識別[M]．機械工業出版社（原書第二版），2005．

[10] Asuncion，ANewman，D.J(2007)，UCI Machine Learning， Repository， Website:http://mlearn.ics.uci.edu/MLRepository.html．

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文