Saturday, September 09, 2017

Python Spark ML(六):Decision Tree Algorithm Survey

Python Spark ML(六):Decision Tree Algorithm Survey

2017/09/08

作業六:

請解釋圖2左邊各 features 以及其選項的意義。

作業請以文章的方式將 GitHub 連結回應到本篇文章在 Python Taiwan 的連結處:
https://www.facebook.com/groups/pythontw/permalink/10156862362473438/

-----

前言:

這是 Python Spark ML 的第一週。

這週我花了不少時間看本活動的教科書 [1],以及蒐集、整理網路上的資料 [2]。

當學生的時候,我其實不喜歡寫作業的。現在算是「當」老師吧!我要勉勵大家,規定的作業,「儘量」好好完成。作業的目的,其實是要輔助你好好瞭解一門科目。

套句歌詞:+1 是簡單的,交作業是困難的。很難的東西,如果你能拆成小塊,就簡單多了。

本篇之後,在下一篇之前,我們大概得花不少時間來消化資料。

整個活動有可能超過一年(如果有認真的同學持續交作業)。如果你能順利走過,一年後你就是炙手可熱、企業爭相追逐的「機器學習專家」了!

-----

Outline

一、決策樹的分類。
二、多棵決策樹。 
三、主要的決策樹演算法。
四、決策樹的歷史演進。

-----

一、決策樹的分類(單棵決策樹)。

本活動的主要目的之一是在 Python Spark 的 ML 環境,分別以 RDD / MLlib 與 DataFrame / ML Pipeline 實作:決策樹二元分類、決策樹多元分類、決策樹迴歸分析 [1]。

配合上述之目的,在上次的資料搜尋中 [2],我們知道,決策樹有兩種主要類型 [3]:

1.1. 分類樹。
1.2. 迴歸樹。

其中,分類樹可用於二元分類與多元分類,迴歸樹可用於迴歸分析。

「分類與迴歸樹 Classification And Regression Trees (CART)」此概念在 [14] 中被提出。

-----

二、多棵決策樹 [4]。

2.1. 裝袋算法(Bagging)。
2.2. 隨機森林(Random Forest)。
2.3. 提升樹(Boosting Tree)。
2.4. 旋轉森林(Rotation forest)。

多棵決策樹的方法,並非本活動的主要目的,但部分如隨機森林等在實作中也會遇到。此處先列出作為參考。

-----

三、主要的決策樹演算法。

圖1是 [5] 列出的主要決策樹演算法。配合稍早 [2] 的部分文獻 [3]-[6],我們可以將圖1再補上 MARS [6], [7]。

3.1. ID3 (Iterative Dichotomiser 3)
3.2. C4.5 (Improvement of ID3)
3.3. CART (Classification And Regression Trees)
3.4. CHAID (Chi-square Automatic Interaction Detector)
3.5. MARS (Multivariate Adaptive Regression Splines)

「常用的屬性選擇指標:
1. 資訊獲利(Information gain):ID3、C4.5、C5.0。
2. 吉尼係數(Gini Index):CART。
3. X平方獨立性檢定:CHAID 。」[22]


Fig. 1. Decision tree algorithms [5].


Fig. 2. Comparison of classification tree methods [8].
 
-----

四、決策樹的歷史演進。

4.0.1. AID (Automatic Interaction Detector) - regression tree
4.0.2. THAID (Theta Automatic Interaction Detector) - classification tree

4.1. ID3 - classification tree
4.2. C4.5 - classification tree
4.3. CART - classification tree and regression tree
4.4. CHAID
4.5. MARS

-----

4.0.1 AID

「Historically, the first regression tree algorithm is AID [9], which appeared several years
before THAID. 」[8]
根據 [8],歷史上,最早的迴歸樹演算法是 AID [9],比 THAID 還要早上幾年。

-----

4.0.2. THAID

「The first published classification tree algorithm is THAID [10], [11]. 」[8]
根據 [8],第一個發表的分類樹演算法是 THAID [10], [11]。

-----

4.1. ID3 [12]

「ID3以選擇最大的資訊獲利值作為分類屬性,以熵(Entropy)為基礎 熵用來衡量資料的一致性,當作資訊量凌亂程度(不確定性)的指標,熵越大代表凌亂程度越大 在資料集合S中,屬性A的資料獲利表示為Gain(S,A) 。當Gain值越大,表示屬性A中資料凌亂程度越小,分類資料越佳。因此,Gain值在同層屬性中越大的,該屬性即會作為分割節點 然而,ID3演算法的缺點在於資訊獲利會傾向選擇擁有許多不同數值的屬性(因為會產生許多分支,分支內資訊量少,所以凌亂度低)。照此方式無法得出有意義的決策樹,因此C4.5就此產生」[22]

-----

4.2. C4.5 [13]

「C4.5演算法改進ID3演算法,以獲利比率(GainRatio)最大者作為決定屬性。這方式解決了ID3的缺點,但是會有過度補償的問題,例如可能只是因為某欄位數值變化比其他欄位低很多而已。改善方式是,選擇具有最大獲利比率的欄位,然而該欄位的資訊獲利要跟所考察的所有欄位的平均資訊獲利差不多 另外,C4.5也可以對連續屬性加以處理 C5.0 C5.0為C4.5的改進版,主要針對海量資料的處理,以及增加執行準確度、減少記憶體耗用 C5.0的其他優點還有提高精度、模型易於理解、不需要很長的訓練次數、面對遺漏值時非常穩定等。」[22]

-----

4.3. CART [14]

「C4.5 [13] and CART [14] are two later classification tree algorithms that follow this approach.」[8]

The AID and CART regression tree methods follow Algorithm 1, with the node impurity
being the sum of squared deviations about the mean and the node predicting the sample mean of Y. [8]

根據 [8],CART 同時是分類樹與迴歸樹。見上文。

有關 CART,更多的資料可以參考 [19]-[21]。

「CART(Classfication and Regression Tree) 在節點上採取二分法,故為二元樹,以吉尼係數作為選擇依據 以吉尼係數最小的屬性作為分割屬性」[22]

-----

4.4. CHAID [15]

-----

4.5. MARS

「MARS 是用來解決多元資料問題的新方法,主要是運用數段解釋方程式而加總組合出一個較具彈性的預測模式的觀念,它是一種具彈性的迴歸處理程序,可以自動建立準則模型,並利用這個準則模型來推測其連續和間斷的反應變數 [16]。從名稱來看,就是指多元逐步的迴歸程序,它最適合運用在高維度的問題,也被視為廣義的線性逐步迴歸,或者是經由修正 CART 的方法而改善迴歸配適的執行過程 [17]。目前已被運用在許多不同領域的研究上,其中又以分類判別問題的應用最多,對於預測問題的運用也有愈來愈普遍的趨勢。 」

「MARS 目前較被廣泛運用的領域大部分是資料採礦的區隔問題方面,由於它的要求是以最適合的解釋變數建立起各區間的解釋模型,我們透過這個新的解釋變數建立的程序,可有效的從資料中挖掘出過去一些處理方法難以發現的重要特性及關係 [18]。而其函數中的解釋方程式之個數則是根據其資料本身參數間的交互關係所決定,並經由評估其損適性之判斷標準,同時獲得最佳及最適合的變數組合,如此可用來解決高維度資料的各種問題 [16]。」

-----

結論:

由本次的文獻回顧,我們可以猜測,在 [1] 裡面用的演算法,決策樹二元分類、決策樹多元分類「可能採用」ID3 / C4.5;決策樹迴歸分析「可能採用」CART。

後續將針對此三種演算法深入討論!

C4.5 與 CART 可參考資料科學最熱的十一種演算法 [23], [24]。

-----

References

[1] Python Spark ML(一):參加辦法
http://hemingwang.blogspot.tw/2017/09/python-spark-ml.html

[2] Python Spark ML(三):Decision Tree Survey
https://hemingwang.blogspot.tw/2017/09/python-spark-mldecision-tree-survey.html

[3] 決策樹 - 維基百科,自由的百科全書
https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91 

[4] 決策樹學習 - 維基百科,自由的百科全書
https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AD%A6%E4%B9%A0 

[5] 活學活用決策樹(三):運用SAS EM決策樹進行CHAID及CART分析
http://www.sasresource.com/faq389.html

[6] 從決策樹到隨機森林:樹型算法的原理與實現_機器之心 _ 微文庫-微信公眾號文章
https://weiwenku.net/d/101752231 

[7] 資料採礦中的統計預測與分類方法
http://www.stat.ncku.edu.tw/faculty_private/sljeng/Datamining/predict.htm

[8] Loh, Wei‐Yin. "Classification and regression trees." Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1.1 (2011): 14-23.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.364.9647&rep=rep1&type=pdf 

[9] Morgan, James N., and John A. Sonquist. "Problems in the analysis of survey data, and a proposal." Journal of the American statistical association 58.302 (1963): 415-434.

[10] Fielding, A., and C. A. O'Muircheartaigh. "Binary segmentation in survey analysis with particular reference to AID." The Statistician (1977): 17-28.

[11] Messenger, Robert, and Lewis Mandell. "A modal search technique for predictive nominal scale multivariate analysis." Journal of the American statistical association 67.340 (1972): 768-772.

[12] Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.

[13] Quinlan, J. Ross. "C4. 5: Programs for machine learning (morgan kaufmann series in machine learning)." Morgan Kaufmann (1993).

[14] Breiman, Leo, et al. Classification and regression trees. CRC press, 1984.

[15] Kass, Gordon V. "An exploratory technique for investigating large quantities of categorical data." Applied statistics (1980): 119-127.

[16] Friedman, Jerome H. "Multivariate adaptive regression splines." The annals of statistics (1991): 1-67.

[17] Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. "The Elements of Statistical Learning: Data Mining, Inference, and Prediction." Biometrics (2002).

[18] Steinberg, D., P. L. Colla, and Kerry Martin. "MARS user guide." San Diego, CA: Salford Systems (1999).

[19] https://rafalab.github.io/pages/649/section-11.pdf

[20] http://www.stat.cmu.edu/~cshalizi/350/lectures/22/lecture-22.pdf

[21] http://avesbiodiv.mncn.csic.es/estadistica/curso2011/regm40.pdf  

[22] 程式_ 決策樹演算法筆記 @ Leon's Sketches   痞客邦 PIXNET
http://iamkyc0312.pixnet.net/blog/post/339857156-%E7%A8%8B%E5%BC%8F%7C-%E6%B1%BA%E7%AD%96%E6%A8%B9%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98 

[23] Wu, Xindong, et al. "Top 10 algorithms in data mining." Knowledge and information systems 14.1 (2008): 1-37.

[24] Chen, Tianqi, and Carlos Guestrin. "XGBoost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016.

No comments: