基于多維度的新型排名算法

摘要:在處理各項指標成績線性之和相差不多，而要使成績平均程度高的排名對象排在前面的排名問題時，普通排名算法存在著一定的局限性。基于多維度的新型排名算法，使得各項考核指標成績越平均的排名對象名次越靠前，該算法科學合理，應用范圍廣，有較強的實用性。首介紹了該算法的基本原理，分別通過理論和實例論證了這種新型排名算法的優勢，最后基于該算法利用Java語言實現了一個簡單的排名軟件。

關鍵詞:排名;多維度;平均;軟件

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)24-6704-03

New Ranking Algorithm Based on Multi-dimension

ZHENG Wei-guo1， JIANG Li-qun1， MENG De-huai2

(1.School of Computer Science and Technology， China University of Mining and Technology， Xuzhou 221008， China;2.School of Chemical Engineering and Technology， China University of Mining and Technology， Xuzhou 221008， China)

Abstract:Traditonal ranking algorithm has limitations when the totals of all the indicators are approximative. The new ranking algorithm based on multi-dimension makes the ranks of the objects upfront whose scores are much more average. This algorithm has wide application range and practicability. Firstly introduces the basic principles of the algorithm and demonstrates the advantages of the new ranking algorithm through theory and example， finally we implement a simple ranking software using java language based on this algorithm.

Key words:rank; multidimensional; average; software

隨著信息技術的發展，在當今社會到處都面臨著排名的問題。大到各種國際獎項的評比，小到企事業單位員工福利的發放和學生的成績排名，排名的問題充斥著社會的方方面面，它和每個人的切身利益都息息相關，所以科學的排名算法確實是十分重要的，而排名的結果總是建立在總成績由高到低排序的基礎上的。

當排名的指標不只一個時，會引入權值的概念，依據權值求得每個指標的加權成績，將各個指標的成績線性相加得到總成績，通過對總成績的排序，獲得最終的排名結果。

目前求總成績只有線性相加這一種算法，這里稱之為普通排名算法，所有的多指標排名問題都采用這一種算法來處理最終數據，對于那些要求使得各項指標成績平均程度越高、水平越穩定，考核對象名次越靠前的排名問題，現有的普通排名算法就顯得無能為力了，這類問題有很多，比如:選拔全能運動員、推選優秀學生、員工獎金發放、名額分配、綜合排名等。

鑒于此，本文介紹一種全新的算法來解決求總成績及其排名的問題，通過將問題擴展到多維角度，并通過一定的理論證明，給出了這種新算法的優勢所在。最后，為了使在應用這種算法時能夠避開繁瑣的計算，通過直接輸入數據就可以得到最終的結果，利用java語言實現了一個簡單的績效排名軟件。

1 普通排名算法分析

普通排名算法即線性求和，是將單個指標的成績與相應的權值相乘，然后累加起來作為總成績。假設共有n項指標，第i項指標的加權之前的成績為vi，其權值為wi，則排名對象的總成績是L，其計算公式如下:

L=pi ， 其中，pi=viwi

普通排名算法簡單明了，但是只是對各項指標成績進行簡單的線性相加，沒有充分考慮各項指標之間的聯系，特別是當要使那些平均水平較高的排名對象的名次相對靠前時，這種算法就有很大的局限性。例如假設有兩個參評對象甲、乙，考核指標的數目是3，甲的三項指標成績都為a，乙的三項指標成績分別為l、m、n，其中a、l、m、n均為正數且不完全相等，且有l+m+n=3a，若根據普通排名算法求得的甲乙兩人的總成績相等，我們注意到甲的成績平均程度要明顯高于乙的，應用普通排名算法體現不出這一特點，從而也就無法直接進行比較，沒有起到理想的排名效果。

2 多維模型算法

2.1 算法介紹

一般地，當排名的指標有三個的時候，每一個指標的成績與相應指標的權值相乘，為了不過分摻加人為因素，采用二維模型來解決問題(如圖1所示)。在平面上取一點O，以O點為中心，在該平面內作三條射線，三條射線之間的夾角為120°，在這三條射線上分別截取一條線段OA、OB、OC，這三條線段的長度分別為加權后相應指標的得分，把A、B、C這三個端點用三條線段連結起來組成一個三角形，形狀類似于BH3分子模型，以該三角形的面積S作為相應對象的總成績，其中S=1/2(OA*OB+OA*OC+OB*OC)sinθ，θ=120°，然后依據此總成績進行排名。

2.2 算法優勢

假設有兩個參評對象甲、乙，考核指標的數目是3，甲的三項指標成績都為a，乙的三項指標成績分別為l、m、n，其中a、l、m、n均為正數且不完全相等，且有l+m+n=3a。

證明:設S甲、S乙分別代表甲乙兩對象的綜合得分。根據二維模型排名算法有:

根據不等式均值定理有:

