2011年11月29日 星期二

CSS 網頁中的文字重疊


网页中的文字重叠是什么原因[点击放大]
網頁中的文字重疊是什麼原因 
在流覽網頁時,經常可以看到文字重疊的現象,尤其是比較大的文字(如上圖一),它們好像更容易“重疊”。  其實,出現這種現象,90%的原因是出自行line-height的誤定。  line-height屬性設置行間的距離(即行高),它和字體大小font-size有很深的關係。line-heightfont-size的計算值之差(在 CSS 中成為“行間距”)分為兩半,分別加到一個文本行內容的頂部和底部。可以包含這些內容的最小框就是行框。  line-height的屬性值可以是數位、圖元、百分比等等。  當重疊現象出現時,一般都是行高的尺寸單位不對應所致。比如: 
<h1 style=" line-height:16px;font-size:30px;">文字文字文字<br />文字文字文字</h1>
 如圖一中所示,文字是30px,而行高是16px,文字必然會重疊。  所以,在某些區域的文字大小可能不會被預知的情況下,最好使用一些靈活的尺寸單位,比如百分比和em等,而盡少使用固定的尺寸單位。  將上代碼改為: 
<h1 style=" line-height:1em;font-size:30px;">文字文字文字<br />文字文字文字</h1>
 或者: 
<h1 style=" line-height:120%;font-size:30px;">文字文字文字<br />文字文字文字</h1>
 1em 等於當前的字體尺寸,不論你的字體是多大,行高都會與字體等高,不會出現重疊現象。定義成百分比,行高會隨著字體的大小按百分比放大或縮小。  這兩種方法完全可以有效防止文字重疊,而且簡單易行。

常見的程式交易系統


現在市場上常見的程式交易系統大概有TradeStationMultiCharts以及日盛的HTS交易軟體,法人大都是用前兩種軟體在作程式交易,所以這邊也只介紹前兩種交易系統。TradeStation算是程式交易的老祖,而MultiCharts是目前比較新的交易系統,不過兩個系統的程式編譯軟體語言其實是大同小異的,差異最大的是在進出場的指令有所不同。
TradeStation雖然算是比較原始的程式交易系統,也因為比較原始簡單,操作起來也比較容易順手,而且它的交易績效報表看起來也比較直觀且順眼,這方面MultiCharts就分的非常的細,容易讓人看的眼花撩亂。不過MultiCharts標榜的功能有可以使用多核心來處理計算,增加處理的速度,因此會要求電腦的配備,規格越高越好。而且MultiCharts不像傳統的TradeStation只能處理分鐘為單位的資料,MultiCharts可以顯示20ticks或是20秒等,多種不同時間間隔的資料,可以一個人喜好去做選擇。這有個好處是可以避免一般人是使用5K的資料來做進出場的時間間隔,而且選擇不同的時間間隔,所呈現出來的K線圖就會有所差別,也許可以讓你觀察到另一種不同感觀的K線圖走勢。尤其像那些在作超短線交易的人,可能就會需要用到時間間隔比較短的K線圖來做為進出場的依據。由此看來MultiCharts提供了更多策略開發的可能性,這點可能是TradeStation所比不上的。



再來,MultiCharts提供了一向很特別的功能,但也是大家所需要的,那就是它可以幫你的策略組合去最適化分配你的口數,當然,你已經在策略裡最適化過了,如果再在口數上做一次最適化,可能會有過度最佳化的疑慮。所以MultiCharts改進了很多之前TradeStation所做不到的事情,不過在下單方面,對於一般散戶可能只能使用元大的下單系統,因為MultiCharts是跟元大合作的,這個是比較制式的地方,而且下單方面的靈活度可能不如使用TradeStation加上自己寫的下單介面來的好。雖然使用MultiCharts可能是未來的趨勢,不過習慣使用TradeStation的人,可能還是會比較喜歡繼續使用TradeStation吧!這邊只是初步的介紹,有的東西必須實際進去摸索才會了解,也歡迎大家一起進來探索這美妙的世界。

轉:建置程式交易系統(2) - 決定獲利策略


相信很多人都有這樣的經驗,用一口去交易時,能穩定獲利,便想用兩口,用十口,試想,原本1點跳動是50塊或200塊,當變成500塊或2000塊,您還能保證用一口會遵循賺錢的策略嗎?少數人也許會嚴守紀律,但大多數一定是賺錢就跑,賠錢死撐。程式交易的好處,在交易口數放大後,依然遵循既定的交易策略(這是廢話,只是1改成10),可以避免掉人性的恐懼跟貪婪,這也是為何要用程式去交易期貨,至於是否有用程式去交易股票,因為股票的波動週期沒有期貨選擇權大,影響變數太多,一則新聞可能就讓股票漲停或跌停,所以散戶沒必要用程式去交易股票(法人在控制期貨盤時,也有會用程式交易現貨股票)。
以下是策略制定步驟:
  1. 先確定要賺的波段,是最短的tick交易、當沖賺一天波動,還是有留倉的大趨勢。當然交易系統是可結合多個策略,而一個策略只適合一種波段。針對策略的波段,再訂定進出的頻率。如果是Tick交易,當然是有賺就跑,高頻進出,但這只適合期貨商。一般散戶多為當沖或賺趨勢財,而當沖策略可以參考自由人的台指當沖交易秘訣,大波段的趨勢財就要參考摩台並判斷國際情勢。
  2. 天馬行空的策略,相信很多程式交易人員是利用技術分析方法來決定進場跟出場,也一定很多人搞不清楚什麼是布林通道,什麼是MACD,老實說我也搞不懂。因此,筆者以熟悉的影像處理方法(訊號處理技術)來套用到程式交易,這並不是說技術分析不對或不適用,但只局限在技術分析的範疇,何不結合其他領域的方法。且技術分析未嘗不是前人天馬行空後的結果。
  3. 決定進場點跟出場點,固定停損或動態停損:您是不是疑惑,為何沒寫固定停利或動態停利?因為如果用固定停利,其實就限制了獲利的範圍,所以應該皆為動態停利。使用技術指標,進場點為指標達到一定數值,可是並非每天交易都適用固定值,所以不妨多個判斷規則來給訂不同數值,亦可使用線性或非線性變數,當然出場也是相同原理,也許是不同指標或多種指標。
期貨程式交易機器人的當沖策略是先利用訊號處理技術過濾tick雜訊,並在一定tick數量上判斷斜率變化及走勢模式(pattern recognition),再配合摩台期的漲跌來決定進場時機。看盤最常用的K線其實是有盲點,十字線呈現開價跟收價是相同的,可是到底是先上漲後下跌還是先下跌後上漲(部分看盤軟體會呈現紅十字線或綠十字線,就可判斷出來),另外,若以一分鐘K線來看,一個大紅K或大黑K的前一根或許是十字線,看不出會突然大漲或大跌,所以通常不會只看K線圖,當然還要配合走勢圖才能分辨。以訊號處理領域解釋K線就是一種濾波器filter,每種濾波器都會凸顯一些資訊並遺失一些資訊,沒有一個濾波器是萬能的。
延伸閱讀:幣圖誌-常見的程式交易系統

轉:建置程式交易系統(1)

審視自身條件
由於本篇是著重準備工作,先不會談論到程式技術面,因並非每個人都適合投資高風險的期貨選擇權,建議先審視自己條件後,再投入這期貨交易才能避免把錢丟入大海、肉包子打狗。
  1. 心理建設 - 首先要判斷自己的投資心態是長線還是短線,如果您以投資股票的心態來投資期貨,必定虧錢,因為股票可以放著不管,但期貨選擇權每月結算一次,不管就等著斷頭追繳保證金,所以一定調整心態,方向錯就要認賠。習慣不把錢當錢看,一開始交易賠錢可能非常懊惱,並影響家庭生活或作息,如果又留倉,晚上更睡不好,且猛盯美股盤勢,更讓隔天交易畏手畏腳,大賺沒抱緊,大賠卻死抱。這都是人為操盤很難克服的心理因素,所以為何要讓程式自行交易。
  2. 具備程式能力 - 既然是要建置程式交易系統,當然要有程式的基礎,至於何種程式語言,則視您的程式交易平台為何?TradeStation就要了解EasyLanguage,MultuChart就要了解PowerLanguage,Excel就要了解VBA,只要有基本程式知識,再去學各種平台都是可行的。
  3. 支援API下單的期貨商 - 目前幾乎所有的期貨公司都有提供API讓顧客撰寫程式下單,建議選擇下單大師有支援的期貨商,把精力都花在程式交易規則,下單就交給下單機去處理。
  4. 穩定報價源 - 雖然大多數都是使用DDE報價,可是DDE在爆量時,會卡住不動,所以不建議使用DDE報價,可以選擇免費的群益API報價或收費的TOUCHANCE,至於如何介接API報價源,這往後文章將介紹。
  5. 模擬測試 - 當完成了一個自動交易程式,千萬別自得意滿,先利用歷史資料回測,如果連歷史資料交易都賠錢,那真實交易也鐵定賠。之後實際交易時,也先用模擬單測試,避免因系統或網路等因素導致大量虧損。下單大師支援模擬下單,既可保留模擬交易紀錄,亦可測試下單API。
上述皆是開發程式交易的必要條件,也是準備工作,如果都具備再進入期貨程式交易這領域,才能避免走很多冤妄路,或還沒賺到就直接血本無歸。
參考資料
以下是程式交易的相關資料,尤其是程式交易的解決方法和Trading Systems Coding,說明了程式交易的開發流程。
程式交易的解決方法
Algorithmic trading
Trading Systems Coding
國外交易分享社群 - Collective2
國內交易分享社群 - 策略星
國內程式交易論壇 - 程式交易聚寶盆

2011年11月28日 星期一

反詐騙裝潢監督聯盟


最近發現這個網站,有滿多裝潢受害的經驗和解決的建議,我們的主結構完成了,下一步就是裝修交屋,之後就接著是裝潢準備入住了,多多參考一下別人的經驗,以避免受害~~~

2011年11月24日 星期四

[轉]統計學習那些事


SVM的基本原理普遍表述為,SVM通過非線性變換把原空間映射到高維空間,然後在這個高維空間構造線性分類器,因為在高維空間資料點更容易分開。 甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣理解SVM的基本原理,我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實:SVM在高維空間裡構建 分類器後,為什麼這個分類器不會對原空間的資料集Overfitting呢?要理解SVM的成功,我覺得可以考慮以下幾個方面:第一,SVM求解最優分類 器的時候,使用了L2-norm regularization,這個是控制Overfitting的關鍵。第二,SVM不需要顯式地構建非線性映射,而是通過Kernel trick完成,這樣大大提高運算效率。第三,SVM的優化問題屬於一個二次規劃(Quadratic programming),優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法,比如SMOSequential minimal optimization)解法。第四,Vapnika的統計學習理論為SVM提供了很好的理論背景(這點不能用來解釋為什麼SVM這麼popular, 因為由理論匯出的boundloose)。於是SVM成功了,火得一塌糊塗!
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂就是比隨機猜要好一點點;就是強啦。這個想法可以追溯到由Leslie Valiant教 授(2010年圖靈獎得主)在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗,再好的理論也需要有效的演算法來執行。終於功夫不負有 心人, Schapire1996年提出一個有效的演算法真正實現了這個夙願,它的名字叫AdaBoostAdaBoost把多個不同的決策樹用一種非隨機的方 式組合起來,表現出驚人的性能!第一,把決策樹的準確率大大提高,可以與SVM媲美。第二,速度快,且基本不用調參數。第三,幾乎不 Overfitting。我估計當時BreimanFriedman肯定高興壞了,因為眼看著他們提出的CART正在被SVM比下去的時 候,AdaBoost讓決策樹起死回生!Breiman情不自禁地在他的論文裡讚揚AdaBoost是最好的現貨方法(off-the-shelf,即拿下了就可以用的意思)。其實在90年代末的時候,大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年,Friedman的一篇技術 報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑(沒有解釋AdaBoost為什麼不容易Overfitting,這個問題好像至今還沒有定論),即搞清楚了 AdaBoost在優化什麼指標以及如何優化的。基於此,Friedman提出了他的GBMGradient Boosting Machine,也叫MART或者TreeNet)。幾乎在同時,Breiman另闢蹊徑,結合他的Bagging (Bootstrap aggregating) 提出了Random Forest (今天微軟的Kinect裡面就採用了Random Forest,相關論文Real-time Human Pose Recognition in Parts from Single Depth ImagesCVPR2011best paper)。
有一個關於Gradient Boosting細節不得不提。Friedman在做實驗的時候發現,把一棵新生成的決策樹,記為f_m,加到當前模型之前,在這棵決策樹前乘以一個小的 數,即v×f_m(比如v=0.01),再加入到當前模型中,往往大大提高模型的準確度。他把這個叫做“Shrinkage”。接下 來,HastieTibshiraniFriedman進一步發現(我發現大師們都是親自動手寫程式做實驗的),如果把具有Shrinkage Gradient Boosting應用到線性回歸中時,得到的Solution PathLassoSolution Path驚人地相似(如圖所示)!他們把這一結果寫在了ESL的第一版裡,並推測這二者存在著某種緊密的聯繫,但精確的數學關係他們當時也不清楚。 Tibshirani說他們還請教了斯坦福的優化大師(我估計是Stephen Boyd),但還是沒有找到答案。

Lasso & Boosting

後來Tibshirani找到自己的恩師EfronTibshirani“The Science of Bradley Efron”這本書的序言裡寫道,He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm, ‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on the Lasso.”我就不逐字逐句翻譯了,大意是:Efron獨自擺平了這個問題,與此同時發明了“Least angle regression (LAR)”Efron結論是LassoBoosting的確有很緊密的數學聯繫,它們都可以通過修改LAR得到。更令人驚歎的是LAR具有非常明確 的幾何意義。於是,Tibshirani在序言中還有一句,In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind: geometric insight and analysis.Prof Efron的文章,可以感受到古典幾何學與現代統計學的結合之美(推薦大家讀讀Efron教授2010年的一本新書Large-Scale Inference,希望以後有機會再寫寫這方面的體會)!總之,Efron的這篇文章是現代統計學的里程碑,它結束了一個時代,開啟了另一個時代。
這裡,想補充說明一下Lasso的身世,它的全稱是The Least Absolute Shrinkage and Selection Operator,讀音不是[‘læso]而是[læ’su:],有中文翻譯為套索,個人覺得這個翻譯不好,太遠離它本來的含義,不如就用 LassoTibshrani自己說他的Lasso是受到BreimanNon-Negative GarroteNNG)的啟發。 LassoNNG的兩步合併為一步,即L1-norm regularizationLasso的巨大優勢在於它所構造的模型是Sparse的,因為它會自動地選擇很少一部分變數構造模型。現在,Lasso 已經家喻戶曉了,但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說,可能是由下面幾個原因造成的:1. 速度問題:當時電腦求解Lasso的速度太慢;2. 理解問題:大家對Lasso模型的性質理解不夠(直到EfronLAR出來後大家才搞明白);3. 需求問題:當時還沒有遇到太多高維資料分析的問題,對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理: 1.千里馬常有,而伯樂不常有(沒有EfronLARLasso可能很難有這麼大的影響力)。2.時勢造英雄(高維資料分析的問題越來越多,比如 Bioinformatics領域)。3.金子總是會閃光的。
LARLasso L1-norm regularization)和Boosting真正的聯繫起來,如同打通了任督二脈(數學細節可以參考本人的一個小結[1], 當然最好還是親自拜讀Efron的原著)。LAR結束了一個晦澀的時代:在LAR之前,有關Sparsity的模型幾乎都是一個黑箱,它們的數學性質(更 不要談古典的幾何性質了)幾乎都是缺失。LAR開啟了一個光明的時代:有關Sparsity的好文章如雨後春筍般地湧現,比如CandesTao Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensingCandes & Tao, Donoho)也與LAR一脈相承,只是更加強調L1-norm regularization其他方面的數學性質,比如Exact Recovery。我覺得這是一個問題的多個方面,Lasso關注的是構建模型的準確性,Compressed sensing關注的是變數選擇的準確性。由此引起的關於Sparsity的研究,猶如黃河氾濫,一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣(現在流行的使用者推薦系統用到的Collaborative filtering的數學原理源於此)。有興趣的童鞋可以參考我個人的小結[2]
還必須提到的是演算法問題。我個人覺得,一個好的模型,如果沒有一個快速準確的演算法作為支撐的話,它最後可能什麼也不是。看看Lasso頭幾年的冷遇 就知道了。LAR的成功除了它漂亮的幾何性質之外,還有它的快速演算法。LAR的演算法複雜度相當於最小二乘法的複雜度,這幾乎已經把Lasso問題的求解推 向極致。這一記錄在2007年被FriedmanCoordinate DescentCD)刷新,至今沒人打破。Hastie教授趣稱這個為“FFTFriedman + Fortran + Tricks。因為CDGeneralized Lasso問題並不能一網打盡,許多凸優化解法應運而生,如Gradient Projection Proximal methodsADMM (Alternating Direction Method of Multipliers) (Split) Bregman methodsNesterov’s method (一階梯度法中最優的收斂速度,Candes 的很多套裝軟體都根據這個方法設計) 等等。哪個方法更好呢?這個就像問誰的武功天下第一一樣。我只能回答王重陽以後再也沒有天下第一了,東邪西毒南帝北丐,他們各有各的所長,有的功夫 是這個人擅長一些,而另外幾門功夫又是另一個人更擅長一些。有關L1的演算法可能還會大量湧現,正如優化大師Stephen Boyd所說(2010928日):“God knows the last thing we need is another algorithm for the Lasso.”
最後我想以討論模糊系統統計學習來結尾。這個話題非常具有爭議,我就冒天下之大不諱吧,談一談我這幾年的學習體會。記得十年前,立新老師 曾經寫過一篇文章《模糊系統:挑戰與機遇並存——十年研究之感悟》,發表在2001年《自動化學報》上。我2005年看到的時候,敬仰之情,猶如滔滔江 水。立新老師曾經有這麼一句話:“If a method works well in practice, there must be some theoretical reasons for its success.”2005年的時候,我開始問自己什麼使模糊系統的成功?立新老師認為有如下幾個原因:1.模糊系統的通用逼近性能(Universal Approximator);2.模糊系統快速的構造演算法,比如他自己的WM方法,Roger JangANFIS等等;3.結果的可解釋性;4.利用各種不同形式的資訊。
下面我談談自己的看法,第一,通用逼近性能當然是一個好的性質,它表明模糊系統是很flexible的,但flexible的結構太多了,比如神經 網路。問題往往不在flexible,而在太flexible導致overfitting。就如同SVM一樣,沒有L2-norm regularization,實踐中的性能就會變得很差。第二,快速演算法,這是好的方法必備的,SVMBoostingRandom Forest的演算法都很快,而且可以直接用到高維,這一點上,我沒有看到模糊系統的優勢。第三,可解釋性:模糊系統對低維資料(比如2-4維)的確具有好 的解釋性(因為IF-THEN規則的前提和結論都很簡潔),但這個時候其它工具也可以做得到,比如Gradient BoostingRandom Forests(很多例子可以在ESL這本書裡看到)。第四,充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識,並 在他的書裡面詳細給出實例。遺憾的是,這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢?我個人看不到它們特殊的優勢。然而,在 統計學習裡,利用不同的先驗知識處理高維空間的例子比比皆是,比如Sparsitygroup-structuresmoothness等等。現在舉 一個Gradient Boosting  machineGBM,也叫MART)的例子來說明我的觀點。根據LassoBoosting的關係,可以知道GBM已經用到了Sparsity的性 質(L1-norm regularization)。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度(depth),控制每棵決策樹的深度 。如果深度為1,即樹樁結構(Stump),表明GBM將採用加法模型(Generalized Additive model),即不考慮變數之間的互動式作用(Interaction);如果深度大於1,則考慮互動式作用。因為互動式作用在非線性建模中比較重要,如 異或(XOR)問題,沒有考慮互動式作用將失敗得很慘,所以這個參數設置反映了對非線性建模的先驗。第二個參數是Shrinkage的大小。假設深度選取 是合理的,在雜訊比較小的時候,沒有Shrinkage會比較好;雜訊比較大的時候,有Shrinkage會好一些。實踐中,使用GBM對高維資料分析, 試錯法(Trial and error)很容易使用,因為就這兩個參數(通常depth=34;實際資料的雜訊往往比較大,推薦設置Shrinkage=0.01)。模型構建好之 後,GBM會告訴你哪些變數是重要的,變數之間的互動式作用如何等等,這樣模型的結果也是比較容易理解。Random Forests也有相似的功能。好了,最後借Hastie教授的一幅圖來總結一下,無疑,GBMMART)是他們的最愛,也是我的最愛。

Characteristics of some statistical models


[轉]決策樹模型組合之隨機森林與GBDT


SVM的基本原理普遍表述為,SVM通過非線性變換把原空間映射到高維空間,然後在這個高維空間構造線性分類器,因為在高維空間資料點更容易分開。 甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣理解SVM的基本原理,我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實:SVM在高維空間裡構建 分類器後,為什麼這個分類器不會對原空間的資料集Overfitting呢?要理解SVM的成功,我覺得可以考慮以下幾個方面:第一,SVM求解最優分類 器的時候,使用了L2-norm regularization,這個是控制Overfitting的關鍵。第二,SVM不需要顯式地構建非線性映射,而是通過Kernel trick完成,這樣大大提高運算效率。第三,SVM的優化問題屬於一個二次規劃(Quadratic programming),優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法,比如SMOSequential minimal optimization)解法。第四,Vapnika的統計學習理論為SVM提供了很好的理論背景(這點不能用來解釋為什麼SVM這麼popular, 因為由理論匯出的boundloose)。於是SVM成功了,火得一塌糊塗!
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂就是比隨機猜要好一點點;就是強啦。這個想法可以追溯到由Leslie Valiant教 授(2010年圖靈獎得主)在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗,再好的理論也需要有效的演算法來執行。終於功夫不負有 心人, Schapire1996年提出一個有效的演算法真正實現了這個夙願,它的名字叫AdaBoostAdaBoost把多個不同的決策樹用一種非隨機的方 式組合起來,表現出驚人的性能!第一,把決策樹的準確率大大提高,可以與SVM媲美。第二,速度快,且基本不用調參數。第三,幾乎不 Overfitting。我估計當時BreimanFriedman肯定高興壞了,因為眼看著他們提出的CART正在被SVM比下去的時 候,AdaBoost讓決策樹起死回生!Breiman情不自禁地在他的論文裡讚揚AdaBoost是最好的現貨方法(off-the-shelf,即拿下了就可以用的意思)。其實在90年代末的時候,大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年,Friedman的一篇技術 報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑(沒有解釋AdaBoost為什麼不容易Overfitting,這個問題好像至今還沒有定論),即搞清楚了 AdaBoost在優化什麼指標以及如何優化的。基於此,Friedman提出了他的GBMGradient Boosting Machine,也叫MART或者TreeNet)。幾乎在同時,Breiman另闢蹊徑,結合他的Bagging (Bootstrap aggregating) 提出了Random Forest (今天微軟的Kinect裡面就採用了Random Forest,相關論文Real-time Human Pose Recognition in Parts from Single Depth ImagesCVPR2011best paper)。
有一個關於Gradient Boosting細節不得不提。Friedman在做實驗的時候發現,把一棵新生成的決策樹,記為f_m,加到當前模型之前,在這棵決策樹前乘以一個小的 數,即v×f_m(比如v=0.01),再加入到當前模型中,往往大大提高模型的準確度。他把這個叫做“Shrinkage”。接下 來,HastieTibshiraniFriedman進一步發現(我發現大師們都是親自動手寫程式做實驗的),如果把具有Shrinkage Gradient Boosting應用到線性回歸中時,得到的Solution PathLassoSolution Path驚人地相似(如圖所示)!他們把這一結果寫在了ESL的第一版裡,並推測這二者存在著某種緊密的聯繫,但精確的數學關係他們當時也不清楚。 Tibshirani說他們還請教了斯坦福的優化大師(我估計是Stephen Boyd),但還是沒有找到答案。

Lasso & Boosting

