[作業] 資料結構與演算法作業五

看板b99902HW作者syuusyou (syuusyou)時間13年前 (2011/05/06 16:01)推噓5(5推 0噓 1→)

留言6則, 6人參與討論串1/1

稍微賺一下文章數跟批幣XD == 5.1 樹(Trees) (1) 請使用 C 語言或任何的虛擬碼(pseudo-code)來寫出一個演算法(algorithm)。而給予線索二叉樹(threaded binary tree)上的一節點(node)，該演算法可以有效率的找出該節點的雙親(parent)。 (2) 請使用 C 語言或任何的虛擬碼來寫出一個時間複雜度演算法(time complexity) 為 O(N) 的演算法，來檢查一個擁有 N 個節點的樹是否為二元搜尋樹(binary search tree)。請簡要地解釋為什麼你寫的演算法時間複雜度為 O(N)。 (3) 請使用 C 語言或任何的虛擬碼來寫出在課本第 230 頁，練習題 5 當中所描述的演算法(5.6 小節)。請簡要地解釋你的演算法時間複雜度為何。 (4) 請使用 C 語言或任何的虛擬碼來寫出在課本第 243 頁，練習題 6 當中所描述的演算法(5.8 小節)。 (5) 證明你在 5.1(4) 當中所演演算法的時間複雜度。 (6) 課本第 247 頁，練習題 2 (5.9 小節)。 (7) 課本第 247 頁，練習題 4 (5.9 小節)。 5.2 決策樹(Decision Tree) 在這個問題中，我們會探究樹在人工智慧(Articial Intelligence)與機器學習(Machine Learning)這兩個領域上的一種應用。決策樹在機器學習上是最早被利用的工具之一。在決策樹中，非葉節點(non-leaf node)代表著我們所考慮的選擇(choice)或因素(factor) ，而葉節點(leaf node)則代表了我們在上述因素下最後做出的決定。為了簡單起見，我們只考慮擁有二元性因素(binary factor)的決策樹，也就是，二元決策樹(binary decision tree)。例如：下面的樹是一個決定要不要打高爾夫球的二元決策樹。如果天氣是陰天(cloudy) 的話，則我們會決定去打高爾夫球；如果不是陰天的話，我們會檢查今天有沒有刮風 (windy)，如果刮風的話，我們只會在天氣晴朗(clear)且不潮溼(humid)的情況下去打高爾夫球。另一方面，如果沒有刮風的話，我們只會在沒有下雨(rainy)但潮濕的情況下不去打高爾夫球。圖請見作業的檔案。這樣的決策樹也被稱為"分類樹(classification tree)"。它把（晴天，雨天，潮濕）這三種不同的情況，分類到決策類別 play? = {是(yes), 否(no)} 當中。決策樹並不是任意生成的。事實上，它是藉由給予一連串例子，讓程式自動學習所得到的結果。換句話說，你可以用這些例子來教導你的程式。表請見作業的檔案。決策樹可以由上往下以遞迴的方式來生成。首先，我們需要找到根的分支。在上表的例子當中，總共有 9 個是及 5 個否（9Y5N）。如果我們考慮的是天氣是否晴朗這個因素，我們可以將這 14 個例子分成 2 個分支：在天氣晴朗的分支上有 2Y3N，而另外一個分支則有 7Y2N；如果我們考慮的因素改為是否為陰天，我們也可以將這 14 個例子分成兩個分支：在陰天的分支上有 4Y0N，而另一個分支則有 5Y5N。我們可以繼續確認可能的分支條件。要建立好的分支選擇，你可以檢查在分支之後的亂度(confusion)。對於一個aYbN的混合物(mixture)，其亂度定義為： confusion(a, b) = 1 - ( a / ( a + b )) ^ 2 - ( b / ( a + b )) ^ 2 而 (c+e)Y(d+f)N 在分支成為 cYdN 及 eYfN 之後，其總亂度為： total(c, d, e, f) = (c + d) * confusion(c, d) / (c + d + e + f) + (e + f) * confusion(e, f) / (c + d + e + f) 例如：如果以天氣是否晴朗來當作分支依據的話，其總亂度為： 5 / 14 * (1 - (2 / 5) ^ 2 - (3 - 5) ^ 2) + 9 / 14 * (1 - (7 / 9) ^ 2 - (2 / 9) ^ 2) 如果我們可以找到一個分支條件使得分支完後的總亂度最小，則可以限制住我們產生出任意的分支。現在，當我們對根找到一個好的分支，則我們可以把所有的例子分成兩個子集合：一個是根左孩子(left-child)，另一個則是根的右孩子(right-child)。而同樣的方法可以分別用在這兩個孩子上，使其又個別產生出兩個孩子，依循此法做遞迴，則可以建出整棵決策樹來。遞迴？那終止條件該是什麼？如果該節點已經沒有亂度存在的話，也就是所有例子組成 aY0N 或 0YbN 的情形時，我們就不需要在繼續分支下去了，也就是說該節點在決策樹當中是葉子(leaf)。在這種狀況之下，我們可以宣告該葉子有一個最終的決定（是或否）。下列是一個簡單的決策樹生成演算法： DecisionTree(examples) if 在examples當中沒有亂度 then 建立一個擁有最終決定的葉子節點並將其回傳 else 找到一個可以將總亂度化為最小的分支條件，並將其存在根當中依此分支條件將example分成兩個子集合，分別分配給左小孩和右小孩令左子樹 = DecisionTree(分配給左小孩的examples) 令右子樹 = DecisionTree(分配給右小孩的examples) 回傳整棵樹 end if 在這個問題當中，你需要寫一個會根據所給例子來生成相對應之二元決策樹的程式。有趣的是，對於二元決策樹，你可以將其表示為 C 語言中的 if(...){...}else{...}。也就是說，在你的程式建出二元決策樹後，它必須自己產生另外一個程式來對以後的例子做出決定。 (1) 實作出上述的決策樹演算法。你的程式必須能讀入例子，並輸出一段程式碼來表示你的程式根據所給例子所建成的二元決策樹（格式請參閱課程網）。 (2) 用圖示來說明你在程式內部用來表示決策樹的資料結構。請盡可能的明確表示。 (3) 以下表的例子來建構函式 f 的二元決策樹，並畫出你所得的樹。（表請見作業檔案） (4) 請建出你自己的資料集(data set)，該資料集至少要有兩個因素，且至少擁有六個例子。你的程式必須對該資料集建出一個至少兩層的決策樹。列出所有的例子、畫出生成的決策樹，並簡單解釋所生成的樹。 (5) 如果你的分支方法不是採用最小亂度的分支法，而是採用隨機分支法，也就是隨機挑選出一個因素當作分支的條件來做分支。由於隨機選取的關係，你可能會重新選取到在上層已經選過的因素。使用問題 5.2(3) 所給的例子，來比較採用最小亂度分支法所形成的決策樹及採用隨機分支法所形成的決策樹的平均高度（至少一千次的平均）。簡單說明你的發現。如果你有興趣擴展你的程式使其在機器學習上更有用處，則你可以在完成作業後，隨時聯絡老師。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.214.43 ※ 編輯: syuusyou 來自: 140.112.214.43 (05/06 16:02)

推

wctaiwan

05/06 17:14, , 1^F

05/06 17:14, 1^F

推

didiwu

05/06 17:32, , 2^F

05/06 17:32, 2^F

→

syuusyou

05/06 20:08, , 3^F

05/06 20:08, 3^F