Skip to content
กลับไปยังผลการค้นหา

การวิเคราะห์แนวคิดเชิงรูปนัย (Formal Concept Analysis - FCA)

ผู้เสนอ
Rudolf Wille & Bernhard Ganter
ปี
1982
ประเภท
Lattice-based knowledge representation / concept mining
กลุ่มวิธี
Concept analysis

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การวิเคราะห์แนวคิดเชิงรูปนัย (FCA) เป็นการสกัดโครงสร้างลำดับชั้นของแนวคิดจากตารางข้อมูลเชิงวัตถุและคุณลักษณะที่เรียบง่าย ก่อตั้งขึ้นโดย Rudolf Wille ในปี 1982 โดยอาศัยทฤษฎีแลตทิซ (lattice theory) FCA จับคู่เซตของวัตถุกับคุณลักษณะที่วัตถุเหล่านั้นมีร่วมกันเพื่อสร้าง 'แนวคิดเชิงรูปนัย' (formal concepts) จากนั้นจึงจัดระเบียบแนวคิดเหล่านี้ให้อยู่ในรูปของแลตทิซแนวคิด (concept lattice) ซึ่งเป็นลำดับชั้นที่อิงหลักการทางคณิตศาสตร์ สามารถตีความได้ และใช้สำหรับการค้นพบองค์ความรู้ การสร้างออนโทโลยี และการวิเคราะห์ข้อมูลเชิงหมวดหมู่ที่สามารถอธิบายได้

แนวคิดเบื้องหลังวิธีการ

เริ่มต้นด้วยตารางไขว้ (cross-table) โดยแถวแทนวัตถุ (objects) และคอลัมน์แทนคุณลักษณะ (attributes) เครื่องหมายในตารางบ่งชี้ว่า 'วัตถุนี้มีคุณลักษณะนี้' แนวคิด (concept) คือการจัดกลุ่มตามธรรมชาติ: เซตของวัตถุร่วมกับคุณลักษณะที่วัตถุเหล่านั้นมีร่วมกันทั้งหมด และในทางกลับกันคือ เซตของคุณลักษณะทั้งหมดที่วัตถุเหล่านั้นมีร่วมกัน 'นก' อาจเป็นวัตถุที่มี {มีขน, วางไข่, บินได้?}; การจำกัดคุณลักษณะให้แคบลงจะลดจำนวนวัตถุ ในขณะที่การขยายคุณลักษณะจะเพิ่มจำนวนวัตถุ FCA จะค้นหาคู่ (เซตวัตถุ, เซตคุณลักษณะ) ที่สอดคล้องกันทั้งหมด และจัดเรียงเป็นแลตทิซ โดยการเลื่อนขึ้นเป็นการทำให้ทั่วไป (วัตถุมากขึ้น, คุณลักษณะที่ใช้ร่วมกันน้อยลง) และการเลื่อนลงเป็นการทำให้เฉพาะเจาะจง ผลลัพธ์คือลำดับชั้นแนวคิดที่โปร่งใสซึ่งอ่านได้โดยตรงจากข้อมูล

ประวัติศาสตร์

Rudolf Wille ได้ริเริ่มการวิเคราะห์แนวคิดเชิงรูปนัยในบทความปี 1982 เรื่อง 'Restructuring lattice theory' โดยปรับกรอบทฤษฎีแลตทิซเชิงนามธรรมของ Birkhoff รอบแนวคิดเชิงรูปธรรมของแนวคิดในฐานะคู่ของวัตถุและคุณลักษณะ ร่วมกับ Bernhard Ganter เขาได้พัฒนาพื้นฐานทางคณิตศาสตร์ (ฉบับภาษาเยอรมันปี 1996; ฉบับแปลภาษาอังกฤษปี 1999) ซึ่งก่อตั้งแลตทิซแนวคิด การเชื่อมโยงแบบกาลัว (Galois connection) และฐานการบอกเป็นนัยของ Duquenne-Guigues FCA ได้เติบโตเป็นสาขาวิชาที่มีความเคลื่อนไหว ครอบคลุมการแทนความรู้ การทำเหมืองข้อมูล การค้นคืนสารสนเทศ และวิศวกรรมซอฟต์แวร์ โดยมีความเชื่อมโยงอย่างแน่นแฟ้นกับการทำเหมืองกฎความสัมพันธ์ (closed itemsets), ทฤษฎีเซตรอบ (rough set theory), และการคำนวณแบบละเอียด (granular computing)