後來Tibshirani找到自己的恩師EfronTibshirani“The Science of Bradley Efron”這本書的序言裡寫道,He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm, ‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on the Lasso.”我就不逐字逐句翻譯了,大意是:Efron獨自擺平了這個問題,與此同時發明了“Least angle regression (LAR)”Efron結論是LassoBoosting的確有很緊密的數學聯繫,它們都可以通過修改LAR得到。更令人驚歎的是LAR具有非常明確 的幾何意義。於是,Tibshirani在序言中還有一句,In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind: geometric insight and analysis.Prof Efron的文章,可以感受到古典幾何學與現代統計學的結合之美(推薦大家讀讀Efron教授2010年的一本新書Large-Scale Inference,希望以後有機會再寫寫這方面的體會)!總之,Efron的這篇文章是現代統計學的里程碑,它結束了一個時代,開啟了另一個時代。
這裡,想補充說明一下Lasso的身世,它的全稱是The Least Absolute Shrinkage and Selection Operator,讀音不是[‘læso]而是[læ’su:],有中文翻譯為套索,個人覺得這個翻譯不好,太遠離它本來的含義,不如就用 LassoTibshrani自己說他的Lasso是受到BreimanNon-Negative GarroteNNG)的啟發。 LassoNNG的兩步合併為一步,即L1-norm regularizationLasso的巨大優勢在於它所構造的模型是Sparse的,因為它會自動地選擇很少一部分變數構造模型。現在,Lasso 已經家喻戶曉了,但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說,可能是由下面幾個原因造成的:1. 速度問題:當時電腦求解Lasso的速度太慢;2. 理解問題:大家對Lasso模型的性質理解不夠(直到EfronLAR出來後大家才搞明白);3. 需求問題:當時還沒有遇到太多高維資料分析的問題,對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理: 1.千里馬常有,而伯樂不常有(沒有EfronLARLasso可能很難有這麼大的影響力)。2.時勢造英雄(高維資料分析的問題越來越多,比如 Bioinformatics領域)。3.金子總是會閃光的。
LARLasso L1-norm regularization)和Boosting真正的聯繫起來,如同打通了任督二脈(數學細節可以參考本人的一個小結[1], 當然最好還是親自拜讀Efron的原著)。LAR結束了一個晦澀的時代:在LAR之前,有關Sparsity的模型幾乎都是一個黑箱,它們的數學性質(更 不要談古典的幾何性質了)幾乎都是缺失。LAR開啟了一個光明的時代:有關Sparsity的好文章如雨後春筍般地湧現,比如CandesTao Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensingCandes & Tao, Donoho)也與LAR一脈相承,只是更加強調L1-norm regularization其他方面的數學性質,比如Exact Recovery。我覺得這是一個問題的多個方面,Lasso關注的是構建模型的準確性,Compressed sensing關注的是變數選擇的準確性。由此引起的關於Sparsity的研究,猶如黃河氾濫,一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣(現在流行的使用者推薦系統用到的Collaborative filtering的數學原理源於此)。有興趣的童鞋可以參考我個人的小結[2]
還必須提到的是演算法問題。我個人覺得,一個好的模型,如果沒有一個快速準確的演算法作為支撐的話,它最後可能什麼也不是。看看Lasso頭幾年的冷遇 就知道了。LAR的成功除了它漂亮的幾何性質之外,還有它的快速演算法。LAR的演算法複雜度相當於最小二乘法的複雜度,這幾乎已經把Lasso問題的求解推 向極致。這一記錄在2007年被FriedmanCoordinate DescentCD)刷新,至今沒人打破。Hastie教授趣稱這個為“FFTFriedman + Fortran + Tricks。因為CDGeneralized Lasso問題並不能一網打盡,許多凸優化解法應運而生,如Gradient Projection Proximal methodsADMM (Alternating Direction Method of Multipliers) (Split) Bregman methodsNesterov’s method (一階梯度法中最優的收斂速度,Candes 的很多套裝軟體都根據這個方法設計) 等等。哪個方法更好呢?這個就像問誰的武功天下第一一樣。我只能回答王重陽以後再也沒有天下第一了,東邪西毒南帝北丐,他們各有各的所長,有的功夫 是這個人擅長一些,而另外幾門功夫又是另一個人更擅長一些。有關L1的演算法可能還會大量湧現,正如優化大師Stephen Boyd所說(2010928日):“God knows the last thing we need is another algorithm for the Lasso.”
最後我想以討論模糊系統統計學習來結尾。這個話題非常具有爭議,我就冒天下之大不諱吧,談一談我這幾年的學習體會。記得十年前,立新老師 曾經寫過一篇文章《模糊系統:挑戰與機遇並存——十年研究之感悟》,發表在2001年《自動化學報》上。我2005年看到的時候,敬仰之情,猶如滔滔江 水。立新老師曾經有這麼一句話:“If a method works well in practice, there must be some theoretical reasons for its success.”2005年的時候,我開始問自己什麼使模糊系統的成功?立新老師認為有如下幾個原因:1.模糊系統的通用逼近性能(Universal Approximator);2.模糊系統快速的構造演算法,比如他自己的WM方法,Roger JangANFIS等等;3.結果的可解釋性;4.利用各種不同形式的資訊。
下面我談談自己的看法,第一,通用逼近性能當然是一個好的性質,它表明模糊系統是很flexible的,但flexible的結構太多了,比如神經 網路。問題往往不在flexible,而在太flexible導致overfitting。就如同SVM一樣,沒有L2-norm regularization,實踐中的性能就會變得很差。第二,快速演算法,這是好的方法必備的,SVMBoostingRandom Forest的演算法都很快,而且可以直接用到高維,這一點上,我沒有看到模糊系統的優勢。第三,可解釋性:模糊系統對低維資料(比如2-4維)的確具有好 的解釋性(因為IF-THEN規則的前提和結論都很簡潔),但這個時候其它工具也可以做得到,比如Gradient BoostingRandom Forests(很多例子可以在ESL這本書裡看到)。第四,充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識,並 在他的書裡面詳細給出實例。遺憾的是,這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢?我個人看不到它們特殊的優勢。然而,在 統計學習裡,利用不同的先驗知識處理高維空間的例子比比皆是,比如Sparsitygroup-structuresmoothness等等。現在舉 一個Gradient Boosting  machineGBM,也叫MART)的例子來說明我的觀點。根據LassoBoosting的關係,可以知道GBM已經用到了Sparsity的性 質(L1-norm regularization)。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度(depth),控制每棵決策樹的深度 。如果深度為1,即樹樁結構(Stump),表明GBM將採用加法模型(Generalized Additive model),即不考慮變數之間的互動式作用(Interaction);如果深度大於1,則考慮互動式作用。因為互動式作用在非線性建模中比較重要,如 異或(XOR)問題,沒有考慮互動式作用將失敗得很慘,所以這個參數設置反映了對非線性建模的先驗。第二個參數是Shrinkage的大小。假設深度選取 是合理的,在雜訊比較小的時候,沒有Shrinkage會比較好;雜訊比較大的時候,有Shrinkage會好一些。實踐中,使用GBM對高維資料分析, 試錯法(Trial and error)很容易使用,因為就這兩個參數(通常depth=34;實際資料的雜訊往往比較大,推薦設置Shrinkage=0.01)。模型構建好之 後,GBM會告訴你哪些變數是重要的,變數之間的互動式作用如何等等,這樣模型的結果也是比較容易理解。Random Forests也有相似的功能。好了,最後借Hastie教授的一幅圖來總結一下,無疑,GBMMART)是他們的最愛,也是我的最愛。

