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

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

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

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

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

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

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