穆哈麥德

【摘要】 互聯(lián)網(wǎng)+已經(jīng)是當(dāng)前國(guó)內(nèi)行業(yè)經(jīng)濟(jì)發(fā)展的重要基礎(chǔ)和技術(shù)支撐，搜索引擎技術(shù)的目標(biāo)任務(wù)就是將用戶(hù)查詢(xún)返回的結(jié)果進(jìn)行排序，這個(gè)排序的標(biāo)準(zhǔn)就是按照與用戶(hù)查詢(xún)的相關(guān)程度進(jìn)行排序，而如何獲得這個(gè)最準(zhǔn)確的返回列表也正是排序?qū)W習(xí)所要研究的重點(diǎn)。本文對(duì)比了幾種常見(jiàn)排序算法，同時(shí)對(duì)于重點(diǎn)提出的基于蟻群算法的排序算法與經(jīng)典的直接優(yōu)化算法進(jìn)行了比較分析。

【關(guān)鍵字】 排序 排序算法 對(duì)比

排序?qū)W習(xí)主要是根據(jù)給定的對(duì)象集合，學(xué)習(xí)一種完整的排序模型，以此來(lái)計(jì)算各個(gè)對(duì)象的分值，然后利用這些分值對(duì)這些對(duì)象進(jìn)行排序。己有的排序?qū)W習(xí)算法在處理小規(guī)模數(shù)據(jù)集時(shí)可以表現(xiàn)出良好的算法性能，然而在大數(shù)據(jù)的背景下現(xiàn)有的算法在處理大規(guī)模數(shù)據(jù)時(shí)面臨訓(xùn)練模型時(shí)間緩慢，內(nèi)存消耗大等問(wèn)題，尤其是在一些需要實(shí)時(shí)處理數(shù)據(jù)的領(lǐng)域，這些問(wèn)題的解決顯得尤為迫切，成為一個(gè)值得研究的具有理論和應(yīng)用價(jià)值的問(wèn)題。

一、排序?qū)W習(xí)算法的比較

排序?qū)W習(xí)對(duì)搜索引擎的研究產(chǎn)生了很大的影響，一般在針對(duì)某個(gè)社會(huì)、管理或者其他領(lǐng)域的復(fù)雜問(wèn)題進(jìn)行系統(tǒng)分析時(shí)，所面臨的問(wèn)題經(jīng)常是一個(gè)由多個(gè)因素影響，且各個(gè)因素之間相互制約的復(fù)雜排序問(wèn)題。要解決這類(lèi)問(wèn)題，必須尋求到一個(gè)簡(jiǎn)潔、有效、實(shí)用的排序方法，并行排序方法為這類(lèi)問(wèn)題找到了解決方案。比較好的排序方法的特征是能夠合理的考慮定性與定量因素，將復(fù)雜的決策過(guò)程按照思維、邏輯規(guī)律進(jìn)行層次化與量化。這是經(jīng)濟(jì)系統(tǒng)決策科學(xué)中的一種常用方法、一種有效的決策工具。層次分析法所依據(jù)的原則就是主要靠決策者以及用戶(hù)的既有經(jīng)驗(yàn)，既通過(guò)定性方法，也通過(guò)定量方法，然后綜合判斷每個(gè)目標(biāo)的實(shí)現(xiàn)的可能性以及互相影響的關(guān)系，同時(shí)界定重要程序，從而結(jié)合這三個(gè)方案來(lái)賦予一定的權(quán)重，通過(guò)權(quán)值之間的組合給方案進(jìn)行優(yōu)劣排序，相比于只使用定量方法來(lái)解決問(wèn)題，效率更高，針對(duì)性更強(qiáng)。主要包括以下幾個(gè)方式：?jiǎn)挝臋n方式是指將單個(gè)文檔作為訓(xùn)練樣本，使得根據(jù)從訓(xùn)練樣本學(xué)習(xí)到的分類(lèi)或者回歸函數(shù)對(duì)文檔評(píng)分，從而根據(jù)這個(gè)評(píng)分結(jié)果決定它的排序。2007年，美國(guó)一些人員通過(guò)研究將將多類(lèi)別分類(lèi)引入到排序問(wèn)題中從而提出了McRank算法。2012年，程凡提出了基于Point-wise的直接優(yōu)化的排序算法。