Characteristics of some statistical models


[轉]邏輯回歸與決策樹在分類上的一些區別


行銷預測模型的目標變數很多為一種狀態或類型,如客戶還是不買、客戶選擇上網方式為寬頻還是撥號、行銷戰通道是郵件、電話、還是網路。我們把這類問題統稱為分類。決策樹和邏輯回歸都是解決分類問題的高手。用不同的演算法解答同樣的問題,自然引出了兩者孰優孰劣的討論,但迄今為止,仍然沒有一個明確的結 論。出現這種情況是意料之中的,因為兩者的具體表現取決於資料狀況和挖掘人員的水準。從演算法本身看,決策樹和回歸各有優勢,因此最好的應用不是兩者擇一, 而是相互取捨,利用一方的長處彌補另一方的不足。



在進一步討論之前,讓我們來看一下邏輯回歸和決策樹的主要差別。


些分歧是表面的,例如決策樹可以對付缺失值,而邏輯回歸需要挖掘人員預先對缺失資料進行處理。但實際上決策樹同樣要對缺失值做出某種假設和處理。例如 CART在遇到一個變數中有缺失情況時,是用次級變數進行替換切分。這種做法在邏輯回歸中也可以辦到,但需要單獨的程式設計。而在決策樹中,這一步已經嵌入軟 件的演算法引擎。


實質上看,決策樹和邏輯回歸的分歧是:1.邏輯回歸對資料整體結構的分析優於決策樹,而決策樹對局部結構的分析優於邏輯回歸。2.邏輯回歸擅長分析線性關 系,而決策樹對線性關係的把握較差。雖然對付非線性關係是決策樹的強項,但是很多非線性關係完全可以用線性關係作為近似,而且效果很好。線性關係在實踐中 有很多優點:簡潔,易理解,可以在一定程度上防止對資料的過度擬合。3.邏輯回歸對極值比較敏感,容易受極端值的影響,而決策樹在這方面表現較好。


者的差別主要來自演算法邏輯。決策樹由於採用分割的方法,所以能夠深入資料細部,但同時失去了對全域的把握。一個分層一旦形成,它和別的層面或節點的關係就 被切斷了,以後的挖掘只能在局部中進行。同時由於切分,樣本數量不斷萎縮,所以無法支援對多變數的同時檢驗。而邏輯回歸,始終著眼整個資料的擬合,所以對 全域把握較好。但無法兼顧局部資料,或者說缺乏探查局部結構的內在機制。


外,邏輯回歸和決策樹還有一些應用上的區別。決策樹的結果和邏輯回歸相比略顯粗糙。邏輯回歸原則上可以提供資料中每個觀察點的概率,而決策樹只能把挖掘對 象分為有限的概率組群。比如決策樹確定17個節點,全部人口就只能有17個概率,在應用上受到一定限制。就操作來說,決策樹比較容易上手,需要的資料預處 理較少,而邏輯回歸則要求一定的訓練和技巧。


於兩者間互補或增強,主要思路是利用決策樹對局部資料結構優越的把握能力增加邏輯回歸的效力。在具體做法上有幾種,一種是從決策樹分析中找出資料局部結 構,作為在邏輯回歸中構建依變數(interaction)的依據。另一種是在需要對預測因數進行離散化處理時,利用決策樹分析決定最佳切分點。還有一種 是把決策樹分類的最終結果作為預測變數,和其他協變數一起代入回歸模型,又稱為嫁接式模型。從理論上講,嫁接模型綜合了決策樹和邏輯回歸的優點。最終 節點包含了資料中重要的局部結構,而協變數可以拾補被決策樹遺漏的資料整體結構。


接模型是一個很巧妙的設計,但是在實踐中並沒有得到普遍的認同。由於決策樹已經對資料進行了最大限度的擬合,所以留給協變數的餘地很小。換句話說,把決策 樹的最終節點作為預測因數,就可能找不出還有獨立作用的協變數。而沒有協變數,邏輯回歸實際只是決策樹的重複。再有,由於節點是多個屬性的綜合,不易解 釋。每個節點到底代表什麼不明確,由此限制了這種方法的推廣。





[轉]資料採擷十大經典演算法


國際權威的學術組織the IEEE International Conference on Data Mining (ICDM) 200612月評選出了資料採擷領域的十大經典演算法:C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.

不僅僅是選中的十大演算法,其實參加評選的18種演算法,實際上隨便拿出一種來都可以稱得上是經典演算法,它們在資料採擷領域都產生了極為深遠的影響。
1. C4.5
C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法. C4.5演算法繼承了ID3演算法的優點,並在以下幾方面對ID3演算法進行了改進:
1) 用資訊增益率來選擇屬性,克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足;
    2)
在樹構造過程中進行剪枝;
    3)
能夠完成對連續屬性的離散化處理;
    4)
能夠對不完整資料進行處理。
C4.5演算法有如下優點:產生的分類規則易於理解,準確率較高。其缺點是:在構造樹的過程中,需要對資料集進行多次的順序掃描和排序,因而導致演算法的低效。
2. The k-means algorithm K-Means演算法
k-means algorithm演算法是一個聚類演算法,把n的物件根據他們的屬性分為k個分割,k < n。它與處理混合正態分佈的最大期望演算法很相似,因為他們都試圖找到資料中自然聚類的中心。它假設物件屬性來自于空間向量,並且目標是使各個群組內部的均方誤差總和最小。
3. Support vector machines
支援向量機,英文為Support Vector Machine,簡稱SV機(論文中一般簡稱SVM)。 它是一種監督式學習的方法,它廣泛的應用於統計分類以及回歸分析中。支持向量機將向量映射到一個更高維的空間裡,在這個空間裡建立有一個最大間隔超平面。 在分開資料的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大,分類器的總誤差越小。 一個極好的指南是C.J.C Burges的《模式識別支援向量機指南》。van der Walt Barnard 將支持向量機和其他分類器進行了比較。
4. The Apriori algorithm
Apriori演算法是一種最有影響的挖掘布林關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推算法。該關聯規則在分類上屬於單維、單層、布林關聯規則。在這裡,所有支持度大於最小支持度的項集稱為頻繁項集,簡稱頻集。
5. 最大期望(EM)演算法
在統計計算中,最大期望(EMExpectation–Maximization)演算法是在概率(probabilistic)模型中尋找參數最大似然估計的演算法,其中概率模型依賴於無法觀測的隱藏變數(Latent Variabl)。最大期望經常用在機器學習和電腦視覺的資料集聚(Data Clustering)領域。
6. PageRank
PageRankGoogle演算法的重要內容。20019月被授予美國專利,專利人是Google創始人之一拉裡·佩奇(Larry Page)。因此,PageRank裡的page不是指網頁,而是指佩奇,即這個等級方法是以佩奇來命名的。
PageRank根據網站的外部連結和內部連結的數量和品質倆衡量網站的價值。PageRank背後的概念是,每個到頁面的連結都是對該頁面的一次投票,被連結的越多,就意味著被其他網站投票越多。這個就是所謂的連結流行度”——衡量多少人願意將他們的網站和你的網站掛鉤。PageRank這個概念引自學術中一篇論文的被引述的頻度——即被別人引述的次數越多,一般判斷這篇論文的權威性就越高。
7. AdaBoost
Adaboost是一種反覆運算演算法,其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器),然後把這些弱分類器集合起來,構成一個更強的最終分類器 (強分類器)。其演算法本身是通過改變資料分佈來實現的,它根據每次訓練集之中每個樣本的分類是否正確,以及上次的總體分類的準確率,來確定每個樣本的權值。將修改過權值的新資料集送給下層分類器進行訓練,最後將每次訓練得到的分類器最後融合起來,作為最後的決策分類器。
8. kNN: k-nearest neighbor classification
K最近鄰(k-Nearest NeighborKNN)分類演算法,是一個理論上比較成熟的方法,也是最簡單的機器學習演算法之一。該方法的思路是:如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別。
9. Naive Bayes
在眾多的分類模型中,應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型(Naive Bayesian ModelNBC)。 樸素貝葉斯模型發源於古典數學理論,有著堅實的數學基礎,以及穩定的分類效率。同時,NBC模型所需估計的參數很少,對缺失資料不太敏感,演算法也比較簡單。理論上,NBC模型與其他分類方法相比具有最小的誤差率。但是實際上並非總是如此,這是因為NBC模型假設屬性之間相互獨立,這個假設在實際應用中往往是不成立的,這給NBC模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時,NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時,NBC模型的性能最為良好。
10. CART: 分類與回歸樹
CART, Classification and Regression Trees 在分類樹下面有兩個關鍵的思想。第一個是關於遞迴地劃分引數空間的想法;第二個想法是用驗證資料進行剪枝。

[轉]搜索時代->推薦時代


最近在做推薦系統的專案,所以也搜羅了一些相關的綜述和資料。所謂的Web3.0,推薦系統就是典型的影子,你想要的資訊能夠主動找到你,並且在合適的時候出現在合適的地方,智慧。

其實推薦系統國內外研究都很熱,而且原型系統也有很多了。目前幾乎所有大型的電子商務系統,如AmazonCDNOWNetflix等,都不同程度地使用了各種形式的推薦系統。而近來以發現為核心的網站 正開始在互聯網上嶄露頭角,比如側重於音樂推薦的八寶盒,側重於圖書推薦的豆瓣等等。而且,去年國內也出現了第一家創業公司百分點科技。 那麼,到底什麼是推薦引擎,個性化推薦的前提、基本形式、具體應用有哪些呢?
推薦引擎利用特殊的資訊過濾(IFInformation Filtering)技術,將不同的內容(例如電影、音樂、書籍、新聞、圖片、網頁等)推薦給可能感興趣的用戶。通常情況下,推薦引擎的實現是通過將用戶 的個人喜好與特定的參考特徵進行比較,並試圖預測用戶對一些未評分項目的喜好程度。參考特徵的選取可能是從專案本身的資訊中提取的,或是基於用戶所在的社 會或社團環境。
在搜索領域,勝負已經非常明顯.在國外,Google遙遙領先,在國內,百度一枝獨秀。但是,起碼到目前為止,還沒有哪個推薦引擎是當之無愧的市場 領導 者。建造個性化的發現機制需要對目前網上所有的表述、分類及評價方式進行深入研究,這絕非易事。但是如果有公司可以把這樣的東西做到這些,那麼,這樣的發 現工具不僅僅可以改變行銷,甚至整個商業社會。
根據如何抽取參考特徵,我們可以將推薦引擎分為以下四大類:
基於內容的推薦引擎:它將計算得到並推薦給用戶一些與該用戶已選擇過的專案相似的內容。例如,當你在網上購書時,你總是購買與歷史相關的書籍,那麼基於 內容的推薦引擎就會給你推薦一些熱門的歷史方面的書籍。
基於協同過濾的推薦引擎:它將推薦給用戶一些與該用戶品味相似的其他使用者喜歡的內容。例如,當你在網上買衣服時,基於協同過濾的推薦引擎會根據你的歷史 購買記錄或是流覽記錄,分析出你的穿衣品位,並找到與你品味相似的一些用戶,將他們流覽和購買的衣服推薦給你。
基於關聯規則的推薦引擎:它將推薦給使用者一些採用關聯規則發現演算法計算出的內容。關聯規則的發現演算法有很多,如 AprioriAprioriTidDHPFP-tree 等。
混合推薦引擎:結合以上各種,得到一個更加全面的推薦效果。
隨著互聯網上資料和內容的不斷增長,人們越來越重視推薦引擎在互聯網應用中的作用。可想而知,由於互聯網上的資料過多,使用者很難找到自己想要的資訊,通過 提供搜索功能來解決這個問題是遠遠不夠的。推薦引擎可以通過分析使用者的行為來預測用戶的喜好,使用戶能更容易找到他們潛在需要的資訊。這裡以電子商務應用 中的推薦引擎為例來說明推薦引擎在互聯網應用中的重要性。


[轉]關聯規則挖掘之空間關聯


關聯規則挖掘的根本目的是尋找商品銷售記錄中的相關性,從而更好地指導銷售策略的制定。一個典型的規則是:“43% 買了雀巢即溶咖啡的顧客都會購買雀巢咖啡伴侶”。基於這個規則,在實體超市中,應當把這兩種產品放到相近的地方,而在網上超市中,如果顧客購買了雀巢即溶 咖啡卻沒有購買咖啡伴侶,則可以在關聯商品欄目中添加相應的推薦。現在很多企業已經認識到詳細的原始購買記錄的重要性,並且建立了規範的資料倉庫,這些都 為關聯規則挖掘技術的應用奠定了良好的基礎。
商品之間關聯規則可以分為空間關聯和時間關聯兩種,時間關聯又可以分為週期關係和順序關聯兩種。在一般研究中提到的關聯規則,其實僅僅是空間關聯[1],也就是在同一個時間(同一次購買)裡,對消費者經常一起購買的商品進行分析,這也是所謂“購物籃分析”的主要支撐技術。
在介紹空間關聯之前,我們再回顧一下關聯規則挖掘中最經典的例子——啤酒與尿布的關聯。沃爾瑪通過對原始交易資料的分析,發現 尿布一起購買最多的商品竟是啤酒!調查顯示,美國的太太們常叮囑她們的丈夫下班後為小孩買尿布,而丈夫們在買尿布後又隨手帶回了他們喜歡的啤酒。對於隱藏 在啤酒和尿布這類表面上風馬牛不相及的商品背後的關聯,如果不通過資料採擷的技術,是沒有辦法靠拍腦袋的辦法想出來的。

附表1:消費者購買記錄示例
消費者/商品
生泥鰍
綠豆
分歧終端機
任意門
滿神牌洗髮水
A
×
×
×
B
×
×
C
×
×
×
D
×
E
×
×

最常見的關聯規則挖掘技術,是所謂的“支援-置信”分析。我們還是以消費者在超市購買商品為例,如果把每一個消費者的一次購買看作一個事件,考慮從商品X到商品Y的關聯規則,支援度是指在所有事件中同時購買商品X和商品Y的比例,置信度則是在所有購買了商品X的事件中也購買商品Y的比例[1][1]。如果支持度和置信度都超過了相應的閾值,則從XY的規則被認為是有效的。附表1給出了一個示例,如果把支持度和置信度的閾值分別設為50%60%,則從生泥鰍到綠豆的規則是有效的(支援度為60%,置信度為75%),而從分歧終端機到任意門的規則是無效的(支援度40%,置信度100%)。對於一個銷售量非常大的電子商務企業或者實體超市,支援度往往是千分之一甚至萬分之一這樣的數量級,在難以選擇合適的置信度閾值的時候,可以按照置信度從高到低的優先順序進行商品推薦。
“支持- 信”分析存在很多缺陷,譬如說需要人為設定支援度閾值——如果閾值太低,則會出現很多可信度很低的關聯規則,僅僅可能來自于個別消費者偶然的行為,如果閾 值太高,很多冷門商品之間的關聯規則無法被挖掘出來。一種可能的替代方法是直接分析商品之間銷售記錄的相似度,認為與商品X關聯最強的商品就是和它相似性最大的商品。這時候需要注意兩點,首先,一般的相似度指標[2]都是對稱的[2][2],也就是說XY的相似性與YX的相似性相同,但是此處要選擇不對稱的定義方式[3]。譬如說商品X賣了10000件,商品Y賣了5件,其中XY共同賣了5次。那麼給一個購買了X的消費者推薦Y不一定合適,因為只有千分之零點五的購買概率,而給一個購買了Y的消費者推薦X就比較靠譜,因為看起來似乎買了Y的消費者都會買X。這就是為什麼要選擇不對稱的相似度指標的原因。其次,因為放棄了支持度閾值,會造成一個銷量很低的產品因為隨機波動的原因出現非常高的關聯,這個時候往往要通過對銷量低的商品相似度進行懲罰,懲罰的力度可以設定為商品銷售量(或者包含該商品的事件數目)的方根倒數[4]。舉例而言,在為商品X選擇關聯商品的時候,如果商品Y銷售了49次,則商品Y對應的相似度應該減去1/7。商品賣得越好,可信度越高,懲罰也越少。
剛才說了支持度的缺陷,另外一個缺陷體現在置信度上。考慮一個銷售量很大的商品X(設銷售事件總數為100萬,包含該商品的銷售事件數為5萬)和一個銷售量很小的商品Y(包含該商品的銷售事件數為200),假設商品XY之間的銷售完全是獨立的,那麼在Y看來,商品X的置信度為5/100=0.05;而在X看來,和Y關聯置信度是200/10=0.002 也就是說,在一對產品的銷售記錄超過了支援度閾值的條件下,系統總是傾向於推薦銷售量大的產品。我們曾將在某家網上超市的關聯推薦欄中發現,當該超市超低 價促銷蘇菲衛生巾的時候,不管購買軍刀、箱包、零食,都會推薦蘇菲衛生巾;而當該超市力推金龍魚油的時候,則經常在推薦欄中連續出現多款金龍魚油,儘管你 只是買了50支一次性紙杯。這些推薦會造成廣告資訊冗餘(首頁上已經用更大幅的廣告低價促銷了),並且用戶體驗較差(用戶理解不了這些關聯,會認為這不是來源於一種資料採擷技術,而是一種打著資料採擷幌子的變相廣告投放)。從資訊熵[5]或者資源配置[6]的角度出發,在設計相似度指標的時候,適度向少量較少的長尾商品傾斜,有望大幅度提高關聯規則挖掘的價值。

[1] J. Hipp, U. Güntzer, G. Nakhaeizadeh, Algorithms for association rule mining - A general survey and comparison, SIGKDD Explorations 2(2) (2000) 1-58.
[2] L. Lü, T. Zhou, Link prediction in complex networks: a survey, Physica A 390 (2011) 1150-1170.
[3] T. Zhou, J. Ren, M. Medo, Y. –C. Zhang, Bipartite network projection and personal recommendation, Physical Review E 76 (2007) 046115.
[4] M. Medo, Y.-C. Zhang, T. Zhou, Adaptive model for recommendation of news, Europhysics Letters 88 (2009) 38005.
[5] L. A. Adamic, E. Adar, Friends and neighbors on the Web, Social Networks 25(3)             (2003) 211-230      .
[6] T. Zhou, L. Lü, Y.-C. Zhang, Predicting missing links via local information, European Physical Journal B 71 (2009) 623-630.