เกริ่นนำ
ใน Part ที่ 4 นี้ขอกล่าวถึงเทคนิคอีกวิธีหนึ่งที่เรียกว่า Local Outlier Factor หรือเรียกสั้นๆว่า LOF ในบทความจะกล่าวถึง LOF คืออะไร แนวคิดของ LOF วิธีการคำนวณ รวมถึง วิธีการใช้งาน และสุดท้ายคือตัวอย่างการใช้งาน ทั้งนี้มาตัวอย่าง Colab ให้ดูด้วยครับ
Local Outlier Factor (LOF)
เป็น Algorithm ที่ถูกคิดค้นขึ้นเพื่อวัดค่าความเป็น Outlier ได้ (Anomaly) โดยให้คะแนน (Score) ความเป็น Outlier ในทุกๆจุดโดยดูความหนาแน่นเป็นหลักและสามารถคัดแยกจุดที่มีความหนาแน่นสูง และจุดที่มีความหนาแน่นต่ำออกจากกันดังรูปด้านล่าง
Cr:https://scikit-learn.org/0.19/auto_examples/neighbors/plot_lof.html
แนวทางนี้มีแนวคิดหรือไอเดียมาจาก DBScan ซึ่ง DBScan จะดูจุดที่ไม่เกาะกลุ่ม หรือ กลุ่มที่มีสมาชิกน้อยๆเป็นหลัก LOF จะลงรายละเอียดขึ้นโดย ทุกๆจุดจะมีคะแนนเป็นของตัวเอง ส่วน DBScan เน้นไปที่ระยะทาง (Distance Base) แต่ LOF นั้นเน้นไปที่ความหนาแน่น เป็นหลัก (Density Base)
ปัจจัยที่ีใช้ในการคำนวณมีเพียงค่า k หรือจำนวนเพื่อนบ้านที่ใกล้ที่สุด k จุด ดังรูปต่อไปนี้คือการกำหนดค่า k=3 โดยจุด A เป็นศูนย์กลาง และ C,B,? เป็นสมาชิก แต่ D ไม่ได้เป็นสมาชิกเพราะว่าเกิดที่ค่า k กำหนดไว้
Cr:https://en.wikipedia.org/wiki/Local_outlier_factor
จากรูปด้านบนเราจะพบว่าจุด B เป็นระยะทางที่ไกลที่สุดของทั้ง 3 จุดเราจะใช้ค่าระยะทางของจุด B เป็นตัวคำนวณหา Density ต่อไป ซึ่งรายละเอียดอยู่ใน ส่วนการคำนวณ LOF ด้านล่างครับ
การหาค่าความเป็น Outlier
หลังจากคำนวณเรียบร้อยแล้วเราจะได้ค่า LOF ซึ่งเราจะประเมินค่าออกมาดังนี้
LOF(k) > 1 แสดงว่าเป็น Outlier หรือผิดปรกติ
LOF(k) ~ 1 แสดงว่ามีความคล้ายคลึงกับเพื่อนบ้าน
LOF(k) < 1 แสดงว่าปรกติ
*ข้อมูลจาก wiki pedia
เพียงเท่านี้ก็สามารถนำ LOF ไปใช้งานได้แล้วครับ สามารถดู Code การใช้งานได้ในส่วนของการประยุกตร์ครับ
การประยุกตร์ใช้งาน
เราสามารถใช้ Technique นี้ในการหา Outlier ของ CPU , Disk I/O , Network Traffic In/Out หรือหากเป็นงานอุตสาหกรรม เราสามารถใช้หา ความผิดปรกติของเครื่องจักร เช่นอุณหภูมิ ความร้อน ความสั่นสะเทือนหรือเสียง เป็นต้น
ในตัวอย่างนี้จะเป็นการค่า LOF ให้กับ CPU จาก Data Numenta Anomaly Benchmark (NAB)
โดยเรานำ CPU ของวันที่ 4 และวันที่ 5 มาเปรียบเทียบกัน คล้ายกับ บทความที่แล้ว
ข้อมูล Timeseries เปรียบเทียบค่า CPU Load average ของวันที่ 4 และวันที่ 5
หลังจากใช้ LOF จะทำการแยกค่า Outlier ออกมาพบจุดที่เป็น Outlier 9 จุดและเมื่อเรา plot ด้วย scatter โดยให้ LOF Score เป็นรัศมี จะเห็นความเป็น Outlier ได้ชัดเจนขึ้น
หลังจากนำจุดที่เป็น Outlier ทั้ง 9 จุด มา Plot ลง Graph ในมุมมองของ Time Series ได้จากรูปด้านล่าง
จะเห็นได้ว่าช่วงที่ CPU เริ่มเพี้ยนหรือไม่สอดคล้องกันเช่นบางวันแรก CPU ขึ้นสูงในเวลาเดียวกัน CPU ต่ำจะเป็นจุดที่เป็น Anomaly เช่นจุดที่ 152 พบ 2 จุดที่ผิดปรกติ เป็นต้น
รายละเอียดการหา Anomaly Detection ด้วย LOF สามารถดูได้จาก link ด้านล่างครับ
colab https://colab.research.google.com/drive/1OEX9LCoH4qwTM8b_QTnncQPVsyTqiNr-
การคำนวณค่า LOF (Optional)
ใน Part การคำนวณเป็นส่วนเสริม สำหรับผู้สนใจการคำนวณว่า LOF คำนวนอย่างไรครับ หากไม่สนใจก็สามารถข้ามได้เลยครับ โดยมี 3 Step ใหญ่ๆดังนี้
1. หาค่า Reachability-distance โดยค่านี้คือค่าระยะที่ห่างไกลที่สุดที่ทำให้พบเพื่อน k คน เขียนเป็นสมการได้ดังนี้
2. หาค่า Local Reachability Density (lrd) โดยนำค่า Distance จากข้อ 1. มาหา Density หรือค่าความหนาแน่นได้จากสูตร
ทั้งนี้ชวนสังเกตว่าค่า Density = คือมวล/พื้นที่ ในที่นี้ มวลคือค่า k นั่นก็คือ |N(A)| และพื้นที่คือ 2πr ในที่นี้ 2π เป็นค่าคงที่เราสามารถตัดออกได้เนื่องจากเราไม่ได้นำค่ามวลมาใช้งานจริง(เราสนใจที่ Ratio) เรา จึงเหลือ r นั่นก็คือ reachability-distance นั่นเอง โดยยิ่งค่า lrd ยิ่งสูงแสดงว่ามีความหนาแน่นสูง นิ่งค่า lrd ต่ำแสดงว่ามีความหนาแน่นต่ำ
3. หาค่า Local Outlier Factor (LOF) คือการนำผลรวม Density ของเพื่อนบ้าน (lrd(B)) ทั้งหมด k คน มาเทียบกับ Density ของเรา (lrd(A)) โดยนำมาหารกันนั่นเอง และหารด้าย |N(A)| ซึ่งนั่นก็คืือ k ผลที่ได้จะออกมาเป็นค่าเฉลี่ยซึ่งได้จากสูตร
ชวนสังเกตว่าหากค่า
- Density ของเพื่อนบ้าน (lrd(B)) มากกว่า Density ของเรา (lrd(A)) เราจะตีความหมายว่า ความหนาแน่นของเราน้อยกว่าเพื่อนบ้านแสดงว่าเรามีโอกาสเป็น Outlier เมื่อนำมาหารกัน (lrd(B))/(lrd(A)) ค่าจะมากกว่า 1
- Density ของเพื่อนบ้าน (lrd(B)) น้อยกว่า Density ของเรา (lrd(A)) เราจะตีความหมายว่า ความหนาแน่นของเรามากกว่าเพื่อนบ้านแสดงว่าเรามีโอกาสเป็น Inlier (Normaly) เมื่อนำมาหารกัน (lrd(B))/(lrd(A)) ค่าจะน้อยกว่า 1
วงเล็กมีความหนาแน่นมากกว่าวงใหญ่ ซึ่งอธิบายได้ว่ายิ่งวงใหญ่มีโอกาสเป็น Outlier สูง
ตัวอย่างการคำนวณด้วยมือ (Optional)
สมมุติว่าเรามี Data อยู่ 4 จุดคือ [0,0] [0,1] [1,1] [3,0] เราสามารถ Plot ได้ดังรูปต่อไปนี้
ในที่นี้เราคำนวณระยะทางด้วย Manhattan Distance (ช่วยให้คำนวณได้ง่าย) เราจะพบว่า
dist(a,b) = 1
dist(a,c) = 2
dist(a,d) = 3
dist(b,c) = 1
dist(b,d) = 4
dist(c,d) = 3
ในที่นี้เรากำหนดค่า k = 2 และทำการหาระยะที่ไกลที่สุดของแต่ละ node เมื่อ k=2 เราจะได้ว่า
dist(a) = 2 ก็คือระยะทางจาก a-c เป็นระยะทางที่ไกลที่สุด
dist(b) = 1 ก็คือระยะทางจาก b-a,b-c เป็นระยะทางที่ไกลที่สุดเท่ากัน
dist(c) = 2 ก็คือระยะทางจาก c-a เป็นระยะทางที่ไกลที่สุด
dist(d) = 3 ก็คือระยะทางจาก d-a,d-c เป็นระยะทางที่ไกลที่สุดเท่ากัน
ทำการหาค่า Reachability Density(b<-a) = max(dist(b),dist(b,a)) ขอใช้ชื่อย่อว่า rd
rd(b<-a) = max(1,1) = 1
rd(a<-b) = max(2,1) = 2
rd(c<-a) = max(2,2) = 2
rd(d<-a) = max(3,3) = 3
rd(c<-b) = max(2,1) = 2
rd(d<-b) = max(3,4) = 4
rd(c<-d) = max(3,3) = 3
คำนวณหา Local Reachability Density (lrd) = |N(a)|/(ผลรวม Reachability Density ของสมาชิก)
lrd(a) = |N(a)| /(rd(c,a)+rd(b,a)) = 2/(2+1) = 0.667
lrd(b) = |N(b)| /(rd(a,b)+rd(c,b)) = 2/(2+2) = 0.5
lrd(c) = |N(c)| /(rd(b,c)+rd(a,c)) = 2/(1+2) = 0.667
lrd(d) = |N(d)| /(rd(c,d)+rd(a,d)) = 2/(3+3) = 0.333
คำนวณหาค่า LOF
LOF(a) = (lrd(c)+lrd(b))/lrd(a)/|N(a)| = (0.667+0.5)/0.667/2 = 0.875
LOF(b) = (lrd(c)+lrd(a))/lrd(b)/|N(b)| = (0.667+0.667)/0.5/2 = 1.334
LOF(c) = (lrd(a)+lrd(b))/lrd(c)/|N(c)| = (0.667+0.5)/0.667/2 = 0.875
LOF(d) = (lrd(a)+lrd(c))/lrd(d)/|N(d)| = (0.667+0.667)/0.333/2 = 2
พบว่า ที่จุด d มีความเป็น Outlier สูงที่สุดคือเท่ากับ 2 และเมื่อเรานำมา plot ด้วย scatter และให้รัศมีคือเป็นค่า lof จะพบว่าที่จุดd จะเป็นวงใหญ่ที่สุด
ปกิณกะของ Sklearn library
จากที่กล่าวมาทั้งหมด Sklearn ซึ่งเป็น Library ชอง Python มี Library ที่สามารถนำมาใช้งานได้เลยชื่อว่า sklearn.neighbors.LocalOutlierFactor สิ่งที่เห็นว่าในสมการมีความแตกต่างกันอยู่บ้างจึงได้ทำการวิเคราะห์ดูโดยมีสิ่งที่แตกต่างกันดังนี้
- ค่า local reachable density ของ Sklearn จะเท่ากับ 1 / (np.mean(Reachabilithy-Distance) + 1e-10) โดย 1e-10 ใช้ป้องกัน Division by Zero ซึ่ง Sklearn นำค่า |N(a)| ออกไป(ไม่ได้ใช้) แต่ถ้ามองในมุมของ Ratio ก็ยังคำนวณได้ผลไม่ต่างกัน
- ค่า LOF ของ Sklearn ใช้ค่าที่เรียกว่า negative_outlier_factor_ แทน LOF เมื่อดูจาก Source ค่านี้เพียงนำค่า local reachable density ของสมาชิกทั้งหมดมาหา AVG แล้วคูณด้วย -1 เท่านั้น
- ค่า contamination ใน Sklearn คือค่า Percentile ของ data ทั้งหมดหากกำหนด 0.1 หมายถึง data 10% ของ data ทั้งหมด เป็น Threshold กำหนดว่าเป็น Outlier ซึ่งมีค่าได้ตั้งแต่ 0-0.5
Conclusion
จะเห็นว่า Local Outlier Factor นั้นใช้เพียงปัจจัยเดียวเท่านั้นในการหา Outlier โดยดูความหนาแน่นของตัวเองและเทียบความหนาแน่นของเพื่อนบ้านหากความหนาแน่นของเรามีค่าต่ำกว่าก็มีโอกาสเป็น Outlier และนี่คือทั้งหมดของ Local Outlier Factor หวังว่าจะเป็นประโยชน์ในการนำไปวิเคราะห์ข้อมูลสำหรับท่านผู้อ่านทุกท่าน ขอบคุณครับ
Reference
- https://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf
- https://en.wikipedia.org/wiki/Local_outlier_factor
- http://www.cse.ust.hk/~leichen/courses/comp5331/lectures/LOF_Example.pdf
- https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LocalOutlierFactor.html
- https://slideplayer.com/slide/7945662/
- http://courses.washington.edu/css581/lecture_slides/18_anomaly_detection.pdf
Change Log
- 11 Mar 2020 Update ตัวอย่างการคำนวณด้วยมือ และเพิ่ม scatter บอก Score ด้วยรัศมี