前文

課程 計算型智慧 報告，這是一門碩班課程，因此聽了許多學長的報告，雖然有難有易，牽扯的領域相當繁雜且艱深，例如影像分析、電機、醫學領域 … 等，很多都是有聽沒有懂，但是多少能明白一些些道理，即使後來挑選幾個進行實作，發現自己根本沒有理解，或者只是單純實作能力不足。

其中最常見到的報告內容是 B*-tree with floor plan，對於電子電路的配置擺放，要求最小化面積的操作。當然其中也有幾個跟我報告的預測性有關。對於影響分析就不多述了，其中也有幾個電費電流調控也挺有意思的，總之報告內容相當多元。

報告的時候，教授就在台下緊盯，而我剛好是在教授開會的時候報告，這學期僅我一個在教授不在的情況下報告。

• One Exam: 30%
  只有一次期中考，而且還是人腦仿電腦考試，但是題目沒有講清楚，考炸了不少，題目理解上把常數搞錯意思，但是這不影響廣義型算法，希望助教給點分！例如：在基因算法中交配的兩兩交配，難道就不能與自己交配嗎？而在粒子算法中，只給兩個參數，難道就不能只模仿全局最佳點和自己嗎？如果只有兩個參數，而且加總為一，您叫我如何模仿鄰居和自己，看來只能二選一。
• Homework: 40% (3 programs)
• Presentation: 30%
  教授不在的情況下仍可以報告，所以成績是由助教評定嗎？
• Questions: 3
  本課程一定要問三個問題，否則視如無效修課，但是問題我總是在課堂中發問，對於學長報告的內容有點作噁不明白。

論文挑選為「Building optimal regression tree by ant colony system – genetic algorithm Application to modeling of melting points」這是一篇化學期刊上的運用，不是在計算機領域的論文。

開始

從一個最簡單的應用開始

在二十個問題內，能猜出心中想的目標角色。這一類的遊戲相當多，在很多遊戲或者是心理測驗中都會用到，用來預測你大概會是哪一種類型的人、或者正在想什麼。
http://en.akinator.com/

決策樹

決策樹的分類

• Classification Tree：分類樹
  分類，輸出 “類型”
• Regression Tree：回歸樹
  關係程度，輸出 “數值”
• CART (Classification And Regression Tree) 即上述兩個的總稱

關於 CART

• 大量數據可以快速算出結果
• 易於理解 和 解釋
• 可以用統計數據驗證模型
• 最優 CART 是 NP 問題。
• 能力有限，只能對有限數據屬性操作
• 機器學習 Machine Learning 領域常用

論文實驗資料

• 4173 種化合物，分類屬性有 202 種描述方式。在 4173 種化合物中，3000 種用來訓練，1173 種用來驗證。
• 與另外一組經由 277 種藥物進行熔點預測的 CART 相比。(另外一篇論文做的結果)
• 目標預測更加準確。

CART–ACS–GA 理論

• 將 ACS – GA 算法，套用在 CART 的建造上。
• 先說說 ACS – GA 算法運作

ACS-GA

ACS–GA 算法 (蟻群遺傳混合算法)，基於 ACS 的缺點 – 收斂慢，加入 GA 算法來加快。

• 為什麼不單純使用 GA 算法就好？
• 對問題編碼的困難 (轉 DNA 的問題)，突變效果可能不好

螞蟻基因也有好壞問題

• 如何反應基因好壞
• 對費洛蒙決策的方式
• 對費洛蒙的敏感度 … 等

換句話說，將螞蟻的能力也各自數據化，對於產生較好解的螞蟻，繁殖、交配、突變，接著談論如何運用在 CART！

CART 建造

假解亂做前，如何隨機？CART 是一棵二分樹
How we do ?

• 基於深度優先的方式，直到某個葉節點的分類種數 < 30 或深度大於某個值，就退回。
• 每一層必須決定 “依據哪個屬性分類” Age ? Gender ? Last R ?
• 分類時，又要按照什麼 數值 進行分割。< 30 ? > 30 ? = 30 ?

假設 CART 有 m 個節點，n 個分類描述。在此篇中，化合物有 202 種描述，即 n = 202。

• 為了表示螞蟻的判斷能力，到達某個節點 i 時，採用下一個分類方式 k 的費洛蒙 M[i][k]
  i < m, k < n
• 這樣可以決定分類方式。對於某個節點 i，i 可以是目前累計完成的節點個數，或者是其他。

上面決定了分類方式，但沒決定分割點 ( cut point ) 的選擇方式。

• 假設用 10 種決策方式，來對應分類到節點內有的所有項目屬性，進行統計分類。
  • 決策方式 1：平均、眾數、權重、 ID3、C4.5 (熵理論和訊息增益) … 等分割策略
  • 決策方式 2 : 用 10 個常數對於屬性最大最小值 f(min, max) = x0 * min + x1 * max + x2 * min * max
  • 決策方式 3：最大最小值之間切 10 等分。
• 費洛蒙將會有 10 × n × m，即 M[10][n][m]。

關於適應函數

對於葉節點

Partial least squares method 不同於 “最小平方法”

• 多因變數 對 多自變數 的回歸建模方法
• 對於每一個葉節點的所有資料分別做偏最小二乘法，會得到分類的相聯性，也就是 相關係數 (correlation coefficient)
• 相關係數總和大小 與 適應力高低 成正比，用 驗證集 找到相關係數。

結論

• 對於下次迭代，偏向於好的切割屬性
• 對於切割屬性，可以得到好的分割點
• 排除單一分割策略的形式