Decision Tree

อ่านเจอใน OnLamp เรื่อง Building Decision Trees in Python
ของ Christopher Roach
ของเดิมเขาเขียนด้วย python ก็เลยลอง implement ด้วย ruby และ clisp ดู

เริ่มด้วยการทำความเข้าใจ Decision Tree ก่อน
ตัว Decision Tree เป็น topic หนึ่งใน maching learning ของ AI
นอกจากนี้ยังเป็น technique ที่ใช้หา ความสัมพันธ์ของข้อมูล ใน Data mining. อีกด้วย

พูดหลักการเฉยๆ จะมองไม่เห็นภาพ ต้องดูตัวอย่างจริง
ยกตัวอย่างว่า เรามี data อยู่ชุดหนึ่ง (sample data)
แล้วเราต้องการหา decision tree จาก data นี้

decision tree ที่ได้ อาจจะมีหน้าตาได้หลายแบบ ขึ้นอยู่กับ
ลำดับของ attribute ที่เราเลือกออกมาทำ category
เช่น ถ้าเลือก house type, district, previous customer
หน้าตาของ tree ก็จะออกมาแบบนี้



แต่ถ้าเลือกลำดับ income ก่อน หน้าตา ก็อาจจะได้ออกมาแบบนี้



จะเห็นได้ว่าเราสามารถจัดกลุ่ม tree ได้หลายแบบมาก
คำถาม ก็คือ tree แบบไหนที่ให้ information ได้ดีที่สุด
คำตอบก็คือ tree ที่สั้นที่สุด (Occam's Razor)
ซึ่งก็คือ tree ที่หน้าตาแบบนี้



algorithm ที่ใช้ในการเลือกลำดับของ attribute ก็คือ
ID3 ที่ใช้การคำนวณ Entropy เข้ามาช่วย
โดยเลือก attribute ที่ทำให้ Entropy ของ tree ลดลงมากที่สุด (entropy สูง, ซับซ้อนสูง)
Tutorial ที่อธิบายวิธีการคำนวณ Entropy ได้ดี อยู่ที่นี่
DMS Tutorial - Decision trees

ผมลองใช้ข้อมูลที่อยู่ใน tutorial ข้างบน [link]
มาลอง implement และ run ด้วย ruby และ lisp ดู

ผลลัพท์ที่ได้ (ใช้เกณฑ์การตัดสินของตัวเอง, bias ล้วนๆ)

• การลอก(แปลง) python มาเป็น ruby ทำได้ง่ายมาก
  
• ตัว code ที่ได้, ทั้ง python และ ruby อ่านง่ายทั้งคู่ ส่วน lisp อ่านยากกว่า
  (ในส่วนของ lisp ถ้าจะให้อ่านง่าย ก็ต้องทำการลดรูป syntax
  โดยใช้ macro เข้ามาช่วย)
  

ลองดู code ของ ruby กับ lisp ดู (code ของ python ให้ดูที่ tutorial ของ OnLamp)
function entropy

def entropy(datas, attr)
  include Math
  
  freqs = Hash.new {|h, k| h[k] = 0.0}

  datas.each do |data|
    freqs[data[column_by_name(attr)]] += 1    
  end
  summ = 0.0
  
  freqs.values.each do |val|
    summ += (-val/datas.length) * 
                    ((log (val/datas.length)) / (log 2))
  end
  
  summ
end

(defun group-by-attr (data attr)
  (let ((hash (make-hash-table)))
    (mapc #'(lambda (record)
          (let* ((elm (funcall attr record))
             (value (gethash elm hash 0)))
        (setf (gethash elm hash) (+ value 1))))
      data)
    hash))
    
(defun entropy (data attr)
  (let ((freqs (group-by-attr data attr))
    (total 0))
    (maphash #'(lambda (key value)
         (let ((frac (/ value (length data))))
           (setq total (+ total
                  (* (- frac)
                     (log frac 2))))))
         freqs)
    total))

function gain

def gain(datas, attr, target_attr)
  freqs = Hash.new {|h, k| h[k] = 0.0}
  subset_entropy = 0.0
  
  datas.each do |data|
    freqs[data[column_by_name(attr)]] += 1
  end
  
  freqs.keys.each do |key|
    prob = freqs[key] / datas.length
    filter_datas = datas.find_all {|data|
      data[column_by_name(attr)] == key
    }
    
    subset_entropy += prob * 
                                 entropy(filter_datas, target_attr)  
  end
  
  entropy(datas, target_attr) - subset_entropy
end

(defun gain (data attr target-attr)
  (let* ((freqs (group-by-attr data attr))
    (total 0))
    (maphash #'(lambda (key value)
         (let ((prob (/ value (length data)))
               (subset (remove-if-not 
                #'(lambda (rec) 
                    (eql key (funcall attr rec))) data)))
           (setq total (+ total 
                               (* prob 
                                   (entropy subset target-attr))))))
         freqs)
    (- (entropy data target-attr) total)))

ใน lisp ผมลองลดรูปด้วยการใช้ macro มาช่วย
(แต่ยัง design macro ไม่เก่ง ผลเลยไม่ดีเท่าไร)
function entropy ถูกลดรูปมาเป็น

(defmacro summ-loop (lst value &rest body)
  `(let ((total 0))
     (mapc #'(lambda (,value)
           (let ((result ,@body))
         (setf total (+ total result))))
       ,lst)
     total))

(defun entropy2 (data attr)
  (let* ((freqs (group-by-attr data attr))
           (values (hash-values freqs)))
    (summ-loop values val
      (let ((frac (/ val (length data))))
        (* (- frac) (log frac 2))))))

Note: การพยายามลดรูปด้วยการ define macro แบบนี้ ถ้าตั้งชื่อไม่สื่อ หรือไม่มีเอกสารพอ
ก็น่าจะนำไปสู่ code ที่อ่านยากขึ้นแทน