l*m≤(l+m)2/4=(3a-n)2/4，當且僅當l=m時等號成立，同理有l*n≤(3a-m)2/4，m*n≤(3a-l)2/4，

綜上，當l=m=n時，S乙取得最大值(/4)a2，而由于l、m、n均為正數且不完全相等，所以總有S甲>S乙，從而使得甲的排名相對更靠前。可見，和普通排名算法相比，二維模型排名算法確實能夠使上述一類問題得到很好地解決，充分利用了考核對象各項指標的平均程度信息，指標成績越平均，名次越靠前，能夠起到很好的排名效果。

3 三維模型算法

當排名的指標有四個的時候，首先考慮四個指標放在一個二維平面內，兩兩之間相互垂直組成一個平面四邊形，用它的面積來表示所得分數的大小，但是這種算法摻加了人為因素，即四個指標不同的排列方式計算出來的面積不一樣，其原因是各條邊之間的夾角是人為引入的，使得各項指標之間的相互作用關系的程度不同，缺乏客觀性、合理性。

考慮把它們組成一個三維圖形，本文首選甲烷的形狀。把上述的四個指標看成是甲烷里的C-H鍵，它們相互之間組成的夾角109°28'(如圖2所示)，以單個指標的成績作為鍵長，而三棱錐的體積是四個指標對排名對象綜合影響績效，然后按照這個總成績進行排名。這類似于有一個容器，它所占據的空間大小即代表了它的實力，為了讓它盡可能多的占據空間，就需充分發揮各條棱(各項指標)之間的作用關系，即在各條棱線性和相差不大時，各條棱長越均衡它所占的體積越大。

具體計算步驟為:

第一步，根據四條已知的鍵長和其夾角，利用余弦定理求出各條棱長;

第二步，根據各棱長求出某共定點的三條棱(a、b、c)之間的夾角記為:

α、β、γ，令s=1/2(α+β+γ);

第三步，求解三棱錐的體積，其計算公式為:

當指標有三個的時候，前面已經證明多維度排名算法能夠使得各項指標成績越平均的對象排名相對越靠前，同樣可證，當排名指標有四個的時候，能起到同樣的效果。

4 實例分析

現在用一個具體的例子來說明問題。某體育隊要從10名隊員中選取5名參加比賽，排名標準只考慮下列因素:項目A、項目B、項目C、項目D(以下分別簡稱項A、項B、項C、項D)，處理后的數據見表1。

用普通排名算法和三維排名算法排名處理結果分別如表2和表3。

兩種算法結果的綜合比較如表4。

從上面的結果不難看出，兩種算法的結果雖然在大體趨勢上一致，然而具體的名次卻是有了較大的變化。如果根據傳統算法，最前兩名P1、P2的總成績相等，并且從第4名開始的P5、P6、P8、P10四人的總成績也相等，而實際上，他們每個人的各項指標成績平均程度不同，這一算法沒有很好的利用到這一信息，若要進一步篩選則需要使用概率、方差等估計知識;采用三維模型排名算法，由于P2的各項指標成績平均程度比P1的高，從而使得P2的總成績高于P1;P5、P6、P8、P10四人中P5的各項指標成績平均程度最高，所以排在了最前面，P10次之，P6最差，此外，在普通排名算法中，P6的總成績比P3的高，但是由于P6的各項成績不如P3的更平均，所以，應用多維排名算法后使得P3的名次相對P6更靠前，充分體現了多維排名算法使得各項成績平均程度越高其排名越靠前的特點，并且效果十分顯著。

5 軟件實現

采用“多維模型算法”解決實際問題時由于在計算棱錐模型體積時較為繁瑣，為了使得這種算法運用起來更加方便和實用，采用Java語言實現了一個較為簡單的軟件，后臺采用數據庫技術，使得數據存儲相對方便和安全。用戶可以通過該軟件根據具體情況選擇指標的數目，輸入對象的各項指標值，只需按下相應的按鈕，即可進行排名。該軟件運行界面如圖3、圖4。

6 結束語

通過一定的理論證明和實例分析，明顯得出本文提出的基于多維度的新型排名算法的特點，即在指標線性和相差不多時，各項指標成績越平均名次越靠前，在這一點上，多維模型算法比普通排名算法更加合理和有效。

為了便于說明問題本文中只提到了指標數目為3、4的計算模型，對于其它更多因素的問題可以轉化為相應的錐體模型，然后求解;也可以進行一系列的轉化，最終轉化成三棱錐模型。

由于多維模型算法目前是首次提出，如果能夠進一步研究和完善，這種算法在不久的將來會在許多領域得到廣泛的應用和認可，同時對我們的生活產生一些影響。

參考文獻:

[1] 蘇金明.數學軟件應用舉例[M].北京:電子工業出版社，2004.

[2] 宋兆基.Matalab6.5在科學計算中的應用[M].北京:清華大學出版社，2005.

[3] 張永強.Java程序設計應用教程[M].北京:電子工業出版社，2007.