عامل الشذوذ المحلي

في مجال الكشف عن الحالات الشاذة ، يُعد عامل الشذوذ المحلي ( LOF ) خوارزمية اقترحها ماركوس إم. برونيج، وهانز-بيتر كريجل ، وريموند تي. نج، ويورج ساندر في عام 2000 لإيجاد نقاط البيانات الشاذة عن طريق قياس الانحراف المحلي لنقطة بيانات معينة بالنسبة لجيرانها. ^{[ 1 ]}

تشترك خوارزمية LOF في بعض المفاهيم مع خوارزميتي DBSCAN و OPTICS مثل مفهومي "مسافة النواة" و"مسافة الوصول"، واللذان يستخدمان لتقدير الكثافة المحلية. ^{[ 2 ]}

يعتمد عامل الشذوذ المحلي على مفهوم الكثافة المحلية، حيث تُحدد المحلية من خلال أقرب k جار، وتُستخدم المسافة بينهم لتقدير الكثافة. وبمقارنة الكثافة المحلية لجسم ما بالكثافات المحلية لجيرانه، يمكن تحديد المناطق ذات الكثافة المتشابهة، والنقاط ذات الكثافة الأقل بكثير من جيرانها. وتُعتبر هذه النقاط شذوذًا .

تُقدَّر الكثافة المحلية بالمسافة النموذجية التي يمكن عندها الوصول إلى نقطة ما من جيرانها. يُعد تعريف "مسافة الوصول" المستخدم في خوارزمية LOF مقياسًا إضافيًا لإنتاج نتائج أكثر استقرارًا داخل المجموعات. وتتضمن "مسافة الوصول" المستخدمة في خوارزمية LOF بعض التفاصيل الدقيقة التي غالبًا ما تُعتبر غير صحيحة في المصادر الثانوية، مثل كتاب إيثم ألبيدين. ^{[ 3 ]}

يترك${\displaystyle k{\text{-distance}}(A)}$لنفترض أن المسافة بين الجسم A وجاره الأقرب رقم k هي . لاحظ أن مجموعة الجيران الأقرب k تشمل جميع الأجسام على هذه المسافة، والتي قد يزيد عددها عن k جسم في حالة التعادل . نرمز إلى مجموعة الجيران الأقرب k بالرمز .${\displaystyle N_{k}(A)}$.

تُستخدم هذه المسافة لتحديد ما يسمى بمسافة الوصول :

$${\displaystyle {\text{مسافة الوصول-المسافة}}_{k}(A,B)=\max\{k{\text{المسافة}}(B),d(A,B)\}}$$

بعبارة أخرى، مسافة الوصول لجسم أ من جسم ب هي المسافة الحقيقية بين الجسمين، ولكن على الأقل${\displaystyle k{\text{-distance}}}$من B. تُعتبر الكائنات التي تنتمي إلى أقرب k جار لـ B (أي "جوهر" B ، انظر تحليل التجميع DBSCAN ) متساوية البعد. والسبب في ذلك هو تقليل التقلبات الإحصائية بين جميع النقاط A القريبة من B ، حيث يؤدي زيادة قيمة k إلى زيادة تأثير التنعيم. ^{[ 1 ]} لاحظ أن هذا ليس بُعدًا بالمعنى الرياضي، لأنه غير متناظر. (على الرغم من أنه من الأخطاء الشائعة ^{[ 4 ]} استخدام دائمًا${\displaystyle k{\text{-distance}}(A)}$وهذا ينتج عنه طريقة مختلفة قليلاً، يشار إليها باسم Simplified-LOF ^{[ 4 ]} )

تُعرَّف كثافة إمكانية الوصول المحلية للكائن A بواسطة

${\displaystyle {\text{lrd}}_{k}(A):={\frac {|N_{k}(A)|}{\sum _{B\in N_{k}(A)}{\text{reachability-distance}}_{k}(A,B)}}}$

وهو مقلوب متوسط ​​مسافة الوصول للكائن A من جيرانه. لاحظ أنه ليس متوسط ​​مسافة الوصول للجيران من A (والذي سيكون بحكم التعريف هو${\displaystyle k{\text{-distance}}(A)}$)، ولكن المسافة التي يمكن عندها "الوصول" إلى النقطة A من جيرانها. ومع وجود نقاط مكررة، يمكن أن تصبح هذه القيمة لانهائية.

ثم تتم مقارنة كثافات إمكانية الوصول المحلية مع كثافات الجيران باستخدام

${\displaystyle {\text{LOF}}_{k}(A):={\frac {1}{|N_{k}(A)|}}\sum _{B\in N_{k}(A)}{\frac {{\text{lrd}}_{k}(B)}{{\text{lrd}}_{k}(A)}}={\frac {1}{|N_{k}(A)|\cdot {\text{lrd}}_{k}(A)}}\sum _{B\in N_{k}(A)}{\text{lrd}}_{k}(B)}$

وهي متوسط ​​كثافة الوصول المحلي للجيران مقسومًا على كثافة الوصول المحلي للكائن نفسه. تشير قيمة تقارب 1 إلى أن الكائن مماثل لجيرانه (وبالتالي ليس قيمة شاذة). تشير قيمة أقل من 1 إلى منطقة ذات كثافة أعلى (والتي ستكون قيمة داخلية)، بينما تشير القيم الأكبر بكثير من 1 إلى قيم شاذة.

${\displaystyle {\text{LOF}}_{k}(A)\sim 1}$يعني كثافة مماثلة للجيران،

${\displaystyle {\text{LOF}}_{k}(A)<1}$يعني كثافة أعلى من المناطق المجاورة (داخلية)،

${\displaystyle {\text{LOF}}_{k}(A)>1}$يعني كثافة أقل من الجيران (قيمة شاذة).

بفضل منهجها المحلي، تستطيع خوارزمية LOF تحديد القيم الشاذة في مجموعة البيانات، والتي لا تُعتبر شاذة في مناطق أخرى من نفس المجموعة. على سبيل المثال، تُعتبر نقطة تقع على مسافة "قصيرة" من مجموعة كثيفة للغاية قيمة شاذة، بينما قد تُظهر نقطة داخل مجموعة متفرقة مسافات مماثلة من جيرانها.

على الرغم من أن الحدس الهندسي لخوارزمية LOF ينطبق فقط على فضاءات المتجهات منخفضة الأبعاد، إلا أنه يمكن تطبيق الخوارزمية في أي سياق يمكن فيه تعريف دالة عدم التشابه. وقد أثبتت التجارب فعاليتها العالية في العديد من الإعدادات، وغالبًا ما تتفوق على المنافسين، على سبيل المثال في كشف اختراقات الشبكات ^{[ 5 ]} وعلى بيانات التصنيف المعيارية المعالجة ^{[ 6 ] .}

يمكن تعميم عائلة طرق LOF بسهولة وتطبيقها على مشاكل أخرى متنوعة، مثل اكتشاف القيم الشاذة في البيانات الجغرافية أو تدفقات الفيديو أو شبكات التأليف. ^{[ 4 ]}

القيم الناتجة هي قيم قسمة يصعب تفسيرها. تشير القيمة 1 أو أقل إلى نقطة داخلية واضحة، ولكن لا توجد قاعدة واضحة لتحديد متى تكون النقطة شاذة. في مجموعة بيانات واحدة، قد تكون القيمة 1.1 شاذة بالفعل، بينما في مجموعة بيانات أخرى ومع معلمات مختلفة (مع تقلبات محلية قوية)، قد تظل القيمة 2 نقطة داخلية. يمكن أن تحدث هذه الاختلافات أيضًا داخل مجموعة البيانات الواحدة بسبب موضعية الطريقة. توجد امتدادات لـ LOF تحاول تحسينها في هذه الجوانب:

• تعتمد خوارزمية تجميع الميزات للكشف عن القيم الشاذة ^{[ 7 ]} على تطبيق خوارزمية LOF على إسقاطات متعددة، ثم تجمع النتائج لتحسين جودة الكشف في الأبعاد العالية. تُعد هذه الخوارزمية أول نهج للتعلم الجماعي في الكشف عن القيم الشاذة، وللاطلاع على متغيرات أخرى، يُرجى مراجعة المرجع ^{[ 8 ]} .
• تُعدّ طريقة احتمالية القيم الشاذة المحلية (LoOP) ^{[ 9 ]} طريقةً مُشتقةً من طريقة LOF، ولكنها تستخدم إحصاءات محلية غير مكلفة لتقليل حساسيتها لاختيار المعامل k . بالإضافة إلى ذلك، يتم تحجيم القيم الناتجة إلى نطاق يتراوح بين 0 و1 .
• يقترح تفسير وتوحيد درجات القيم الشاذة ^{[ 10 ]} توحيد درجات القيم الشاذة LOF إلى الفترة [0:1] باستخدام القياس الإحصائي لزيادة قابلية الاستخدام ويمكن اعتبارها نسخة محسنة من أفكار LoOP.
• يقترح ^{[ 11 ]} طرقًا لقياس التشابه والتنوع في طرق بناء مجموعات الكشف عن القيم الشاذة المتقدمة باستخدام متغيرات LOF وخوارزميات أخرى وتحسين نهج تجميع الميزات الذي تمت مناقشته أعلاه.
• إعادة النظر في اكتشاف القيم الشاذة المحلية: نظرة معممة على مفهوم المحلية مع تطبيقات لاكتشاف القيم الشاذة في البيانات المكانية والفيديوهات والشبكات ^{[ 4 ]،} حيث يناقش هذا البحث النمط العام في مختلف طرق اكتشاف القيم الشاذة المحلية (بما في ذلك، على سبيل المثال، LOF، ونسخة مبسطة من LOF، وLoOP)، ويستخلص منه إطارًا عامًا. ثم يُطبق هذا الإطار، على سبيل المثال، لاكتشاف القيم الشاذة في البيانات الجغرافية، وتدفقات الفيديو، وشبكات التأليف.