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

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

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

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

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

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

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