文檔列表方式是將查詢(xún)結(jié)果的列表作為模型訓(xùn)練用的實(shí)例，其最終目的在于最小化文檔列表的損失函數(shù)來(lái)達(dá)到優(yōu)化排序結(jié)果的效果，文檔列表方式是最具現(xiàn)實(shí)意義的方法因?yàn)樗鼘⑴判騿?wèn)題看待為更實(shí)際的模型。2007年Z.Cao等人提出的ListNet算法根據(jù)定義的排列概率與實(shí)際排序的序列的KL距離作為損失函數(shù)進(jìn)行學(xué)習(xí)。2014年，繆志高將半監(jiān)督引入了List-wise排序?qū)W習(xí)框架，基于這種半監(jiān)督的排序?qū)W習(xí)算法可以更加有效地提升算法性能。

二、基于蟻群算法的并行排序算法

蟻群算法是一種仿生算法，具有路徑概率選擇機(jī)制，信息的正負(fù)反饋機(jī)制，幾乎所有的螞蟻都沿著一條路徑行走，該條路徑就是一條最優(yōu)路徑，在很多領(lǐng)域得到成功的應(yīng)用，也可以應(yīng)用到排序算法中。

設(shè)有一組用戶(hù)瀏覽的記錄為：S={（n1，n4，n8），（n1，n4），（n1，n4，n7），（n1，n3，n7），（n1，n3，n6），（n1，n3，n7），（n1，n3，n6），（n1，n2，n5，n3，n7），（n1，n2，n5），（n6，n7））

蟻群算法的Web站點(diǎn)排序模型如圖1所示

基于蟻群算法的排序模型包括以下策略：（1）首先建立一個(gè)比較簡(jiǎn)單的文檔列表；（2）然后通過(guò)利用文檔列表建立一種群體用戶(hù)模型；（3）采用蟻群算法對(duì)最優(yōu)排序進(jìn)行求解。

三、比較分析

為驗(yàn)證第2節(jié)中的基于蟻群的排序算法效率，接下來(lái)對(duì)比了本文算法與的直接優(yōu)化排序算法，對(duì)于不同的事務(wù)長(zhǎng)度，排序的效率如表1所示：

因此，相對(duì)于直接優(yōu)化排序算法，蟻群排序算法的排序效率和準(zhǔn)確度更高，主要由于蟻群算法采用信息素機(jī)制實(shí)現(xiàn)正負(fù)反饋機(jī)制。

四、結(jié)論

現(xiàn)在是海量數(shù)據(jù)以及物流極度發(fā)達(dá)的一個(gè)時(shí)代，為了更好的配置資源，降低實(shí)體化的路途成本，充分利用當(dāng)前數(shù)據(jù)庫(kù)以及分布式技術(shù)的優(yōu)勢(shì)，實(shí)現(xiàn)多方合理資源共享以及降低成本，提高企業(yè)工作效率與利潤(rùn)。而如何進(jìn)一步挖掘互聯(lián)網(wǎng)下所產(chǎn)生的海量數(shù)據(jù)信息，進(jìn)行快速排序，是一個(gè)具有高度價(jià)值與前景的課題。集成了數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘技術(shù)一體的商業(yè)智能，則為顯性知識(shí)中的并行排序提供了良好的方式，為企業(yè)提供有價(jià)值的信息以支持決策。

本文將蟻群算法引入到排序建模中，通過(guò)蟻群算法的正負(fù)反饋機(jī)制和路徑概率選擇機(jī)制快速排序，取得很好的效果。

參 考 文 獻(xiàn)

[1] R.Cooley.Web Usage Mining： Discovery and Application of Interesting Patterns from Web data. PhD thesis， Dept. of Computer Science， University of Minnesota， May 2000.

[2] 鄭先榮，湯澤瀅，曹先彬.適應(yīng)用戶(hù)興趣變化的非線性逐步遺：怎協(xié)同過(guò)濾算法[J].計(jì)算機(jī)輔助工程，2010，16（2）：69-73.

[3] 涂承勝，魯明羽，陸玉昌.Web挖掘研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，2003，10：90-93.