基于用户投票的排名算法（四）：牛顿冷却定律
日期：?2012年3月16日
這個(gè)系列的前三篇，介紹了Hacker News，Reddit和Stack Overflow的排名算法。
今天，討論一個(gè)更一般的數(shù)學(xué)模型。
這個(gè)系列的每篇文章，都是可以分開讀的。但是，為了保證所有人都在同一頁上，我再說一下，到目前為止，我們用不同方法，企圖解決的都是同一個(gè)問題：根據(jù)用戶的投票，決定最近一段時(shí)間內(nèi)的"熱文排名"。
你可能會(huì)覺得，這是一個(gè)全新的課題，伴隨著互聯(lián)網(wǎng)而產(chǎn)生，需要全新的方法來解決。但是，實(shí)際上不是。我們可以把"熱文排名"想象成一個(gè)"自然冷卻"的過程：
（1）任一時(shí)刻，網(wǎng)站中所有的文章，都有一個(gè)"當(dāng)前溫度"，溫度最高的文章就排在第一位。
（2）如果一個(gè)用戶對(duì)某篇文章投了贊成票，該文章的溫度就上升一度。
（3）隨著時(shí)間流逝，所有文章的溫度都逐漸"冷卻"。
這樣假設(shè)的意義，在于我們可以照搬物理學(xué)的冷卻定律，使用現(xiàn)成的公式，建立"溫度"與"時(shí)間"之間的函數(shù)關(guān)系，輕松構(gòu)建一個(gè)"指數(shù)式衰減"（Exponential decay）的過程。
偉大的物理學(xué)家牛頓，早在17世紀(jì)就提出了溫度冷卻的數(shù)學(xué)公式，被后人稱作"牛頓冷卻定律"（Newton's Law of Cooling）。我們就用這個(gè)定律構(gòu)建排名算法。
"牛頓冷卻定律"非常簡單，用一句話就可以概況：
物體的冷卻速度，與其當(dāng)前溫度與室溫之間的溫差成正比。
寫成數(shù)學(xué)公式就是：
其中，
- T(t)是溫度（T）的時(shí)間（t）函數(shù)。微積分知識(shí)告訴我們，溫度變化（冷卻）的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。
- H代表室溫，T(t)-H就是當(dāng)前溫度與室溫之間的溫差。由于當(dāng)前溫度高于室溫，所以這是一個(gè)正值。
- 常數(shù)α（α>0）表示室溫與降溫速率之間的比例關(guān)系。前面的負(fù)號(hào)表示降溫。不同的物質(zhì)有不同的α值。
這是一個(gè)微分方程，為了計(jì)算當(dāng)前溫度，需要求出T(t)的函數(shù)表達(dá)式。
第一步，改寫方程，然后等式兩邊取積分。
第二步，求出這個(gè)積分的解（c為常數(shù)項(xiàng)）。
第三步，假定在時(shí)刻t0，該物體的溫度是T(t0)，簡寫為T0。代入上面的方程，得到
第四步，將上一步的C代入第二步的方程。
假定室溫H為0度，即所有物體最終都會(huì)"冷寂"，方程就可以簡化為
上面這個(gè)方程，就是我們想要的最終結(jié)果：
本期溫度 = 上一期溫度 x exp(-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
將這個(gè)公式用在"排名算法"，就相當(dāng)于（假定本期沒有增加凈贊成票）
本期得分 = 上一期得分 x exp(-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
其中，"冷卻系數(shù)"是一個(gè)你自己決定的值。如果假定一篇新文章的初始分?jǐn)?shù)是100分，24小時(shí)之后"冷卻"為1分，那么可以計(jì)算得到"冷卻系數(shù)"約等于0.192。如果你想放慢"熱文排名"的更新率，"冷卻系數(shù)"就取一個(gè)較小的值，否則就取一個(gè)較大的值。
[參考文獻(xiàn)]
* Rank Hotness With Newton's Law of Cooling
（完）
文檔信息
- 版權(quán)聲明：自由轉(zhuǎn)載-非商用-非衍生-保持署名（創(chuàng)意共享3.0許可證）
- 發(fā)表日期：?2012年3月16日
- 更多內(nèi)容：?檔案???算法與數(shù)學(xué)
- 購買文集：?《如何變得有思想》
- 社交媒體：?twitter，?weibo
- Feed訂閱：?
相關(guān)文章
- 2015.09.01:?理解矩陣乘法 大多數(shù)人在高中，或者大學(xué)低年級(jí)，都上過一門課《線性代數(shù)》。這門課其實(shí)是教矩陣。
- 2015.07.27:?蒙特卡羅方法入門 本文通過五個(gè)例子，介紹蒙特卡羅方法（Monte Carlo Method）。
- 2015.06.10:?泊松分布和指數(shù)分布：10分鐘教程 大學(xué)時(shí)，我一直覺得統(tǒng)計(jì)學(xué)很難，還差點(diǎn)掛科。
- 2013.12.16:?樸素貝葉斯分類器的應(yīng)用 生活中很多場合需要用到分類，比如新聞分類、病人分類等等。
留言（19條）
好模型。
2012年3月16日 02:18?|?∞?|?引用
有趣的模型。如果拿這個(gè)跟那些score=log(vote)-c*time的模型比較，可以發(fā)現(xiàn)后者就是對(duì)牛頓模型里的溫度取了個(gè)對(duì)數(shù)。
一個(gè)可能的變化是考慮每一票的時(shí)間，一小時(shí)前的新“頂”應(yīng)該比去年的“頂”有更大的效果。其實(shí)有些論壇按照最后回復(fù)來排列貼子，結(jié)果近似于每一個(gè)回復(fù)都讓系統(tǒng)溫度提高很多（自動(dòng)取得所有貼子里的最高溫度），而后慢慢冷卻。每“頂”一次都把文章提到最前是沒有必要的，但可以調(diào)節(jié)參數(shù)得到更有實(shí)際意義的模型。其負(fù)面作用是或者要記錄每一“頂”的時(shí)間，增加系統(tǒng)負(fù)擔(dān)，或者要實(shí)時(shí)記錄當(dāng)前“溫度”，而這個(gè)“溫度”無法從原始數(shù)據(jù)得出（因?yàn)槊看巍绊敗钡臅r(shí)間沒有記錄下來）。
2012年3月16日 04:41?|?∞?|?引用
這個(gè)模型不錯(cuò)！
2012年3月16日 09:12?|?∞?|?引用
那如果是本期有增加贊成票呢，應(yīng)該怎么計(jì)算呢？
是不是可以這樣, 先算一下上一期到現(xiàn)在冷卻后的得分,然后再加上{本期增加贊成票數(shù)}
本期得分 = 上一期得分 × exp(-(冷卻系數(shù)) × 間隔的小時(shí)數(shù)) + 本期增加贊成票數(shù)
可是{本期增加贊成票數(shù)}是否應(yīng)以1為單位增加呢
2012年3月16日 11:03?|?∞?|?引用
"微積分知識(shí)告訴我們，溫度變化（冷卻）的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。" 這個(gè)怎么理解？
2012年3月16日 11:06?|?∞?|?引用
看得真親切，物理+微積分～～ :-)
2012年3月16日 22:57?|?∞?|?引用
我在想,阮gg這個(gè)公式編輯器用的是什么?
怎么生成圖片的???
看這公式,哥哥又要膜拜了...
到處都是大神啊...
2012年3月17日 12:24?|?∞?|?引用
之前也一直在思考如何將排名算法抽象出來，類比了一些自然現(xiàn)象也不得其解。
直到看到這篇文章，醍醐灌頂啊，真是萬物歸一，非常感謝分享。
2012年3月17日 19:45?|?∞?|?引用
引用亂發(fā)吹風(fēng)的發(fā)言：
那如果是本期有增加贊成票呢，應(yīng)該怎么計(jì)算呢？
是不是可以這樣, 先算一下上一期到現(xiàn)在冷卻后的得分,然后再加上{本期增加贊成票數(shù)}
本期得分 = 上一期得分 × exp(-(冷卻系數(shù)) × 間隔的小時(shí)數(shù)) + 本期增加贊成票數(shù)
可是{本期增加贊成票數(shù)}是否應(yīng)以1為單位增加呢
具體的權(quán)值應(yīng)該跟你的網(wǎng)站的特性有關(guān)。比如說訪問量，贊成票的更新量等等來具體決定吧。
2012年3月19日 09:15?|?∞?|?引用
引用必填的發(fā)言：
一個(gè)可能的變化是考慮每一票的時(shí)間，一小時(shí)前的新“頂”應(yīng)該比去年的“頂”有更大的效果。其實(shí)有些論壇按照最后回復(fù)來排列貼子，結(jié)果近似于每一個(gè)回復(fù)都讓系統(tǒng)溫度提高很多（自動(dòng)取得所有貼子里的最高溫度），而后慢慢冷卻。每“頂”一次都把文章提到最前是沒有必要的，但可以調(diào)節(jié)參數(shù)得到更有實(shí)際意義的模型。其負(fù)面作用是或者要記錄每一“頂”的時(shí)間，增加系統(tǒng)負(fù)擔(dān)，或者要實(shí)時(shí)記錄當(dāng)前“溫度”，而這個(gè)“溫度”無法從原始數(shù)據(jù)得出（因?yàn)槊看巍绊敗钡臅r(shí)間沒有記錄下來）。
并不需要記錄所有“頂”的時(shí)間，只需要記錄上一次“頂”的時(shí)間和當(dāng)時(shí)的溫度即可算出當(dāng)前“頂”之前的一瞬間冷卻到什么溫度，然后加上這個(gè)“頂”所帶來的溫度的提升即可。
冷卻模型沒有后效性，所以記錄原始數(shù)據(jù)是沒有意義的。
實(shí)際工程中應(yīng)該是離散地迭代來實(shí)現(xiàn)的。
2012年3月19日 09:23?|?∞?|?引用
引用xb的發(fā)言：
"微積分知識(shí)告訴我們，溫度變化（冷卻）的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。" 這個(gè)怎么理解？
速率就是一定時(shí)間內(nèi)變化量與時(shí)間的比。
V = (T(t) - T(t+dt)) / dt = dT(t) / dt = T'(t)2012年3月19日 09:26?|?∞?|?引用
有實(shí)現(xiàn)的代碼參考嗎？
2012年3月20日 00:42?|?∞?|?引用
引用Ranmocy的發(fā)言：
并不需要記錄所有“頂”的時(shí)間，只需要記錄上一次“頂”的時(shí)間和當(dāng)時(shí)的溫度即可算出當(dāng)前“頂”之前的一瞬間冷卻到什么溫度，然后加上這個(gè)“頂”所帶來的溫度的提升即可。
冷卻模型沒有后效性，所以記錄原始數(shù)據(jù)是沒有意義的。
實(shí)際工程中應(yīng)該是離散地迭代來實(shí)現(xiàn)的。
是，這基本上就是我說的“實(shí)時(shí)記錄當(dāng)前‘溫度’”。 我的想法是，有的時(shí)候可能會(huì)希望從原始數(shù)據(jù)重新計(jì)算一下溫度，比如說想調(diào)整冷卻系數(shù)；如果只記錄了當(dāng)前溫度，舊文章和新文章的計(jì)算就會(huì)有不一致的地方。
2012年3月20日 00:44?|?∞?|?引用
你是抄襲的么?http://www.oschina.net/question/12_45050
2012年4月 1日 09:45?|?∞?|?引用
非常thought-provoking，但是這里只考慮了冷卻問題，還有一個(gè)加溫的問題，二者在實(shí)際運(yùn)用中往往是結(jié)合在一起的。
比如頂（即贊成票）應(yīng)該是具有時(shí)效性的，當(dāng)前的頂顯然比一年前的頂更為重要。
2012年4月 2日 20:42?|?∞?|?引用
引用大米的發(fā)言：
你是抄襲的么?http://www.oschina.net/question/12_45050
那篇下面寫的有原文出處，就是這里呀。
2012年4月 9日 16:57?|?∞?|?引用
這就是工業(yè)界最常用的衰減因子了，每次歷史聚合的時(shí)候都對(duì)上一次的結(jié)果進(jìn)行衰減。
衰減因子主要存在的問題在于是衰減整體投票結(jié)果還是衰減投票。
比如歷史上不同時(shí)間段有贊成票， 反對(duì)票， 以及每個(gè)時(shí)間段的贊成比例。 不管衰減哪個(gè)都有優(yōu)勢(shì)和劣勢(shì)
2012年5月16日 15:07?|?∞?|?引用
對(duì)這個(gè)模型很感興趣。您覺得新浪微博的智能排序使用了什么算法呢？
2012年9月26日 11:08?|?∞?|?引用
這里只是考慮得分的一種通用自然衰減過程，沒有考慮其他因素比如用戶參與與外部貢獻(xiàn)是吧？
2013年9月 6日 09:34?|?∞?|?引用
總結(jié)
以上是生活随笔為你收集整理的基于用户投票的排名算法（四）：牛顿冷却定律的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于用户投票的排名算法（三）：Stack
- 下一篇： 基于用户投票的排名算法（五）：威尔逊区间