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

ปัจจัยค่าผิดปกติเฉพาะที่ (Local Outlier Factor: LOF)

ผู้เสนอ
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
ปี
2000
ประเภท
Density-based anomaly detection (unsupervised)

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

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

ใช้ทำอะไร?

Local Outlier Factor (LOF) เป็นอัลกอริทึมการตรวจจับความผิดปกติแบบไม่มีผู้สอน (unsupervised anomaly detection) ที่อาศัยความหนาแน่น (density-based) ซึ่งนำเสนอโดย Breunig, Kriegel, Ng และ Sander ในปี 2000 อัลกอริทึมนี้กำหนดคะแนนความผิดปกติแบบต่อเนื่อง (continuous outlier score) ให้กับแต่ละจุดข้อมูล ซึ่งเป็นการวัดว่าจุดนั้นมีความโดดเดี่ยวเมื่อเทียบกับเพื่อนบ้านในละแวกใกล้เคียงมากน้อยเพียงใด ทำให้สามารถตรวจจับความผิดปกติที่วิธีการแบบทั่วโลก (global methods) พลาดไปได้ เนื่องจากจุดเหล่านั้นอาจรวมตัวอยู่ในกลุ่มที่หนาแน่นในส่วนอื่นของปริภูมิข้อมูล

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

ลองนึกภาพแผนที่เมืองที่ผู้คนส่วนใหญ่อาศัยอยู่ในเขตเมืองที่หนาแน่น บ้านหลังหนึ่งที่ตั้งอยู่โดดเดี่ยวในชนบทนั้นเห็นได้ชัดว่ามีความโดดเดี่ยว แต่ LOF ก้าวไปไกลกว่านั้น: มันสามารถระบุบ้านที่ตั้งอยู่ในชานเมืองที่มีความหนาแน่นปานกลางได้ หากเพื่อนบ้านที่อยู่ใกล้ที่สุดทั้งหมดของมันรวมตัวกันอยู่ในกลุ่มที่หนาแน่นยิ่งกว่าเดิม แทนที่จะถามว่า 'จุดนี้อยู่ห่างจากทุกสิ่งหรือไม่?' LOF จะถามว่า 'ละแวกใกล้เคียงของจุดนี้มีความเบาบางกว่าละแวกใกล้เคียงของเพื่อนบ้านของมันเองมากหรือไม่?' จุดที่เพื่อนบ้านทั้งหมดอาศัยอยู่รวมกันอย่างหนาแน่นกว่าตัวจุดเอง จะได้คะแนน LOF สูง ซึ่งบ่งชี้ว่ามันเป็นความผิดปกติเฉพาะที่ (local outlier) แม้ว่าในภาพรวมจะไม่ได้อยู่ในบริเวณที่ว่างเปล่าก็ตาม

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

LOF ถูกนำเสนอโดย Markus Breunig, Hans-Peter Kriegel, Raymond Ng และ Jörg Sander ในการประชุม ACM SIGMOD ปี 2000 เพื่อแก้ไขข้อจำกัดที่รับรู้ของวิธีการตรวจจับความผิดปกติที่มีอยู่ — ซึ่งอาศัยเกณฑ์ระยะห่างแบบทั่วโลก และทำให้สับสนระหว่างความผิดปกติเฉพาะที่กับจุดปกติในบริเวณที่มีความหนาแน่นน้อยกว่า กระดาษนำเสนอแนวคิดของความหนาแน่นที่สามารถเข้าถึงได้เฉพาะที่ (local reachability density) และคะแนน LOF ซึ่งกลายเป็นแหล่งอ้างอิงหลักในการตรวจจับความผิดปกติอย่างรวดเร็ว นับตั้งแต่นั้นมา ได้มีการพัฒนาต่อยอดโดยมีรูปแบบต่างๆ มากมาย รวมถึง LoOP (local outlier probabilities), LOCI และ COF และถูกรวมอยู่ในไลบรารีการเรียนรู้ของเครื่องที่สำคัญ กระดาษ ACM SIGMOD ปี 2000 ได้รับการอ้างอิงหลายพันครั้ง และถือเป็นหนึ่งในผลงานพื้นฐานในด้านการทำเหมืองข้อมูลที่อาศัยความหนาแน่น

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

LOF เหมาะสมเมื่อคาดว่าความผิดปกติจะเกิดขึ้นในกลุ่มที่มีความหนาแน่นแตกต่างกัน และเมื่อเกณฑ์ระยะห่างแบบทั่วโลกจะพลาดความผิดปกติที่ซ่อนอยู่ในบริเวณที่เบาบาง หรือระบุจุดที่ผิดพลาดในกลุ่มที่เบาบางอย่างสม่ำเสมอได้อย่างไม่ถูกต้อง อัลกอริทึมทำงานบนปริภูมิคุณลักษณะต่อเนื่องใดๆ ที่มีเมตริกวัดระยะทางที่มีความหมาย และไม่ต้องการตัวอย่างข้อมูลที่มีป้ายกำกับความผิดปกติ (เป็นแบบไม่มีผู้สอนโดยสมบูรณ์) เหมาะสำหรับแอปพลิเคชัน เช่น การตรวจจับการฉ้อโกง การตรวจจับการบุกรุกเครือข่าย การควบคุมคุณภาพการผลิต และการคัดกรองความผิดปกติทางการแพทย์ ข้อสมมติฐานหลักคือจุดปกติ (inliers) ก่อตัวเป็นละแวกใกล้เคียงเฉพาะที่ที่ค่อนข้างเหนียวแน่น และสามารถคำนวณระยะห่างระหว่างคู่ได้ ความหมาย LOF ทำงานได้ดีที่สุดเมื่อ n มีค่าอย่างน้อยหลักสิบถึงหลักร้อยต้นๆ สำหรับข้อมูลที่มีมิติสูงมาก (curse of dimensionality) ระยะห่างจะมีความสามารถในการแยกแยะน้อยลง และแนะนำให้ทำการลดมิติ (dimensionality reduction) หรือการเลือกคุณลักษณะ (feature selection) ก่อน

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

  • ความซับซ้อนเชิงเวลาแบบกำลังสอง (Quadratic time complexity) ในการนำไปใช้แบบตรงไปตรงมา ทำให้ช้าบนชุดข้อมูลขนาดใหญ่หากไม่มีการจัดทำดัชนีเพื่อนบ้านใกล้เคียงโดยประมาณ (approximate nearest-neighbor indexing)
  • ไวต่อการเลือกค่า k: หาก k น้อยเกินไปจะทำให้คะแนนมีความผันผวน (noisy) หาก k มากเกินไปจะทำให้โครงสร้างเฉพาะที่พร่ามัว
  • ประสิทธิภาพลดลงในปริภูมิที่มีมิติสูงมากเนื่องจาก curse of dimensionality
  • ไม่สามารถปรับขนาดให้เข้ากับข้อมูลแบบสตรีมมิ่ง (streaming) หรือข้อมูลออนไลน์ (online data) ได้ตามธรรมชาติโดยไม่ต้องคำนวณซ้ำ
  • ไม่มีโมเดลที่สามารถนำไปใช้ให้คะแนนจุดใหม่ได้โดยตรงโดยไม่ต้องเข้าถึงชุดข้อมูลฝึกสอน

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

จุดแข็ง

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

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

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

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

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

1

สำหรับแต่ละจุด p อัลกอริทึมจะคำนวณ k-distance ก่อน ซึ่งคือระยะห่างไปยังเพื่อนบ้านที่ใกล้ที่สุดลำดับที่ k ของ p สิ่งนี้จะกำหนดขอบเขตของละแวกใกล้เคียงเฉพาะที่ (local neighborhood) ของ p จุดทั้งหมดที่อยู่ในระยะนั้นจะประกอบกันเป็นละแวกใกล้เคียง k (k-neighborhood) N_k(p) การเลือกค่า k จะควบคุมมาตราส่วนที่ประเมินความเป็นท้องถิ่น (locality) — ค่า k ที่น้อยจะจับโครงสร้างเฉพาะที่ในระดับละเอียด (fine-grained) ส่วนค่า k ที่มากขึ้นจะทำให้โครงสร้างนั้นเรียบขึ้น

สูตร
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

ระยะห่างที่สามารถเข้าถึงได้ (reachability distance) จาก p ไปยังเพื่อนบ้าน o ถูกกำหนดให้เป็นค่าสูงสุดระหว่าง k-distance ของ o และระยะห่างจริงแบบยุคลิด (หรือเมตริกอื่น) ระหว่าง p และ o การปรับให้เรียบนี้จะป้องกันความไม่เสถียรเมื่อจุดสองจุดอยู่ใกล้กันมาก: มันจะแทนที่ระยะห่างที่เล็กมากด้วยขอบเขตที่กว้างกว่าของละแวกใกล้เคียงของ o เอง ทำให้การประมาณความหนาแน่นมีความทนทานมากขึ้น

สูตร
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

ความหนาแน่นที่สามารถเข้าถึงได้เฉพาะที่ (local reachability density) ของ p (lrd) คือส่วนกลับของค่าเฉลี่ยระยะห่างที่สามารถเข้าถึงได้จาก p ไปยังเพื่อนบ้าน k ทั้งหมดของมัน จุดที่ล้อมรอบด้วยเพื่อนบ้านที่อยู่ใกล้กันมาก จะมีค่าเฉลี่ยระยะห่างที่สามารถเข้าถึงได้น้อย และดังนั้นจึงมี lrd สูง จุดที่อยู่ในบริเวณที่เบาบางจะมีค่าเฉลี่ยระยะห่างที่สามารถเข้าถึงได้มาก และมี lrd ต่ำ

สูตร
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}
4

คะแนน LOF ของ p คือค่าเฉลี่ยของอัตราส่วนค่า lrd ของเพื่อนบ้านต่อ lrd ของ p เอง หากเพื่อนบ้านของ p ทั้งหมดมีค่า lrd สูงกว่า p อย่างมีนัยสำคัญ — หมายความว่าพวกมันอาศัยอยู่ในบริเวณย่อยที่หนาแน่นกว่า — อัตราส่วนจะเกิน 1 ซึ่งบ่งชี้ว่า p เป็นความผิดปกติเฉพาะที่ คะแนนที่ใกล้เคียง 1 บ่งชี้ว่า p มีความหนาแน่นใกล้เคียงกับสภาพแวดล้อมของมัน คะแนนที่มากกว่า 1 มากๆ จะบ่งชี้ถึงจุดที่ผิดปกติมากขึ้นเรื่อยๆ การเปรียบเทียบที่คำนึงถึงความเป็นท้องถิ่นนี้คือสิ่งที่ทำให้ LOF แตกต่างจากวิธีการที่ใช้ระยะห่างเพียงอย่างเดียว

สูตร
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}

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

  • การลืมปรับมาตรฐาน (standardize) หรือทำให้เป็นปกติ (normalize) คุณลักษณะก่อนคำนวณระยะทาง ทำให้คุณลักษณะที่มีความแปรปรวนสูงมีอิทธิพลเหนือกว่า
  • การใช้ค่า k ค่าเดียวโดยไม่มีการวิเคราะห์ความไว (sensitivity analysis) แนวทางปฏิบัติที่ดีที่สุดคือการประเมินค่า k หลายค่า
  • การปฏิบัติต่อคะแนน LOF เสมือนเป็นความน่าจะเป็น — เป็นการวัดเชิงเปรียบเทียบที่ไม่มีการตีความเชิงความน่าจะเป็นที่แน่นอน
  • การเพิกเฉยต่อ curse of dimensionality ในข้อมูลมิติสูงและคาดหวังให้ LOF ทำงานได้โดยไม่ต้องมีการลดมิติเบื้องต้น
  • การตั้งเกณฑ์ LOF ตามอำเภอใจ (เช่น คะแนน > 1.5) โดยไม่ได้ตรวจสอบการกระจายตัวของคะแนนสำหรับชุดข้อมูลเฉพาะ

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

ฉันจะเลือกค่า k ที่เหมาะสมได้อย่างไร?

ไม่มีค่า k ที่เหมาะสมที่สุดสำหรับทุกกรณี แนวทางปฏิบัติทั่วไปคือการประเมินค่าในช่วงต่างๆ — โดยทั่วไปคือ 5 ถึง 50 — และตรวจสอบว่าการกระจายตัวของคะแนนและความผิดปกติที่ถูกระบุเปลี่ยนแปลงไปอย่างไร การวิเคราะห์ความไว (sensitivity analysis) ในช่วงค่า k ต่างๆ จะช่วยให้มั่นใจได้ว่าความผิดปกติที่ตรวจพบนั้นมีความทนทานต่อการเลือกค่า การมีความรู้เกี่ยวกับขนาดกลุ่มที่คาดหวังขั้นต่ำก็สามารถช่วยกำหนดขอบเขตล่างได้เช่นกัน

คะแนน LOF ที่ 1 เทียบกับ 3 หมายความว่าอย่างไร?

คะแนนที่ใกล้เคียง 1 หมายความว่าจุดนั้นมีความหนาแน่นเฉพาะที่ใกล้เคียงกับเพื่อนบ้าน และถือว่าเป็นจุดปกติ (inlier) คะแนนที่มากกว่า 1 อย่างมีนัยสำคัญ — ซึ่งมักตีความว่าสูงกว่า 1.5 หรือ 2 ขึ้นอยู่กับชุดข้อมูล — บ่งชี้ว่าละแวกใกล้เคียงของจุดนั้นเบาบางกว่าละแวกใกล้เคียงของเพื่อนบ้านอย่างมาก ไม่มีเกณฑ์ตัด (cutoff) สากล เกณฑ์ควรถูกเลือกโดยการตรวจสอบการกระจายตัวของคะแนน LOF สำหรับชุดข้อมูลเฉพาะ

LOF สามารถให้คะแนนจุดใหม่ที่ยังไม่เคยเห็นได้โดยไม่ต้องฝึกสอนใหม่หรือไม่?

LOF เป็นวิธีการแบบถ่ายทอด (transductive method): ต้องมีชุดข้อมูลฝึกสอนอยู่เพื่อคำนวณละแวกใกล้เคียงและความหนาแน่นสำหรับจุดใหม่ใดๆ ในการให้คะแนนการสังเกตการณ์ใหม่ ต้องเก็บชุดข้อมูลฝึกสอนไว้ และต้องแทรกจุดใหม่แต่ละจุดเพื่อคำนวณ k-neighborhood ใหม่เทียบกับจุดฝึกสอนที่เก็บไว้ การนำไปใช้บางอย่างมีฟังก์ชันนี้ แต่มีความแตกต่างพื้นฐานจากโมเดลแบบพาราเมตริก (parametric models) ที่เรียนรู้ฟังก์ชันการให้คะแนนที่กระชับ

LOF เปรียบเทียบกับ Isolation Forest สำหรับการตรวจจับความผิดปกติอย่างไร?

LOF ใช้การประมาณความหนาแน่นโดยอาศัยละแวกใกล้เคียงเฉพาะที่ และมีประสิทธิภาพดีกว่าเมื่อความผิดปกติรวมตัวกันในบริเวณที่เบาบางเฉพาะที่ของปริภูมิที่มีความหลากหลาย Isolation Forest ใช้การแบ่งพาร์ติชันแบบสุ่ม และมีแนวโน้มที่จะเร็วกว่าและปรับขนาดได้ดีกว่าสำหรับชุดข้อมูลขนาดใหญ่ สำหรับข้อมูลมิติสูงหรือข้อมูลขนาดใหญ่มาก Isolation Forest มักจะถูกเลือกใช้มากกว่า สำหรับข้อมูลมิติปานกลางที่มีความหนาแน่นแตกต่างกัน LOF มักจะให้การแยกแยะที่ละเอียดกว่า

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

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

  1. Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

    ISBN: 978-3-319-47577-6
    คัดลอกแล้ว
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    ISBN: 978-0-387-84857-0
    คัดลอกแล้ว