基于機器學習的環(huán)匹配算法的研究與實現(xiàn).pdf

1、隨著互聯(lián)網和交付服務的發(fā)展，在線交換服務已經變得越來越方便和流行。發(fā)布/訂閱系統(tǒng)在交換服務領域的應用，使人們處理信息的方式發(fā)生了改變。同構對稱的發(fā)布/訂閱應用中，發(fā)布和訂閱角色是對稱的，用戶同時是消息的發(fā)布者和訂閱者。無論是事件的訂閱者還是事件的產生者都可以給出限制條件，對得到的最終結果進行取舍。對于發(fā)布/訂閱系統(tǒng)來說，可以成功交換數量越多，系統(tǒng)和用戶的收益越大。匹配不僅可以發(fā)生在兩個用戶之間，還可以發(fā)生在多于兩個用戶之間形成環(huán)匹配，這

2、樣就提高了用戶被匹配的概率。在實際應用中，隨著用戶（訂閱）數和環(huán)匹配的長度變大，環(huán)匹配數目和中間匹配結果（鏈訂閱）數目呈指數式增長，服務端運行所需的空間呈指數式增長。因此，需要近似的環(huán)匹配策略，選擇性保留相應的鏈訂閱，來達到利用有限空間來發(fā)現(xiàn)更多環(huán)匹配的目的。另外，隨著系統(tǒng)用戶越來越多，系統(tǒng)為用戶提供的候選匹配結果集也越來越大，快速、有效地為用戶推薦最優(yōu)匹配也成為發(fā)布/訂閱系統(tǒng)研究的關鍵問題。
　　針對近似環(huán)匹配策略問題，傳統(tǒng)的閾

3、值策略通過設置與訂閱被匹配概率相關的閾值，拋出低于該閾值的相關鏈訂閱，來節(jié)省存儲空間。由于在線交換服務是一種在線的實時系統(tǒng)，隨著時間推移，系統(tǒng)中的訂閱數據分布會發(fā)生變化，傳統(tǒng)的閾值策略就需要用戶頻繁的設置閾值，才能找到最佳閾值點。另外，傳統(tǒng)的閾值策略，只考慮到訂閱數據整體匹配概率，忽略了兩種謂詞匹配概率的離散度，可能導致訂閱數據的擁有謂詞匹配概率和需求謂詞匹配概率相差懸殊。鑒于此，本文提出了基于ELM(Extreme LearningM

4、achine)的動態(tài)分類策略，通過動態(tài)分類來不斷適應改變的數據分布，而不需要頻繁設置閾值，而且考慮到訂閱數據擁有謂詞匹配概率和需求謂詞匹配概率的離散度，避免了某種謂詞匹配概率高而另外一種匹配概率低的劣質訂閱數據匹配，同時系統(tǒng)可以節(jié)約很大的空間。本文將動態(tài)分類策略和傳統(tǒng)的閾值策略以及基于SVM的近似環(huán)匹配算法在仿真環(huán)境下進行了實驗對比，實驗結果表明動態(tài)分類策略總能找到最好的閾值點來對中間結果進行分類，并且使環(huán)匹配時間與傳統(tǒng)的閾值策略在一個

5、數量級上，獲得了較高的分類精度。
　　針對最優(yōu)推薦問題，傳統(tǒng)的top-k查詢策略，通過對最終的匹配結果進行打分，按照打分結果進行top-k查詢?yōu)橛脩敉扑]最優(yōu)的k個匹配結果。但是，對于海量匹配結果下最終環(huán)匹配結果的極為相近的情況，top-k查詢策略的查詢結果相似度可能過高，提供給用戶的可利用的結果種類可能偏少，不能很好地滿足用戶。另外，top-k查詢策略查詢過程中的剪枝策略，使得查詢結果缺乏可持久性，在top-k查詢結果不好的情況下

6、，用戶必須重新發(fā)起top-k查詢才能瀏覽更多的匹配結果?；谶@兩點，本文提出了top-k聚類策略，首先給出了三種top-k聚類算法，增加了匹配結果展示手段，同時也避免top-k查詢的不可恢復性，然后本文將三個top-k聚類算法與基于堆的top-k查詢算法在仿真環(huán)境下進行了對比，結果表明，top-k聚類策略與top-k查詢策略相比，可以獲得更加豐富的匹配結果，基于直方圖和基于擴展DBSCAN的top-k聚類算法聚類時間都比top-k查詢時