عامل الشذوذ المحلي (LOF)
- قدّمه
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- السنة
- 2000
- النوع
- Density-based anomaly detection (unsupervised)
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
عامل الشذوذ المحلي (LOF) هو خوارزمية غير خاضعة للإشراف للكشف عن الشذوذ تعتمد على الكثافة، قدمها Breunig و Kriegel و Ng و Sander في عام 2000. وهي تُسند لكل نقطة بيانات درجة شذوذ مستمرة تُقَيِّم مدى انعزال تلك النقطة بالنسبة لجوارها المحلي، مما يتيح اكتشاف الشذوذ الذي تفشل فيه الطرق الشاملة لأنها تندمج في تجمعات كثيفة في أماكن أخرى من الفضاء.
الفكرة الحدسية وراء الطريقة
تخيل خريطة مدينة حيث يعيش معظم الناس في مناطق حضرية كثيفة. منزل يقف بمفرده في الريف معزول بوضوح. لكن LOF يذهب أبعد من ذلك: يمكنه أيضًا تمييز منزل يقع في ضاحية متوسطة الكثافة عندما يكون جميع جيرانه المباشرين مكدسين في تجمع أكثر كثافة. بدلاً من السؤال 'هل هذه النقطة بعيدة عن كل شيء؟'، تسأل LOF 'هل حي هذه النقطة أكثر ندرة من أحياء جيرانها؟' النقطة التي يعيش فيها جيرانها جميعًا بشكل أكثر إحكامًا من النقطة نفسها تحصل على درجة LOF عالية - مما يشير إلى أنها شاذة محليًا حتى لو لم تكن في منطقة فارغة بشكل شامل.
التاريخ
تم تقديم LOF بواسطة Markus Breunig و Hans-Peter Kriegel و Raymond Ng و Jörg Sander في مؤتمر ACM SIGMOD 2000. وقد عالج قيودًا معترفًا بها في طرق الشذوذ الحالية - أنها اعتمدت على عتبات المسافة الشاملة وبالتالي خلطت بين الشواذ المحلية والنقاط العادية في المناطق الأقل كثافة. قدمت الورقة مفهوم الكثافة المحلية القابلة للوصول ودرجة LOF، والتي سرعان ما أصبحت مرجعًا أساسيًا في الكشف عن الشذوذ. وقد تم توسيعها منذ ذلك الحين من خلال متغيرات عديدة، بما في ذلك LoOP (احتمالات الشذوذ المحلي) و LOCI و COF، وهي مدرجة في مكتبات التعلم الآلي الرئيسية. الورقة البحثية لـ ACM SIGMOD 2000 تراكمت عليها آلاف الاستشهادات وتُعتبر واحدة من الأعمال الأساسية في استخراج البيانات المعتمد على الكثافة.
متى تُستخدم
LOF مناسب عندما يُتوقع حدوث الشذوذ في تجمعات ذات كثافة متغيرة وعندما تتجاهل عتبة المسافة الشاملة الشواذ المخفية في المناطق النادرة أو تميز بشكل خاطئ النقاط في التجمعات النادرة ولكن المتسقة بشكل شرعي. تعمل على أي فضاء ميزات مستمر مع مقياس مسافة ذي معنى ولا تتطلب أمثلة شاذة مصنفة (غير خاضعة للإشراف بالكامل). وهي تناسب تطبيقات مثل اكتشاف الاحتيال، واكتشاف التسلل الشبكي، ومراقبة جودة التصنيع، وفحص الشذوذ الطبي. الافتراضات الرئيسية هي أن النقاط الداخلية تشكل أحياء محلية متماسكة بشكل معقول وأن المسافات الزوجية ذات المغزى يمكن حسابها. يؤدي LOF أفضل أداء عندما يكون n في حدود العشرات إلى المئات المنخفضة؛ بالنسبة للبيانات عالية الأبعاد جدًا (لعنة الأبعاد) تصبح المسافات أقل تمييزًا ويوصى أولاً بتقليل الأبعاد أو اختيار الميزات.
الحدود والاعتبارات
- التعقيد الزمني التربيعي في التنفيذ الساذج يجعله بطيئًا على مجموعات البيانات الكبيرة بدون فهرسة الجار الأقرب التقريبية.
- حساس لاختيار k: k صغيرة جدًا تنتج درجات مشوشة؛ k كبيرة جدًا تطمس البنية المحلية.
- يتدهور الأداء في المساحات عالية الأبعاد جدًا بسبب لعنة الأبعاد.
- لا يتوسع بشكل طبيعي للبيانات المتدفقة أو عبر الإنترنت دون إعادة حساب.
- لا يوفر نموذجًا يمكن تطبيقه مباشرة لتسجيل نقاط جديدة دون الوصول إلى مجموعة التدريب.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يكتشف الشواذ المحليين في مجموعات البيانات ذات التجمعات ذات الكثافة المتغيرة، حيث تفشل الطرق الشاملة.
- ينتج درجة مستمرة وقابلة للتفسير بدلاً من تسمية ثنائية صارمة، مما يسمح باختيار عتبة مرن.
- غير خاضع للإشراف بالكامل: لا يلزم وجود بيانات شاذة مصنفة.
- قابل للتطبيق على أي فضاء ميزات مع مقياس مسافة قابل للحساب، بما في ذلك المسافات غير الإقليدية.
- قوي لمقياس الميزات الفردية عند حساب المسافات على بيانات موحدة.
التطبيقات
- اكتشاف الاحتيال في المعاملات المالية حيث يخلق النشاط الاحتيالي أنماطًا نادرة محليًا.
- اكتشاف التسلل الشبكي عن طريق تمييز سجلات حركة المرور التي يكون حيّها المحلي أكثر ندرة من محيطها.
- مراقبة جودة التصنيع لتحديد العناصر المعيبة في بيانات الإنتاج الغنية بالمستشعرات.
- فحص الشذوذ الطبي - اكتشاف ملفات تعريف المرضى غير العادية بالنسبة لمجموعات المرضى المماثلة.
- اكتشاف الشذوذ المكاني في البيانات الجغرافية والبيئية ذات الكثافة غير المتجانسة.
كيف يعمل
كيف يعمل
لكل نقطة p، تحسب الخوارزمية أولاً مسافة k: المسافة إلى الجار الأقرب رقم k للنقطة p. هذا يحدد مدى حي p المحلي. جميع النقاط ضمن تلك المسافة تشكل الحي المحلي N_k(p). اختيار k يتحكم في المقياس الذي يتم به تقييم المحلية - k الصغيرة تلتقط البنية المحلية الدقيقة، و k الأكبر تنعم عليها.
الصيغة
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pمسافة الوصول من p إلى جار o تُعرَّف بأنها الحد الأقصى لمسافة k للجار o والمسافة الإقليدية الفعلية (أو مقياس آخر) بين p و o. هذا التنعيم يمنع عدم الاستقرار عندما تكون نقطتان قريبتين جدًا من بعضهما البعض: فهو يستبدل المسافات الصغيرة بالبصمة الأوسع لحي o الخاص، مما يجعل تقديرات الكثافة أكثر قوة.
الصيغة
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}الكثافة المحلية القابلة للوصول للنقطة 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)|}الأخطاء الشائعة
- نسيان توحيد أو تطبيع الميزات قبل حساب المسافات، مما يتسبب في هيمنة الميزات ذات التباين العالي.
- استخدام قيمة واحدة لـ k دون تحليل الحساسية؛ أفضل ممارسة هي تقييم عدة قيم لـ k.
- معاملة درجة LOF كاحتمال - إنها مقياس نسبي بدون تفسير احتمالي ثابت.
- تجاهل لعنة الأبعاد في البيانات عالية الأبعاد وتوقع أن يعمل LOF بدون تقليل الأبعاد المسبق.
- تعيين عتبة LOF اعتباطية (على سبيل المثال، درجة > 1.5) دون فحص توزيع الدرجات لمجموعة البيانات المحددة.
الأسئلة الشائعة
كيف أختار القيمة المناسبة لـ k؟
لا توجد قيمة k مثلى عالميًا. الممارسة الشائعة هي تقييم نطاق من القيم - عادة من 5 إلى 50 - وفحص كيف يتغير توزيع الدرجات والشواذ المحددة. يمنح تحليل الحساسية عبر قيم k الثقة في أن الشواذ المكتشفة قوية بالنسبة للاختيار. يمكن أيضًا أن توجه معرفة المجال حول الحد الأدنى المتوقع لحجم التجمع الحد الأدنى.
ماذا تعني درجة LOF البالغة 1 مقابل 3؟
تشير درجة قريبة من 1 إلى أن النقطة لها نفس الكثافة المحلية تقريبًا مثل جيرانها وتعتبر نقطة داخلية. تشير درجة أكبر بكثير من 1 - غالبًا ما تُفسر على أنها أعلى من 1.5 أو 2 اعتمادًا على مجموعة البيانات - إلى أن حي النقطة أكثر ندرة بكثير من أحياء جيرانها. لا يوجد حد قاطع عالمي؛ يجب اختيار العتبة عن طريق فحص توزيع درجات LOF لمجموعة البيانات المحددة.
هل يمكن لـ LOF تسجيل نقاط جديدة غير مرئية دون إعادة التدريب؟
LOF هي طريقة استقرائية (transductive): تتطلب وجود مجموعة التدريب لحساب الأحياء والكثافات لأي نقطة جديدة. لتسجيل ملاحظات جديدة، يجب الاحتفاظ بمجموعة التدريب ويجب إدراج كل نقطة جديدة لإعادة حساب حي k الخاص بها مقابل نقاط التدريب المخزنة. تقدم بعض التطبيقات هذه الوظيفة، لكنها تختلف جوهريًا عن النماذج البارامترية التي تتعلم دالة تسجيل مدمجة.
كيف يقارن 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.
ردمك: 978-3-319-47577-6تم النسخ.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ردمك: 978-0-387-84857-0تم النسخ.