การทำเหมืองกฎความสัมพันธ์ (Association Rule Mining) (Apriori)
- ผู้เสนอ
- Rakesh Agrawal & Ramakrishnan Srikant
- ปี
- 1994
- ประเภท
- Unsupervised pattern discovery algorithm
- กลุ่มวิธี
- Pattern mining
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การทำเหมืองกฎความสัมพันธ์ (Association Rule Mining) เป็นเทคนิคการทำเหมืองข้อมูลแบบไม่มีผู้สอน (unsupervised data-mining technique) ที่ค้นหารูปแบบการปรากฏร่วมกันของรายการต่างๆ ในชุดข้อมูลธุรกรรม (transactional datasets) โดยพื้นฐานแล้ว เทคนิคนี้ถูกนำเสนออย่างเป็นทางการโดย Agrawal, Imieliński, และ Swami ในปี 1993 และได้รับการปรับปรุงด้วยอัลกอริทึม Apriori ที่เป็นหลักโดย Agrawal และ Srikant ในปี 1994 โดยมีเป้าหมายเพื่อระบุ กฎในรูปแบบ X ⇒ Y ซึ่งหมายความว่าธุรกรรมที่มีเซตรายการ X มักจะมีเซตรายการ Y ด้วย โดยกฎเหล่านี้จะถูกวัดค่าด้วยความถี่ (support) ความเชื่อมั่น (confidence) และการยกขึ้น (lift)
แนวคิดเบื้องหลังวิธีการ
ลองนึกถึงบันทึกใบเสร็จซูเปอร์มาร์เก็ต: หากลูกค้าหลายพันคนที่ซื้อขนมปังและเนยก็มักจะซื้อนมด้วย รูปแบบดังกล่าวสมควรได้รับความสนใจ การทำเหมืองกฎความสัมพันธ์ทำงานเหมือนบรรณารักษ์ที่พิถีพิถัน ค้นหาใบเสร็จทุกใบเพื่อนับจำนวนครั้งที่รายการต่างๆ ปรากฏร่วมกัน และแสดงรายการที่เกินความถี่ขั้นต่ำที่กำหนด เมื่อพบกลุ่มที่พบบ่อยแล้ว อัลกอริทึมจะถามว่า: เมื่อพิจารณาว่าคุณมีรายการเหล่านี้อยู่แล้ว ความน่าเชื่อถือในการทำนายรายการถัดไปคือเท่าใด ตรรกะสองรอบนี้คือความถี่แล้วตามด้วยความเชื่อมั่น ซึ่งเป็นหัวใจสำคัญของ Apriori
ประวัติศาสตร์
บทความพื้นฐานโดย Agrawal, Imieliński, และ Swami (1993) ได้กำหนดปัญหาเรื่องกฎความสัมพันธ์ในบริบทของข้อมูลธุรกรรมซูเปอร์มาร์เก็ต บทความ VLDB ปี 1994 ของ Agrawal และ Srikant ได้นำเสนออัลกอริทึม Apriori และกลยุทธ์การตัดแต่งที่มีประสิทธิภาพ ทำให้การทำเหมืองข้อมูลขนาดใหญ่เป็นไปได้จริง งานวิจัยต่อมาได้พัฒนา FP-Growth (Han et al., 2000) ซึ่งหลีกเลี่ยงการสร้างผู้สมัครโดยสิ้นเชิง และ ECLAT ซึ่งทำการทำเหมืองในรูปแบบข้อมูลแนวตั้ง (vertical data format) ซึ่งเป็นการสร้างตระกูลอัลกอริทึมที่หลากหลายซึ่งปัจจุบันเป็นหัวใจสำคัญของหลักสูตรการทำเหมืองข้อมูล
ควรใช้เมื่อใด
การทำเหมืองกฎความสัมพันธ์เหมาะสำหรับชุดข้อมูลธุรกรรมขนาดใหญ่ที่เป้าหมายคือการค้นหารูปแบบการปรากฏร่วมกันโดยไม่มีตัวแปรเป้าหมายที่กำหนดไว้ล่วงหน้า โดยสมมติว่ารายการต่างๆ เป็นแบบไบนารี (มี/ไม่มี) ต่อธุรกรรม เหมาะสำหรับการวิเคราะห์ตะกร้าสินค้า (market basket analysis) ระบบแนะนำ (recommendation systems) การวิเคราะห์เส้นทางการคลิกบนเว็บ (web clickstream analysis) และการค้นหาการวินิจฉัยร่วมทางการแพทย์ (medical co-diagnosis discovery) ไม่เหมาะสำหรับข้อมูลต่อเนื่องหรือข้อมูลเชิงอันดับ (ordinal data) เว้นแต่จะถูกแบ่งกลุ่มก่อน (pre-discretized) สำหรับชุดข้อมูลที่มีมิติสูงมาก (พื้นที่ผู้สมัครแบบทวีคูณ) หรือเมื่อต้องการการอนุมานเชิงสาเหตุ (causal inference) มากกว่าการอนุมานเชิงความสัมพันธ์ (associative inference) ทางเลือกอื่น ได้แก่ FP-Growth สำหรับการแจงนับเซตรายการที่พบบ่อยที่เร็วกว่า และการทำเหมืองลำดับ (sequence mining) เมื่อลำดับเวลามีความสำคัญ
ข้อจำกัดและข้อควรพิจารณา
- พื้นที่ผู้สมัครแบบทวีคูณ: จำนวนกฎเพิ่มขึ้นแบบผสมผสานกับจำนวนรายการที่แตกต่างกัน
- กรอบงาน support–confidence อาจให้กฎที่ทำให้เข้าใจผิดได้เมื่ออัตราพื้นฐานของรายการแตกต่างกันอย่างมาก (จำเป็นต้องมีการปรับ lift)
- แบบจำลองธุรกรรมแบบไบนารีต้องการการแบ่งกลุ่มตัวแปรต่อเนื่อง ซึ่งนำไปสู่การสูญเสียข้อมูล
- การตั้งค่าเกณฑ์ support ขั้นต่ำที่สูงเกินไปจะทำให้พลาดกฎที่มีค่าน้อยแต่มีค่า; การตั้งค่าเกณฑ์ต่ำเกินไปจะสร้างกฎเล็กน้อยนับพัน
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่มีผู้สอนโดยเนื้อแท้: ไม่จำเป็นต้องมีข้อมูลที่มีป้ายกำกับหรือตัวแปรเป้าหมายที่กำหนดไว้ล่วงหน้า
- ผลลัพธ์ที่ตีความได้: กฎเป็นข้อความถ้า-แล้วที่มนุษย์อ่านได้ พร้อมด้วยค่า support และ confidence ที่วัดค่าได้
- ปรับขนาดได้ผ่านการตัดแต่งของ Apriori; รูปแบบ FP-Growth ช่วยขจัดกระบวนการสแกนฐานข้อมูลซ้ำซ้อนโดยสิ้นเชิง
- ไม่ขึ้นกับโดเมน: นำไปใช้ได้ทั่วทั้งภาคค้าปลีก สุขภาพ การวิเคราะห์เว็บ และชีวสารสนเทศ
การประยุกต์ใช้
- ภาคค้าปลีก: การจัดวางผลิตภัณฑ์และการแนะนำการขายพ่วง (cross-selling) จากบันทึกธุรกรรม ณ จุดขาย (point-of-sale transaction logs)
- ภาคสุขภาพ: การวิเคราะห์การปรากฏร่วมกันของการวินิจฉัย ขั้นตอน หรือยา ในเวชระเบียนอิเล็กทรอนิกส์ (electronic health records)
- การวิเคราะห์เว็บ: การค้นหารูปแบบเส้นทางการคลิกเพื่อแนะนำหน้าเว็บและการปรับปรุงการนำทาง
- ชีวสารสนเทศ: การระบุชุดยีนที่แสดงออกร่วมกัน (co-expressed gene sets) และลวดลายการปฏิสัมพันธ์ของโปรตีน (protein interaction motifs)
- ความปลอดภัยทางไซเบอร์: การตรวจจับเหตุการณ์เครือข่ายที่สัมพันธ์กันซึ่งบ่งชี้ถึงรูปแบบการบุกรุก
วิธีการทำงาน
วิธีการทำงาน
อัลกอริทึมจะสแกนฐานข้อมูลธุรกรรม D เพื่อเพื่อนับจำนวนครั้งที่เซตรายการ X ปรากฏ เซตรายการจะถูกประกาศว่าพบบ่อย (frequent) และถูกจัดเก็บไว้ใน L_k ก็ต่อเมื่อความถี่ (support) ของมัน (คือสัดส่วนของธุรกรรมที่มีเซตรายการนั้น) เท่ากับหรือสูงกว่าเกณฑ์ความถี่ขั้นต่ำที่ผู้ใช้กำหนด σ_min กระบวนการเริ่มต้นด้วยรายการเดี่ยวๆ (k=1) และสร้างชุดผู้สมัคร (candidate sets) ที่ใหญ่ขึ้นตามลำดับ
สูตร
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}คุณสมบัติการต่อต้านความเป็นโมโนโทน (anti-monotonicity property) ของความถี่ระบุว่าเซตย่อยใดๆ ของเซตรายการที่พบบ่อยจะต้องเป็นเซตที่พบบ่อยด้วยเช่นกัน Apriori ใช้ประโยชน์จากคุณสมบัตินี้โดยการตัดเซตรายการ k รายการ (candidate k-itemset) ทุกชุดที่เซตย่อย (k-1) ของมันไม่ได้อยู่ในชุดที่ผ่านการตรวจสอบแล้ว L_{k-1} ทั้งหมด ซึ่งช่วยลดพื้นที่การค้นหาได้อย่างมาก และหลีกเลี่ยงการสแกนฐานข้อมูลที่มีค่าใช้จ่ายสูงสำหรับเซตรายการที่อาจไม่พบบ่อย
สูตร
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kจากเซตรายการที่พบบ่อยแต่ละชุด X ∪ Y อัลกอริทึมจะสร้างกฎ X ⇒ Y โดยที่ X และ Y เป็นเซตย่อยที่ไม่ทับซ้อนกัน กฎจะถูกเก็บไว้ก็ต่อเมื่อความเชื่อมั่น (confidence) ของมัน ซึ่งคือความน่าจะเป็นแบบมีเงื่อนไขของ Y เมื่อกำหนด X คำนวณได้จาก support(X ∪ Y) / support(X) เท่ากับหรือสูงกว่าเกณฑ์ความเชื่อมั่นขั้นต่ำ γ_min ขั้นตอนนี้จะแปลงการปรากฏร่วมกันของรายการดิบให้เป็นข้อความคาดการณ์แบบมีทิศทาง
สูตร
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}กฎที่ถูกเก็บไว้จะถูกจัดอันดับและกรองด้วยค่า lift ซึ่งวัดว่า Y มีแนวโน้มที่จะปรากฏร่วมกับ X มากกว่าโดยบังเอิญเพียงใด ค่า lift > 1 บ่งชี้ความสัมพันธ์เชิงบวกที่เกินกว่าความเป็นอิสระ ค่า lift = 1 บ่งชี้ความเป็นอิสระ และค่า lift < 1 บ่งชี้ความสัมพันธ์เชิงลบ มาตรวัดความน่าสนใจเพิ่มเติม เช่น conviction และ leverage สามารถปรับปรุงชุดกฎให้เหมาะสมกับการใช้งานจริงได้
สูตร
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}ข้อผิดพลาดที่พบบ่อย
- การตั้งค่า support ขั้นต่ำต่ำเกินไปจะทำให้ผู้ทำการวิเคราะห์ท่วมท้นไปด้วยกฎที่ผิดพลาด การเลือกเกณฑ์ต้องอาศัยความรู้เฉพาะทางหรือการตรวจสอบไขว้ (cross-validation)
- การสับสนระหว่างความสัมพันธ์ทางสถิติกับความเป็นสาเหตุ: ค่า lift ที่สูงไม่ได้หมายความว่า X ทำให้เกิด Y
- การละเลยการกระจายความถี่ของรายการ: รายการทั่วไปมีอิทธิพลต่อกฎและเบียดบังความสัมพันธ์ของรายการที่หายากที่มีความหมาย
- การพิจารณา confidence เพียงอย่างเดียวเป็นตัวชี้วัดคุณภาพ; กฎที่มี confidence สูงแต่ lift ต่ำอาจทำงานได้ไม่ดีไปกว่าการสุ่ม
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่าง support, confidence, และ lift?
Support วัดว่าเซตรายการปรากฏในชุดข้อมูลโดยรวมบ่อยเพียงใด Confidence วัดความน่าจะเป็นแบบมีเงื่อนไขของผลลัพธ์ (consequent) เมื่อกำหนดเงื่อนไขของเหตุ (antecedent) Lift ปรับค่า confidence ด้วยความถี่ตามขอบของผลลัพธ์ เพื่อเปิดเผยว่าการปรากฏร่วมกันนั้นเกินกว่าที่คาดหวังภายใต้ความเป็นอิสระหรือไม่ ทั้งสามเมตริกจำเป็นต้องใช้ร่วมกันเพื่อการประเมินกฎที่แข็งแกร่ง
อัลกอริทึม Apriori ลดต้นทุนการคำนวณได้อย่างไร?
Apriori ใช้ประโยชน์จากคุณสมบัติการต่อต้านความเป็นโมโนโทน: หากเซตรายการไม่พบบ่อย เซตย่อยทั้งหมดของมันก็จะต้องไม่พบบ่อยด้วยเช่นกัน โดยการทิ้งผู้สมัครทุกชุดที่เซตย่อยของมันไม่ได้รับการยืนยันว่าพบบ่อยทั้งหมด อัลกอริทึมจะตัดส่วนใหญ่ของพื้นที่การค้นหาออกก่อนที่จะทำการนับ ซึ่งช่วยลดจำนวนครั้งที่ต้องสแกนฐานข้อมูลลงอย่างมากเมื่อเทียบกับการแจงนับแบบ brute-force
เมื่อใดที่ควรใช้ FP-Growth แทน Apriori?
FP-Growth เป็นที่ต้องการเมื่อชุดข้อมูลมีขนาดใหญ่และเกณฑ์ support ขั้นต่ำต่ำ เนื่องจากมันจะบีบอัดฐานข้อมูลธุรกรรมให้อยู่ในโครงสร้าง FP-tree ที่กะทัดรัด และทำการทำเหมืองรูปแบบโดยตรงโดยไม่ต้องสร้างผู้สมัครที่ชัดเจน ซึ่งช่วยขจัดกระบวนการสแกนฐานข้อมูลเต็มรูปแบบซ้ำๆ ทำให้เร็วกว่า Apriori อย่างมากบนชุดข้อมูลที่หนาแน่นซึ่งมีเซตรายการที่พบบ่อยจำนวนมาก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วAgrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว