Home » Posts tagged "ranking"

對於按讚數排名的方法

前幾天看到一篇 2009 年的老文章,在討論使用者透過「喜歡」以及「不喜歡」投票後,要怎麼排名的方法:「How Not To Sort By Average Rating」。

基本的概念是當使用者投票數愈多時就會愈準確,透過統計方法可以算一個信賴區間,再用區間的下限來排... 但沒想到公式「看起來」這麼複雜 XDDD

Score = Lower bound of Wilson score confidence interval for a Bernoulli parameter

但實際的運算其實沒那麼複雜,像是 Ruby 的程式碼可以看出大多都是系統內的運算就可以算出來。其中的 z 在大多數的情況下是常數。

require 'statistics2'

def ci_lower_bound(pos, n, confidence)
    if n == 0
        return 0
    end
    z = Statistics2.pnormaldist(1-(1-confidence)/2)
    phat = 1.0*pos/n
    (phat + z*z/(2*n) - z * Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)
end

The z-score in this function never changes, so if you don't have a statistics package handy or if performance is an issue you can always hard-code a value here for z. (Use 1.96 for a confidence level of 0.95.)

作者後來在 2012 年與 2016 年也分別給了 SQL 以及 Excel 的範例程式碼出來,裡面 hard-code 了 95% 信賴區間的部份:

SELECT widget_id, ((positive + 1.9208) / (positive + negative) - 
                   1.96 * SQRT((positive * negative) / (positive + negative) + 0.9604) / 
                          (positive + negative)) / (1 + 3.8416 / (positive + negative)) 
       AS ci_lower_bound FROM widgets WHERE positive + negative > 0 
       ORDER BY ci_lower_bound DESC;
=IFERROR((([@[Up Votes]] + 1.9208) / ([@[Up Votes]] + [@[Down Votes]]) - 1.96 * 
    SQRT(([@[Up Votes]] *  [@[Down Votes]]) / ([@[Up Votes]] +  [@[Down Votes]]) + 0.9604) / 
    ([@[Up Votes]] +  [@[Down Votes]])) / (1 + 3.8416 / ([@[Up Votes]] +  [@[Down Votes]])),0)

而更多的說明在維基百科的「Binomial proportion confidence interval」可以翻到,裡面也有其他的方法可以用。

Google PageRank 資料將不再公開

Google 將不再對外公開 PageRank 資訊:「Google has confirmed it is removing Toolbar PageRank」與「RIP Google PageRank score: A retrospective on how it ruined the web」。

PageRank 資訊是透過 Google Toolbar 再反向被挖出來的,而 Toolbar 上的資訊將會拿掉,也預期對應的 API 應該也會關閉:

Google has confirmed with Search Engine Land that it is removing Toolbar PageRank. That means that if you are using a tool or a browser that shows you PageRank data from Google, within the next couple weeks it will begin not to show any data at all.

Google 內部還是會用,只是不會公開了...

IndexTank 的設計

IndexTank 是在 xdite 的個人板上看到的網站,號稱真正 Scalable 的 Search Engine,看了他的架構設計後看起來應該是真的 Scalable。

由於是屬於 SaaS 服務,對於 startup 不想自己做 search engine 的可以直接套上去。而對於技術人員真正有價值的是他的 API 設計文件中的 function definition syntax:「function definition syntax」,雖然故意寫個 coming soon,但實際上可以在 client library 裡看到範例:「Python client」。

先內建一些基本的數學函數,像是四則運算、power、log,並且內建一些很常用到的變數。接下來定義出來的函數可以再重複使用,不斷累積上去,最後在 query 的時候就可以 ORDER BY 某個 score...

IndexTank 告訴你「利用 API 讓前端程式設定 function 以降低 denormalization 的複雜度」時要怎麼設計 API,當你自己建立 search engine 時,新增的 function 還可以在後端用 MapReduce 把資料補上去...。

另外可以再參考「How Hacker News ranking algorithm works」這篇文章。(這篇文章的 comment 裡面有其他的 ranking code 可以看)

Archives