幾種排序算法對比分析

穆哈麥德

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

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

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

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

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

文檔列表方式是將查詢結(jié)果的列表作為模型訓(xùn)練用的實(shí)例，其最終目的在于最小化文檔列表的損失函數(shù)來達(dá)到優(yōu)化排序結(jié)果的效果，文檔列表方式是最具現(xiàn)實(shí)意義的方法因?yà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è)有一組用戶瀏覽的記錄為：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）首先建立一個比較簡單的文檔列表；（2）然后通過利用文檔列表建立一種群體用戶模型；（3）采用蟻群算法對最優(yōu)排序進(jìn)行求解。

三、比較分析

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

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

四、結(jié)論

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

本文將蟻群算法引入到排序建模中，通過蟻群算法的正負(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)用戶興趣變化的非線性逐步遺：怎協(xié)同過濾算法[J].計(jì)算機(jī)輔助工程，2010，16（2）：69-73.

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