การทำเหมืองกฎความสัมพันธ์แบบกึ่งมีผู้สอน (Semi-supervised Association Rules)
- ผู้เสนอ
- Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
- ปี
- 2003–2010s
- ประเภท
- Pattern mining with partial supervision
- กลุ่มวิธี
- Machine learning
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การทำเหมืองกฎความสัมพันธ์แบบกึ่งมีผู้สอนเป็นการต่อยอดจากการเรียนรู้กฎความสัมพันธ์แบบดั้งเดิม โดยการนำข้อมูลที่มีป้ายกำกับ (labeled data) จำนวนเล็กน้อยมาใช้ร่วมกับชุดข้อมูลที่ไม่มีป้ายกำกับ (unlabeled data) จำนวนมาก การทำเหมืองวิธีนี้ใช้ข้อมูลคลาสที่ทราบ หรือข้อจำกัดที่ผู้ใช้กำหนด เพื่อชี้นำการค้นหากฎที่ทั้งมีความถี่ทางสถิติและมีความหมายในเชิงความหมาย ซึ่งเป็นการเชื่อมโยงระหว่างการทำเหมืองรูปแบบที่ไม่มีผู้สอน (unsupervised pattern mining) กับการกำกับดูแลแบบเบา (light supervision)
แนวคิดเบื้องหลังวิธีการ
การทำเหมืองกฎความสัมพันธ์แบบมาตรฐานจะค้นหารูปแบบการเกิดร่วมกันที่พบบ่อยทั้งหมด โดยไม่มีการรับรู้ว่าสิ่งใดมีความสำคัญ กฎความสัมพันธ์แบบกึ่งมีผู้สอนเปลี่ยนแปลงสิ่งนี้โดยการอนุญาตให้ตัวอย่างที่มีป้ายกำกับจำนวนเล็กน้อย หรือข้อจำกัดของโดเมน ชี้นำการค้นหา โดยกฎที่สอดคล้องกับโครงสร้างคลาสที่ทราบจะได้รับความนิยมมากกว่ากฎที่พบบ่อยทางสถิติแต่ไม่มีความหมาย ลองนึกภาพว่าเป็นการให้คำใบ้แก่อัลกอริทึมเกี่ยวกับสิ่งที่นักวิเคราะห์สนใจ เพื่อที่อัลกอริทึมจะได้หยุดแสดงรูปแบบที่ซ้ำซากหรือเป็นที่ทราบกันดีอยู่แล้ว และเน้นความสัมพันธ์ใหม่ที่นำไปปฏิบัติได้จริงแทน ผลลัพธ์ที่ได้คือการผสมผสานระหว่างความกว้างของการค้นหารูปแบบที่ไม่มีผู้สอนเข้ากับการชี้นำที่เพียงพอเพื่อให้ผลลัพธ์มีความเกี่ยวข้อง
ประวัติศาสตร์
การทำเหมืองกฎความสัมพันธ์ถูกทำให้เป็นทางการโดย Agrawal, Imielinski และ Swami ในปี 1993 ด้วยการแนะนำอัลกอริทึม Apriori โดยมีเป้าหมายเพื่อการค้นหาชุดรายการที่พบบ่อยแบบไม่มีผู้สอนในข้อมูลตะกร้าสินค้า การรวมป้ายคลาสและข้อจำกัดเข้ากับการทำเหมืองกฎความสัมพันธ์ได้รับแรงผลักดันในช่วงต้นทศวรรษ 2000 โดยเฉพาะอย่างยิ่งผ่านเฟรมเวิร์ก CMAR และ CBA ของ Liu และเพื่อนร่วมงาน ซึ่งปฏิบัติต่อป้ายคลาสในฐานะส่วนท้ายของกฎ ส่วนขยายแบบกึ่งมีผู้สอนเกิดขึ้นเมื่อนักวิจัยตระหนักว่าการกำกับดูแลบางส่วนสามารถลดการระเบิดเชิงการจัด (combinatorial explosion) ของกฎที่เป็นผู้สมัคร ในขณะที่ยังคงรักษาการมีส่วนร่วมทางสถิติของข้อมูลที่ไม่มีป้ายกำกับ วิธีการนี้ปรากฏในสาขาชีวสารสนเทศศาสตร์ (bioinformatics) การทำเหมืองข้อมูลทางการศึกษา (educational data mining) และระบบแนะนำ (recommendation systems)
ควรใช้เมื่อใด
ใช้การทำเหมืองกฎความสัมพันธ์แบบกึ่งมีผู้สอนเมื่อคุณมีชุดข้อมูลธุรกรรมหรือตารางขนาดใหญ่ ซึ่งมีเพียงส่วนเล็กน้อยที่มีป้ายคลาสหรือคำอธิบายประกอบโดเมน และคุณต้องการค้นหารูปแบบการเกิดร่วมกันที่เกี่ยวข้องอย่างแท้จริงกับแนวคิดเป้าหมาย แทนที่จะเป็นเพียงแค่ความถี่ วิธีนี้เหมาะสำหรับการวิเคราะห์ตะกร้าสินค้า (market-basket analysis) ที่มีผลลัพธ์การซื้อที่ทราบเพียงบางส่วน การทำเหมืองเวชระเบียนที่กรณีเพียงบางส่วนมีการวินิจฉัยที่ยืนยันแล้ว และการจำแนกประเภทข้อความที่เอกสารที่มีป้ายกำกับมีน้อย ควรหลีกเลี่ยงเมื่อส่วนที่มีป้ายกำกับมีน้อยมาก (น้อยกว่าสองสามสิบตัวอย่างที่มีป้ายกำกับ) เมื่อการกำกับดูแลแบบเต็ม (full supervision) สามารถทำได้ หรือเมื่อข้อกำหนดด้านความสามารถในการตีความต้องการโมเดลที่ง่ายกว่า เช่น การถดถอยโลจิสติก (logistic regression) หรือต้นไม้ตัดสินใจ (decision tree)
ข้อจำกัดและข้อควรพิจารณา
- คุณภาพของกฎขึ้นอยู่กับคุณภาพและการเป็นตัวแทนของชุดเริ่มต้นที่มีป้ายกำกับอย่างมาก ชุดที่มีป้ายกำกับที่เอนเอียงจะส่งต่อความเอนเอียงไปยังกฎที่ค้นพบ
- การผสมผสานระหว่าง support, confidence และเกณฑ์ข้อจำกัดสร้างพื้นที่ไฮเปอร์พารามิเตอร์ขนาดใหญ่ที่ปรับแต่งได้ยากหากไม่มีข้อมูลการตรวจสอบที่มีป้ายกำกับ
- ต้นทุนการคำนวณจะเพิ่มขึ้นตามจำนวนชุดรายการที่เป็นผู้สมัคร ชุดข้อมูลที่มีพื้นที่รายการมิติสูงมากต้องการกลยุทธ์การตัดทอนที่เข้มงวด
- วงจรการฝึกฝนตนเองสามารถขยายข้อผิดพลาดในช่วงต้นได้หากป้ายกำกับเทียมเริ่มต้นมีสัญญาณรบกวน (noisy) ซึ่งนำไปสู่การเลื่อนไหลของกฎเมื่อทำซ้ำ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ใช้ประโยชน์จากข้อมูลที่ไม่มีป้ายกำกับจำนวนมากเพื่อค้นหารูปแบบที่จะมองไม่เห็นทางสถิติด้วยข้อมูลที่มีป้ายกำกับเพียงอย่างเดียว
- ข้อจำกัดที่ได้จากป้ายกำกับจะตัดทอนกฎที่ไม่เกี่ยวข้อง ทำให้ได้ชุดกฎที่เล็กลงและนำไปปฏิบัติได้จริงมากขึ้นกว่าการทำเหมืองแบบไม่มีผู้สอนเพียงอย่างเดียว
- กฎยังคงเป็นข้อความ IF-THEN ที่มนุษย์อ่านได้ ซึ่งรักษาข้อได้เปรียบด้านความสามารถในการตีความของการเรียนรู้กฎความสัมพันธ์แบบดั้งเดิม
- การปรับปรุงด้วยตนเอง (self-training refinement) สามารถปรับปรุงคุณภาพของกฎและการครอบคลุมของป้ายกำกับเทียมได้อย่างต่อเนื่องโดยไม่ต้องเสียค่าใช้จ่ายในการติดป้ายกำกับเพิ่มเติม
- ยืดหยุ่น: ข้อจำกัดสามารถเข้ารหัสความรู้โดเมนที่นอกเหนือไปจากป้ายคลาสอย่างง่าย (เช่น ลำดับเวลา ลำดับชั้นของรายการ)
การประยุกต์ใช้
- การทำเหมืองเวชระเบียนที่บันทึกของผู้ป่วยเพียงบางส่วนเท่านั้นที่มีการวินิจฉัยที่ยืนยันแล้ว
- การวิเคราะห์ตะกร้าสินค้าโดยได้รับคำแนะนำจากชุดผลลัพธ์การซื้อที่มีมูลค่าสูงที่ทราบเพียงบางส่วน
- การทำเหมืองข้อมูลทางการศึกษาเพื่อค้นหารูปแบบพฤติกรรมการเรียนรู้ที่เกี่ยวข้องกับผลลัพธ์ประสิทธิภาพของนักเรียนที่มีป้ายกำกับจำนวนเล็กน้อย
- การทำเหมืองข้อความและการจำแนกประเภทเอกสารด้วยคลังข้อมูลที่มีป้ายกำกับที่หายาก
- การตรวจจับการบุกรุก (Intrusion detection) ที่เหตุการณ์เครือข่ายเพียงส่วนน้อยเท่านั้นที่ได้รับการยืนยันว่าเป็นผู้โจมตี
- ระบบแนะนำที่ใช้การให้คะแนนของผู้ใช้แบบเบา (sparse user ratings) เพื่อจำกัดกฎการเกิดร่วมกันของรายการ
วิธีการทำงาน
วิธีการทำงาน
ชุดข้อมูลจะถูกแบ่งออกเป็นส่วนที่มีป้ายกำกับจำนวนเล็กน้อย (พร้อมป้ายคลาสที่ทราบหรือข้อจำกัดที่ผู้ใช้ระบุ) และส่วนที่ไม่มีป้ายกำกับจำนวนมาก ตัวอย่างที่มีป้ายกำกับทำหน้าที่เป็นจุดเริ่มต้นหรือจุดยึดที่กำหนดพื้นที่แนวคิดเป้าหมาย ในขณะที่ธุรกรรมที่ไม่มีป้ายกำกับให้มวลทางสถิติที่จำเป็นในการคำนวณจำนวนการสนับสนุน (support count) ที่เชื่อถือได้
การแจงนับชุดรายการที่พบบ่อย (frequent itemset enumeration) จะดำเนินการกับทั้งข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับ โดยใช้อัลกอริทึมแบบดั้งเดิม เช่น Apriori หรือ FP-Growth การคำนวณค่า support เป็นสัดส่วนของธุรกรรมที่มีชุดรายการที่กำหนด ชุดรายการที่เกินเกณฑ์ minimum support จะถูกเก็บไว้เป็นผู้สมัครสำหรับการสร้างกฎ
สูตร
\text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \text{min\_sup}ข้อจำกัดที่ได้จากป้ายกำกับหรือที่ผู้ใช้ระบุจะถูกนำมาใช้เพื่อตัดทอนพื้นที่ของผู้สมัคร ข้อจำกัดอาจอยู่ในรูปแบบของ must-link (สองรายการควรเกิดร่วมกันในส่วนท้าย (consequent) กับคลาสเป้าหมาย) cannot-link (บางชุดค่าผสมจะถูกยกเว้น) หรือตัวกรองป้ายคลาสที่จำกัดว่ากฎใดเกี่ยวข้องกับผลลัพธ์เป้าหมาย สิ่งนี้จะช่วยลดจำนวนกฎที่ผิดพลาดหรือซ้ำซ้อนได้อย่างมาก
กฎที่ถูกต้อง X นำไปสู่ Y จะถูกสร้างขึ้นจากชุดรายการที่พบบ่อยที่เหลืออยู่ โดยกรองด้วยเกณฑ์ minimum confidence ค่า confidence วัดความน่าจะเป็นแบบมีเงื่อนไขที่ Y ปรากฏเมื่อกำหนด X ในการตั้งค่าแบบกึ่งมีผู้สอน กฎที่มีส่วนท้ายสอดคล้องกับป้ายคลาสหรือข้อจำกัดที่ติดป้ายกำกับจะได้รับความสำคัญหรือให้น้ำหนักมากขึ้น
สูตร
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}กฎที่ค้นพบสามารถนำมาใช้ซ้ำๆ เพื่อกำหนดป้ายกำกับเทียม (pseudo-labels) ให้กับธุรกรรมที่ไม่มีป้ายกำกับก่อนหน้านี้ ซึ่งจะถูกป้อนกลับเข้าสู่รอบการทำเหมืองครั้งต่อไป วงจรการฝึกฝนตนเอง (self-training loop) นี้จะค่อยๆ เพิ่มพูนคลังข้อมูลที่มีป้ายกำกับและทำให้ชุดกฎมีความคมชัดขึ้น โดยจะบรรจบกันเมื่อไม่พบกฎที่มีความมั่นใจสูงใหม่ หรือเมื่อถึงขีดจำกัดการทำซ้ำที่กำหนดไว้ล่วงหน้า
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่า minimum support ต่ำเกินไปโดยไม่มีข้อจำกัด จะทำให้ผลลัพธ์เต็มไปด้วยกฎที่พบบ่อยแต่ไม่มีข้อมูล
- การละเลยความไม่สมดุลของคลาสในชุดเริ่มต้นที่มีป้ายกำกับ ซึ่งทำให้ตัวกรองข้อจำกัดให้ความสำคัญกับคลาสส่วนใหญ่ในกฎที่ค้นพบมากเกินไป
- การปฏิบัติต่อ confidence ในฐานะมาตรวัดความน่าสนใจเพียงอย่างเดียว และพลาดกฎที่มี lift หรือ conviction สูงซึ่งมีประโยชน์ในทางปฏิบัติมากกว่า
- การข้ามการประเมินคุณภาพการทำนายของกฎที่แยกออกมา และยอมรับกฎที่ทำเหมืองได้ตามที่เป็นจริงโดยไม่มีการตรวจสอบข้อมูลที่ไม่เคยเห็น
- การผสมปนเปกันระหว่างความสัมพันธ์ (การเกิดร่วมกัน) กับความเป็นเหตุเป็นผลเมื่อรายงานผลการค้นพบ
คำถามที่พบบ่อย
วิธีนี้แตกต่างจากการทำเหมืองกฎความสัมพันธ์มาตรฐานอย่างไร
การทำเหมืองกฎความสัมพันธ์แบบมาตรฐานเป็นการทำเหมืองแบบไม่มีผู้สอนอย่างสมบูรณ์: ค้นหารูปแบบการเกิดร่วมกันทั้งหมดที่อยู่เหนือเกณฑ์ support และ confidence โดยไม่มีแนวคิดเกี่ยวกับคลาสเป้าหมาย กฎความสัมพันธ์แบบกึ่งมีผู้สอนจะรวมข้อมูลป้ายกำกับบางส่วนหรือข้อจำกัดของโดเมนเพื่อกรองและจัดลำดับความสำคัญของกฎที่เกี่ยวข้องกับผลลัพธ์เฉพาะ ทำให้ได้ชุดผลลัพธ์ที่เล็กลงและนำไปปฏิบัติได้จริงมากขึ้น
ต้องใช้ข้อมูลที่มีป้ายกำกับมากน้อยเพียงใด
แม้แต่ชุดข้อมูลที่มีป้ายกำกับจำนวนเล็กน้อยก็สามารถให้ข้อจำกัดที่เป็นประโยชน์ได้ แต่คุณภาพของชุดเริ่มต้นมีความสำคัญมากกว่าปริมาณ ในทางปฏิบัติ แนะนำให้มีตัวอย่างที่มีป้ายกำกับอย่างน้อยสองสามสิบตัวอย่างต่อคลาส เพื่อหลีกเลี่ยงข้อจำกัดที่เอนเอียงอย่างรุนแรง หากป้ายกำกับมีน้อยมาก ควรตรวจสอบผลลัพธ์อย่างระมัดระวังบนชุดข้อมูลที่มีป้ายกำกับที่แยกออกมา
ฉันควรตั้งค่าเกณฑ์ support และ confidence เท่าใด
ไม่มีคำตอบที่เป็นสากล: เกณฑ์ขึ้นอยู่กับขนาดของชุดข้อมูล โดเมน และจำนวนกฎที่คุณสามารถประเมินได้จริง เริ่มต้นด้วยเกณฑ์ปานกลาง (เช่น support 0.05–0.10, confidence 0.60–0.80) ตรวจสอบจำนวนกฎที่ได้ และปรับเปลี่ยน เมื่อมีการใช้ข้อจำกัด คุณมักจะสามารถใช้เกณฑ์ support ที่ต่ำลงเล็กน้อยได้ เนื่องจากกฎที่ไม่เกี่ยวข้องจะถูกกรองโดยเงื่อนไขป้ายกำกับ
วิธีนี้สามารถจัดการกับคุณลักษณะต่อเนื่องหรือตัวเลขได้หรือไม่
การทำเหมืองกฎความสัมพันธ์ทำงานกับรายการที่ไม่ต่อเนื่อง (discrete items) โดยธรรมชาติ คุณลักษณะต่อเนื่องต้องถูกแปลงเป็นช่วง (discretised) ก่อนการทำเหมือง กลยุทธ์การแบ่งช่วงที่เลือกส่งผลต่อชุดรายการที่จะกลายเป็นที่พบบ่อย ดังนั้นจึงควรทดลองกับการแบ่งช่วงที่มีความกว้างเท่ากัน (equal-width) ความถี่เท่ากัน (equal-frequency) และการแบ่งช่วงตามโดเมน (domain-driven) และตรวจสอบว่าผลลัพธ์มีความอ่อนไหวต่อการเลือกอย่างไร
ฉันจะประเมินคุณภาพของกฎที่ค้นพบได้อย่างไร
นอกเหนือจาก support และ confidence ให้ประเมินกฎโดยใช้ lift (ค่าที่มากกว่า 1 บ่งชี้ว่าเกิดร่วมกันจริงนอกเหนือจากโอกาส) conviction และ leverage หากกฎถูกใช้เพื่อการทำนาย ให้วัดความแม่นยำในการจำแนกประเภท (classification accuracy) F1 หรือ AUC บนชุดข้อมูลที่มีป้ายกำกับที่แยกออกมา มาตรวัดความน่าสนใจเพียงอย่างเดียวไม่เพียงพอสำหรับการประเมินประโยชน์ในทางปฏิบัติ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Liu, B., Hsu, W., & Ma, Y. (2003). Integrating Classification and Association Rule Mining. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), pp. 339–346.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วAssociation rule learning. Wikipedia.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว