ปัจจัยค่าผิดปกติเฉพาะที่ (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) ได้อย่างยืดหยุ่น
- ไม่มีผู้สอนโดยสมบูรณ์: ไม่จำเป็นต้องมีข้อมูลความผิดปกติที่มีป้ายกำกับ
- สามารถนำไปใช้กับปริภูมิคุณลักษณะใดๆ ที่มีเมตริกวัดระยะทางที่สามารถคำนวณได้ รวมถึงระยะทางที่ไม่ใช่แบบยุคลิด
- ทนทานต่อมาตราส่วนของคุณลักษณะแต่ละรายการเมื่อคำนวณระยะทางบนข้อมูลที่ปรับมาตรฐานแล้ว
การประยุกต์ใช้
- การตรวจจับการฉ้อโกงในการทำธุรกรรมทางการเงิน ซึ่งกิจกรรมที่ฉ้อโกงสร้างรูปแบบที่เบาบางเฉพาะที่
- การตรวจจับการบุกรุกเครือข่ายโดยการระบุบันทึกการรับส่งข้อมูลที่มีละแวกใกล้เคียงเฉพาะที่เบาบางกว่าสภาพแวดล้อมโดยรอบ
- การควบคุมคุณภาพการผลิตเพื่อระบุรายการที่มีข้อบกพร่องในข้อมูลการผลิตที่มีเซ็นเซอร์จำนวนมาก
- การคัดกรองความผิดปกติทางการแพทย์ — การตรวจจับโปรไฟล์ผู้ป่วยที่ผิดปกติเมื่อเทียบกับกลุ่มผู้ป่วยที่คล้ายคลึงกัน
- การตรวจจับความผิดปกติเชิงพื้นที่ในข้อมูลทางภูมิศาสตร์และสิ่งแวดล้อมที่มีความหนาแน่นไม่สม่ำเสมอ
วิธีการทำงาน
วิธีการทำงาน
สำหรับแต่ละจุด 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ระยะห่างที่สามารถเข้าถึงได้ (reachability distance) จาก p ไปยังเพื่อนบ้าน o ถูกกำหนดให้เป็นค่าสูงสุดระหว่าง k-distance ของ o และระยะห่างจริงแบบยุคลิด (หรือเมตริกอื่น) ระหว่าง p และ o การปรับให้เรียบนี้จะป้องกันความไม่เสถียรเมื่อจุดสองจุดอยู่ใกล้กันมาก: มันจะแทนที่ระยะห่างที่เล็กมากด้วยขอบเขตที่กว้างกว่าของละแวกใกล้เคียงของ o เอง ทำให้การประมาณความหนาแน่นมีความทนทานมากขึ้น
สูตร
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}ความหนาแน่นที่สามารถเข้าถึงได้เฉพาะที่ (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}คะแนน 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 มักจะให้การแยกแยะที่ละเอียดกว่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้วAggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN: 978-3-319-47577-6คัดลอกแล้วHastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN: 978-0-387-84857-0คัดลอกแล้ว