ควรใช้เมื่อใด

ใช้การวิเคราะห์แนวคิดเชิงรูปนัยเพื่อค้นหาและแสดงภาพโครงสร้างแนวคิดที่ซ่อนอยู่ในข้อมูลเชิงหมวดหมู่/เลขฐานสอง — สำหรับวิศวกรรมความรู้และการสร้างออนโทโลยี, การค้นคืนสารสนเทศและการเรียกดูแบบแบ่งส่วน (faceted browsing), การวิเคราะห์ซอฟต์แวร์และข้อมูล, การศึกษาความสัมพันธ์ระหว่างยีน/คำศัพท์, และการจัดกลุ่มที่อธิบายได้ซึ่งต้องการลำดับชั้นที่โปร่งใสและกฎที่แม่นยำ เหมาะอย่างยิ่งเมื่อคุณต้องการแนวคิดที่ได้รับการสนับสนุนทั้งหมดและการบอกเป็นนัยระหว่างคุณลักษณะ ไม่ใช่เพียงแค่การจัดกลุ่มเดียว ข้อควรระวัง: แลตทิซแนวคิดอาจมีขนาดใหญ่ขึ้นแบบทวีคูณตามขนาดของบริบท ดังนั้นบริบทขนาดใหญ่หรือหนาแน่นจึงต้องการการตัดแต่ง (iceberg lattices, stability/support thresholds); FCA จัดการกับคุณลักษณะแบบเลขฐานสองโดยธรรมชาติ ดังนั้นข้อมูลเชิงตัวเลขหรือข้อมูลที่มีหลายค่าจะต้องถูก 'ปรับสเกล' (scaled) เป็นรูปแบบเลขฐานสองก่อน ซึ่งเป็นทางเลือกในการสร้างแบบจำลองที่ส่งผลต่อผลลัพธ์ FCA เชื่อมโยงอย่างใกล้ชิดกับการทำเหมืองกฎความสัมพันธ์ (association-rule mining), ทฤษฎีเซตรอบ (rough sets), และการคำนวณแบบละเอียด (granular computing)

ข้อจำกัดและข้อควรพิจารณา

  • แลตทิซแนวคิดอาจมีขนาดใหญ่ขึ้นแบบทวีคูณสำหรับบริบทขนาดใหญ่หรือหนาแน่น
  • โดยธรรมชาติเป็นแบบเลขฐานสอง — ข้อมูลที่มีหลายค่าต้องมีการปรับสเกลแนวคิด ซึ่งเป็นขั้นตอนที่ขึ้นอยู่กับการตัดสินใจ
  • ไวต่อสัญญาณรบกวน: เครื่องหมายที่ผิดพลาดเพียงไม่กี่อย่างสามารถทำให้แลตทิซแตกเป็นส่วนๆ ได้
  • การแสดงภาพทำได้ยากเมื่อมีแนวคิดจำนวนมากเกินกว่าระดับปานกลาง

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • สกัดลำดับชั้นแนวคิดที่แม่นยำและอิงหลักการทางคณิตศาสตร์โดยตรงจากข้อมูล
  • ตีความได้สูง: แนวคิด ขอบเขต/เจตนา และการบอกเป็นนัย สามารถอ่านได้โดยมนุษย์
  • ให้กฎการบอกเป็นนัยของคุณลักษณะ (ฐานรากที่น้อยที่สุด) ซึ่งมีประโยชน์สำหรับฐานความรู้
  • เชื่อมโยงตามธรรมชาติกับกฎความสัมพันธ์ ทฤษฎีเซตรอบ และวิศวกรรมออนโทโลยี

การประยุกต์ใช้

  • วิศวกรรมความรู้และการสร้างออนโทโลยีจากข้อมูลวัตถุ-คุณลักษณะ
  • การค้นคืนสารสนเทศและการเรียกดูแบบแบ่งส่วน/แนวคิดของชุดเอกสาร
  • การทำเหมืองการบอกเป็นนัยของคุณลักษณะและ closed itemsets ในการวิเคราะห์ข้อมูล
  • การวิเคราะห์วิศวกรรมซอฟต์แวร์ (เช่น ลำดับชั้นคลาส/ฟีเจอร์)
  • การศึกษาความสัมพันธ์ระหว่างคำศัพท์ในชีวการแพทย์และยีน-การแสดงออก

วิธีการทำงาน

วิธีการทำงาน

1

ข้อมูลนำเข้าคือบริบทเชิงรูปนัย (formal context) ซึ่งประกอบด้วยเซตของวัตถุ G, เซตของคุณลักษณะ M, และความสัมพันธ์การเกิด (incidence relation) I ที่เป็นเลขฐานสอง ซึ่งระบุว่าวัตถุใดมีคุณลักษณะใด นี่เป็นเพียงตารางวัตถุ × คุณลักษณะแบบบูลีน (Boolean)

สูตร
\mathbb{K} = (G, M, I),\quad I \subseteq G \times M
2

มีตัวดำเนินการ (operator) สองตัวสำหรับการอนุมาน (Galois operators) ที่เชื่อมโยงวัตถุและคุณลักษณะ: สำหรับเซตของวัตถุ A, A′ คือเซตของคุณลักษณะที่วัตถุทั้งหมดใน A มีร่วมกัน; สำหรับเซตของคุณลักษณะ B, B′ คือเซตของวัตถุที่มีคุณลักษณะทั้งหมดใน B การใช้ตัวดำเนินการซ้ำสองครั้งจะให้ผลลัพธ์เป็น 'การปิด' (closure) ซึ่งจับ 'ขอบเขต/เจตนาตามธรรมชาติที่เกิดจากเซตเริ่มต้น'

สูตร
A' = \{m \mid \forall g\in A,\ (g,m)\in I\},\quad B' = \{g \mid \forall m\in B,\ (g,m)\in I\}
3

แนวคิดเชิงรูปนัยคือคู่ (A, B) — โดย A คือขอบเขต (extent - เซตของวัตถุ) และ B คือเจตนา (intent - เซตของคุณลักษณะ) ที่มีการปิดซึ่งกันและกัน (mutually closed): คุณลักษณะที่วัตถุใน A มีร่วมกันคือ B พอดี และวัตถุที่มีคุณลักษณะ B คือ A พอดี คู่เหล่านี้คือกลุ่มที่เสถียรและไม่ขึ้นกับดุลยพินิจที่ข้อมูลสนับสนุน

สูตร
(A,B)\ \text{is a concept} \iff A' = B \ \text{and}\ B' = A
4

จัดลำดับแนวคิดตามการบรรจุของขอบเขต (extent inclusion): แนวคิดหนึ่งจะอยู่ต่ำกว่าอีกแนวคิดหนึ่งหากเซตวัตถุของมันถูกบรรจุอยู่ในเซตของอีกแนวคิดหนึ่ง (หรือเทียบเท่าคือเซตคุณลักษณะของมันบรรจุเซตของคุณลักษณะของอีกแนวคิดหนึ่ง) อันดับบางส่วนนี้จะเป็นแลตทิซสมบูรณ์เสมอ (complete lattice) — คือแลตทิซแนวคิด (concept lattice) ซึ่งวาดเป็นแผนภาพฮาสเซ (Hasse diagram) การบอกเป็นนัยของคุณลักษณะ (attribute implications — กฎเช่น 'คุณลักษณะ X มักมาพร้อมกับคุณลักษณะ y') สามารถอ่านได้จากโครงสร้างเดียวกัน (ฐานรากของ Duquenne-Guigues ให้ชุดกฎที่น้อยที่สุด)

สูตร
(A_1,B_1) \le (A_2,B_2) \iff A_1 \subseteq A_2\ (\Leftrightarrow B_2 \subseteq B_1)

ข้อผิดพลาดที่พบบ่อย

  • การนำไปใช้กับบริบทขนาดใหญ่และหนาแน่นโดยไม่มีการตัดแต่ง (iceberg/stability) และจมอยู่กับแนวคิดจำนวนมาก
  • การปรับสเกลคุณลักษณะเชิงตัวเลขอย่างไม่ระมัดระวัง ซึ่งเป็นการกำหนดแนวคิดที่พบโดยพลการ
  • การปฏิบัติต่อบริบทที่มีสัญญาณรบกวนเสมือนว่าเป็นข้อมูลที่แม่นยำ ทำให้เกิดแนวคิดที่ซ้ำกันเกือบทั้งหมดจำนวนมาก
  • การสับสนระหว่างการบอกเป็นนัยที่แม่นยำของ FCA กับกฎความสัมพันธ์ทางสถิติ (โดยปกติไม่มี support/confidence)

คำถามที่พบบ่อย

แนวคิดเชิงรูปนัยคืออะไร?

แนวคิดเชิงรูปนัยคือคู่ของขอบเขต (เซตของวัตถุ) และเจตนา (เซตของคุณลักษณะที่วัตถุเหล่านั้นมีร่วมกันทั้งหมด) ซึ่งมีการปิดซึ่งกันและกัน: คุณลักษณะที่วัตถุในขอบเขตมีร่วมกันคือเจตนาพอดี และวัตถุที่มีเจตนาคือขอบเขตพอดี คู่ที่สอดคล้องกันซึ่งกันและกันเหล่านี้คือแนวคิดตามธรรมชาติที่ข้อมูลสนับสนุน

FCA เกี่ยวข้องกับการจัดกลุ่ม (clustering) อย่างไร?

การจัดกลุ่มจะสร้างการแบ่งพาร์ติชันออกเป็นกลุ่มๆ โดยทั่วไปอาศัยความคล้ายคลึงกัน FCA จะสร้างแลตทิซที่สมบูรณ์ของแนวคิดที่สอดคล้องกันทั้งหมด โดยจัดลำดับจากทั่วไปไปเฉพาะเจาะจง พร้อมคำจำกัดความของคุณลักษณะและการบอกเป็นนัยที่แม่นยำ FCA เป็นลำดับชั้นของแนวคิดที่โปร่งใสและทับซ้อนกัน แทนที่จะเป็นการแบ่งพาร์ติชันแบบแบนราบเพียงครั้งเดียว

FCA สามารถจัดการกับข้อมูลเชิงตัวเลขได้หรือไม่?

โดยตรงไม่ได้ — FCA ทำงานกับบริบทวัตถุ-คุณลักษณะแบบเลขฐานสอง คุณลักษณะเชิงตัวเลขหรือที่มีหลายค่าจะต้องถูกแปลงเป็นแบบเลขฐานสองผ่านการปรับสเกลแนวคิด (เช่น การใช้เกณฑ์หรือการเข้ารหัสช่วง) การปรับสเกลนี้เป็นการตัดสินใจในการสร้างแบบจำลองที่ส่งผลอย่างมากต่อแนวคิดที่ได้ ดังนั้นจึงควรทำอย่างรอบคอบ

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Wille, R. (1982). Restructuring lattice theory: an approach based on hierarchies of concepts. In I. Rival (Ed.), Ordered Sets (pp. 445–470). Reidel.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Ganter, B., & Wille, R. (1999). Formal Concept Analysis: Mathematical Foundations. Springer.

    ISBN: 978-3-540-62771-5
    คัดลอกแล้ว