ขั้นตอนการหากฏความสัมพันธ์ (Association Rules)

บทความที่ผ่านมาได้พูดถึงวิธีการสร้างโมเดล classification แบบต่าง เช่น Neural Network, Support Vector Machine, Decision Tree และ Naive Bayes ในบทความนี้จะพูดถึงการหากฏความสัมพันธ์ หรือ association rules

ในการหากฏความสัมพันธ์นี้มีอยู่หลายวิธี แต่สำหรับบทความนี้จะแสดงการหากฏความสัมพันธ์ด้วยวิธี Apriori ซึ่งจะมีอยู่ 2 ขั้นตอนใหญ่ๆ คือ

  1. การหา frequent itemset เป็นการหารูปแบบของข้อมูลที่เกิดขึ้นร่วมกันบ่อยๆ ในฐานข้อมูล  หรือ มากกว่าค่า minimum support ที่ผู้ใช้กำหนด ในขั้นตอนนี้จะแบ่งได้อีกเป็น 2 ขั้นตอนย่อย คือ
    • การสร้างรูปแบบของ itemset  (join) จะใช้รูปแบบของ itemset ที่มีค่ามากกว่า minimum support มาทำการสร้างรูปแบบของ itemset ที่มีขนาดยาวมากขึ้นทีละหนึ่งขั้นไปเรื่อยๆ
    • การนับค่า support (count) หลังจากที่สร้างรูปแบบของ itemset ได้แล้ว ขั้นถัดมาจะทำการคำนวณค่า support ที่เกิดขึ้น โดยที่ support คือจำนวนเปอร์เซ็นต์ที่พบ itemset ในฐานข้อมูล
  2. การสร้าง association rule หลังจากที่หา frequent itemset ได้แล้วจะนำรูปแบบที่หาได้มาสร้างเป็นกฏความสัมพันธ์โดย เช่น Apple => Cereal หมายความว่าเมื่อลูกค้าซื้อ Apple แล้วลูกค่าจะซื้อ Cereal ร่วมไปด้วย

ในบทความนี้จะใช้ตัวอย่างข้อมูลที่แสดงในรูปที่ 1 ซึ่งเรียกว่า transaction database ในฐานข้อมูลนี้จะประกอบด้วย 4 transaction และมีสินค้าที่ลูกค้าซื้อทั้งหมด 5 ประเภทคือ Apple, Beer, Cereal, Diapers และ Eggs

transaction_database

รูปที่ 1 แสดง transaction database ที่จะใช้หากฏความสัมพันธ์

ในบทความนี้จะแสดงตัวอย่างการหากฏความสัมพันธ์โดยกำหนดค่า minimum support ไว้ที่ 50% นั่นคือ สินค้าที่มีการซื้อมากกว่าหรือเท่ากับ 50% จะถือว่าเป็น frequent itemset ขั้นตอนการทำงานมีดังต่อไปนี้

1. คำนวณหาค่า support ของแต่ละ item ดังแสดงในรูปที่ 2 แต่ละแถวคือข้อมูลสินค้าแต่ละชนิดและแต่ละคอลัมน์มีความหมายดังนี้

  • คอลัมน์ที่ 1 คือชื่อสินค้าหรือ item หรือ itemset
  • คอลัมน์ที่ 2-5 คือหมายเลขของ transaction ถ้ามีการซื้อสินค้าใน transaction ใดที่คอลัมน์ของ transaction นั้นจะมีหมายเลข 1 แต่ถ้าไม่มีจะเป็นเลข 0
  • คอลัมน์ที่ 6 คือ ค่า support

association_rule1

รูปที่ 2 แสดงการคำนวณค่า support ของสินค้าแต่ละชนิด

จากค่า support ที่คำนวณได้ในรูปที่ 2 จะเห็นว่า Diapers มีค่า support ตำ่กว่าค่า minimum support (25% < 50%) ดังนั้น Diapers จะถูกตัดออกและไม่นำไปพิจารณาสร้างเป็น itemset ที่มีความยาว 2 ต่อไป ดังรูปที่ 3 และเรียก Apple, Beer, Cereal และ Eggs ว่า frequent itemset

association_rule2

รูปที่ 3 Diapers ถูกตัดทิ้งเนื่องจากมีค่า support ต่ำกว่าค่า minimum support ที่กำหนดไว้

2. นำ frequent itemset ที่ได้จากรูปที่ 3 มาสร้างเป็น itemset ที่มีความยาว 2 โดยใช้การ join ได้เป็น {Apple, Beer}, {Apple, Cereal}, {Apple, Eggs}, {Beer, Cereal}, {Cereal, Eggs} และเนื่องจากเป็นเซต ลำดับของข้อมูลไม่มีผล นั่นคือ {Apple, Beer} = {Beer, Apple}

ส่วนการคำนวณค่า support ก็นำข้อมูล transaction ในรูปที่ 3 มาทำ intersect กัน (หรือใช้ bit opreration AND ก็ได้) เช่น การหา support ของ {Apple, Beer} จะเกิดจาก

  • transaction(Apple)               = {1,0,1,0}
  • transaction(Beer)                 = {0,1,1,1}
  • transaction(Apple, Beer)   = {0,0,1,0}

ค่า support ของitemsets ที่มีความยาว 2 ทั้งหมดจะแสดงในรูปที่ 4 และ itemset ที่มีค่า support น้อยกว่า minimum support จะถูกตัดทิ้งไปทำให้เหลือ frequent itemset ที่มีความยาว 2 เพียงแค่ {Apple, Cereal}, {Beer, Cereal}, {Beer, Eggs}, {Cereal, Eggs} ดังแสดงในรูปที่ 5

association_rule3

รูปที่ 4 แสดงค่า support ของ itemset ที่มีความยาว 2

association_rule4

รูปที่ 5 แสดง frequent itemset ที่มีความยาว 2

3. ถัดมาทำการสร้าง itemset ที่มีความยาวเท่ากับ 3 โดยมีเงื่อนไขว่าข้อมูล item แรกจะต้องมีค่าเหมือนกันจึงสามารถทำการ join กันได้ เช่น  {Beer, Cereal, Eggs} เกิดจากการ join {Beer, Cereal} และ {Beer, Eggs} แต่ไม่สามารถ join {Apple, Cereal} และ {Beer, Cereal} ได้ ดังนั้นในขั้นตอนนี้จะมีเพียงแค่ itemset เดียวคือ  {Beer, Cereal, Eggs} และเป็น frequent itemset ดังแสดงในรูปที่ 6

association_rule5

รูปที่ 6 แสดง itemset ที่มีความยาวเท่ากับ 3

จากรูปที่ 6 เราไม่สามารถสร้าง itemset ที่มีความยาวมากขึ้นกว่านี้ได้อีก ขั้นตอนการหา frequent itemset จึงหยุด และได้ frequent itemsets ทั้งหมดดังแสดงในรูปที่ 7

association_rule6

รูปที่ 7 แสดง frequent itemset ทั้งหมดที่หาได้

4. ขั้นตอนถัดมาคือการสร้างกฏความสัมพันธ์จาก frequent itemset ที่หาได้ โดยจะพิจารณา frequent itemset ที่มีความยาวมากกว่า 2 item ขึ้นไปมาสร้างเป็นกฏความสัมพันธ์ เช่น
{Apple, Cereal} จะสร้างกฏความสัมพันธ์ได้เป็น Apple => Cereal เป็นต้น โดยกฏความสัมพันธ์ทั่วไปจะแสดงเป็น

Screen Shot 2557-03-20 at 4.03.33 AM

โดยที่ LHS (Left Hand Side) แสดงรูปแบบของ itemset ด้านซ้ายของกฏความสัมพันธ์ และ RHS (Right Hand Side) แสดงรูปแบบของ itemset ด้านขวาของกฏความสัมพันธ์

ในการพิจารณาว่ากฏความสัมพันธ์ที่สร้างได้ดีหรือไม่จำเป็นจะต้องมีตัววัดประสิทธิภาพของกฏ ในบทความนี้จะขอแนะนำ 2 ตัววัด คือ confidence และ lift

  • ค่า confidence แสดงความเชื่อมั่นของกฏความสัมพันธ์ที่เมื่อรูปแบบ LHS เกิดขึ้นแล้วรูปแบบ RHS จะเกิดขึ้นด้วยเป็นจำนวนกี่เปอร์เซ็นต์ การคำนวณค่า confidence หาได้จาก

association_rule8 โดยที่ support (LHS, RHS) คือ ค่า support ที่รูปแบบ LHS และ RHS เกิดขึ้นพร้อมๆ กัน ตัวอย่างการหา confidence ของกฏ Apple => Cereal แสดงได้ดังนี้

Screen Shot 2557-03-20 at 4.15.55 AM

  • ค่า lift คือค่าที่บ่งบอกว่าการเกิดรูปแบบ LHS และ RHS มีความสัมพันธ์กันแค่ไหน โดยถ้าค่า lift เป็น 1 แสดงว่ารูปแบบ LHS และ RHS ไม่ขึ้นต่อกัน (independent) ค่า lift คำนวณได้จาก

association_rule10

ตัวอย่างของการหาค่า lift ของกฏ Apple => Cereal แสดงได้ดังนี้

Screen Shot 2557-03-20 at 4.16.02 AM

ค่า confidence และ lift ของกฏความสัมพันธ์ทั้งหมดที่สร้างได้แสดงในรูปที่ 8 โดยทำการเรียงตามค่า confidence และ lift จากมากไปหาน้อย
Screen Shot 2557-03-20 at 4.18.21 AM

รูปที่ 8 แสดงกฏความสัมพันธ์ทั้งหมดที่สร้างได้พร้อมทั้งค่า confidence และ lift

ทั้งหมดนี้คือขั้นตอนการหากฏความสัมพันธ์แบบง่ายๆ สำหรับการหากฏความสัมพันธ์ใน Weka สามารถดูได้จากที่นี่ครับ

Posted in data mining, data science and tagged , , .

Leave a Reply

Your email address will not be published. Required fields are marked *