Skip to content
بازگشت به نتایج جست‌وجو

عامل دورافتادگی محلی (LOF)

معرفی‌شده توسط
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
سال
2000
نوع
Density-based anomaly detection (unsupervised)

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

عامل دورافتادگی محلی (LOF) یک الگوریتم تشخیص ناهنجاری بدون نظارت و مبتنی بر چگالی است که توسط برونیگ، کریگل، نگ، و سندرز در سال ۲۰۰۰ معرفی شد. این الگوریتم به هر نقطه داده یک امتیاز پیوسته دورافتادگی اختصاص می‌دهد که میزان انزوای آن نقطه را نسبت به همسایگی محلی‌اش کمی‌سازی می‌کند. این قابلیت امکان تشخیص ناهنجاری‌هایی را فراهم می‌آورد که روش‌های سراسری از تشخیص آن‌ها باز می‌مانند، زیرا این ناهنجاری‌ها در خوشه‌های متراکم‌تر در سایر نقاط فضا ادغام می‌شوند.

شهود پشت روش

نقشه شهری را تصور کنید که بیشتر مردم در مناطق شهری متراکم زندگی می‌کنند. خانه‌ای که به تنهایی در حومه شهر قرار دارد، به وضوح منزوی است. اما LOF فراتر می‌رود: این الگوریتم می‌تواند خانه‌ای را نیز شناسایی کند که در یک حومه با تراکم متوسط قرار دارد، در حالی که تمام همسایگان بلافاصله‌اش در یک خوشه حتی متراکم‌تر فشرده شده‌اند. به جای پرسیدن «آیا این نقطه از همه چیز دور است؟»، LOF می‌پرسد «آیا همسایگی این نقطه بسیار پراکنده‌تر از همسایگی‌های همسایگان خودش است؟» نقطه‌ای که همسایگانش بسیار نزدیک‌تر از خود نقطه به هم زندگی می‌کنند، امتیاز LOF بالایی دریافت می‌کند — که نشان می‌دهد این نقطه یک دورافتاده محلی است، حتی اگر به صورت سراسری در یک منطقه خالی نباشد.

تاریخ

LOF توسط مارکوس برونیگ، هانس-پیتر کریگل، ریموند نگ، و یورگ سندر در کنفرانس ACM SIGMOD 2000 معرفی شد. این روش به یک محدودیت شناخته شده در روش‌های موجود تشخیص دورافتادگی — که بر آستانه‌های فاصله سراسری تکیه داشتند و بنابراین ناهنجاری‌های محلی را با نقاط عادی در مناطق کم‌تراکم‌تر اشتباه می‌گرفتند — پرداخت. این مقاله مفهوم چگالی دسترسی‌پذیری محلی و امتیاز LOF را معرفی کرد که به سرعت به یک مرجع اساسی در تشخیص ناهنجاری تبدیل شد. از آن زمان تاکنون، این روش با انواع متعددی از جمله LoOP (احتمالات دورافتادگی محلی)، LOCI، و COF گسترش یافته و در کتابخانه‌های اصلی یادگیری ماشین گنجانده شده است. مقاله ACM SIGMOD 2000 هزاران ارجاع جمع‌آوری کرده و به عنوان یکی از کارهای بنیادی در داده‌کاوی مبتنی بر چگالی شناخته می‌شود.

چه زمانی استفاده شود

LOF زمانی مناسب است که انتظار می‌رود ناهنجاری‌ها در خوشه‌هایی با چگالی‌های متفاوت رخ دهند و زمانی که یک آستانه فاصله سراسری یا ناهنجاری‌های پنهان در مناطق پراکنده را از دست می‌دهد یا نقاط را در خوشه‌هایی که به طور مشروع پراکنده اما سازگار هستند، به اشتباه شناسایی می‌کند. این روش بر روی هر فضای ویژگی پیوسته با یک معیار فاصله معنی‌دار کار می‌کند و نیازی به نمونه‌های ناهنجاری برچسب‌گذاری شده ندارد (کاملاً بدون نظارت). برای کاربردهایی مانند تشخیص تقلب، تشخیص نفوذ شبکه، کنترل کیفیت تولید و غربالگری ناهنجاری‌های پزشکی مناسب است. فرضیات اصلی این است که نقاط داخلی، همسایگی‌های محلی نسبتاً منسجمی را تشکیل می‌دهند و فواصل زوجی معنی‌دار قابل محاسبه هستند. LOF بهترین عملکرد را زمانی دارد که n حداقل در ده‌ها تا چند صد باشد؛ برای داده‌های با ابعاد بسیار بالا (نفرین ابعاد)، فواصل کمتر تمایزگذار می‌شوند و کاهش ابعاد یا انتخاب ویژگی ابتدا توصیه می‌شود.

محدودیت‌ها و ملاحظات

  • پیچیدگی زمانی درجه دوم در پیاده‌سازی ساده، آن را در مجموعه‌داده‌های بزرگ بدون نمایه‌سازی تقریبی نزدیکترین همسایه کند می‌کند.
  • حساس به انتخاب k: k بسیار کوچک امتیازات نویزدار تولید می‌کند؛ k بسیار بزرگ ساختار محلی را محو می‌کند.
  • عملکرد در فضاهای با ابعاد بسیار بالا به دلیل نفرین ابعاد کاهش می‌یابد.
  • بدون محاسبه مجدد، به طور طبیعی به داده‌های جریانی یا آنلاین مقیاس‌پذیر نیست.
  • مدلی ارائه نمی‌دهد که بتوان آن را مستقیماً برای امتیازدهی به نقاط جدید بدون دسترسی به مجموعه آموزشی به کار برد.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • ناهنجاری‌های محلی را در مجموعه‌داده‌ها با خوشه‌هایی با چگالی‌های متفاوت، که روش‌های سراسری در آن شکست می‌خورند، شناسایی می‌کند.
  • به جای یک برچسب باینری سخت، یک امتیاز پیوسته و قابل تفسیر تولید می‌کند که امکان انتخاب آستانه انعطاف‌پذیر را فراهم می‌آورد.
  • کاملاً بدون نظارت: نیازی به داده‌های ناهنجاری برچسب‌گذاری شده نیست.
  • قابل اعمال برای هر فضای ویژگی با یک معیار فاصله قابل محاسبه، از جمله فواصل غیر اقلیدسی.
  • در برابر مقیاس ویژگی‌های فردی مقاوم است، زمانی که فواصل بر روی داده‌های استاندارد شده محاسبه می‌شوند.

کاربردها

  • تشخیص تقلب در تراکنش‌های مالی که فعالیت‌های متقلبانه الگوهای محلی پراکنده ایجاد می‌کنند.
  • تشخیص نفوذ شبکه با علامت‌گذاری رکوردهای ترافیکی که همسایگی محلی آنها بسیار پراکنده‌تر از محیط اطرافشان است.
  • کنترل کیفیت تولید برای شناسایی اقلام معیوب در داده‌های تولیدی غنی از حسگر.
  • غربالگری ناهنجاری‌های پزشکی — تشخیص پروفایل‌های غیرعادی بیماران نسبت به گروه‌های بیماران مشابه.
  • تشخیص ناهنجاری فضایی در داده‌های جغرافیایی و محیطی با چگالی ناهمگن.

چگونه کار می‌کند

چگونه کار می‌کند

1

برای هر نقطه p، الگوریتم ابتدا فاصله k را محاسبه می‌کند: فاصله تا k-امین نزدیکترین همسایه p. این کار محدوده همسایگی محلی N_k(p) را تعریف می‌کند. تمام نقاط در این فاصله، همسایگی k را تشکیل می‌دهند. انتخاب k مقیاسی را کنترل می‌کند که در آن محلیت ارزیابی می‌شود — k کوچک ساختار محلی دقیق را ثبت می‌کند، k بزرگتر آن را هموار می‌کند.

فرمول
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

فاصله دسترسی‌پذیری از p به یک همسایه o به عنوان حداکثر فاصله k از o و فاصله اقلیدسی (یا سایر معیارهای متریک) واقعی بین p و o تعریف می‌شود. این هموارسازی از ناپایداری جلوگیری می‌کند، زمانی که دو نقطه بسیار به هم نزدیک هستند: این روش فواصل بسیار کوچک را با ردپای گسترده‌تر همسایگی خود o جایگزین می‌کند و تخمین‌های چگالی را قوی‌تر می‌سازد.

فرمول
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

چگالی دسترسی‌پذیری محلی 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 است. اگر lrd همه همسایگان p به طور قابل توجهی بالاتر از lrd خود p باشد — به این معنی که آنها در زیرمناطق متراکم‌تری زندگی می‌کنند — نسبت از ۱ فراتر می‌رود، که نشان می‌دهد p یک دورافتاده محلی است. امتیازی نزدیک به ۱ نشان می‌دهد که p تقریباً همان چگالی محیط اطراف خود را دارد. امتیازات بسیار بیشتر از ۱ نقاط به طور فزاینده‌ای ناهنجار را نشان می‌دهند. این مقایسه آگاهانه از محلیت چیزی است که 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 بهینه جهانی وجود ندارد. روش معمول این است که طیفی از مقادیر — معمولاً ۵ تا ۵۰ — را ارزیابی کرده و نحوه تغییر توزیع امتیاز و ناهنجاری‌های شناسایی شده را بررسی کنید. تحلیل حساسیت در طول مقادیر k اطمینان می‌دهد که ناهنجاری‌های شناسایی شده نسبت به انتخاب مقاوم هستند. دانش دامنه در مورد حداقل اندازه خوشه مورد انتظار نیز می‌تواند راهنمای حد پایین باشد.

امتیاز LOF ۱ در مقابل ۳ به چه معناست؟

امتیاز نزدیک به ۱ به این معنی است که نقطه تقریباً همان چگالی محلی همسایگان خود را دارد و یک نقطه داخلی محسوب می‌شود. امتیاز به طور قابل توجهی بیشتر از ۱ — که اغلب بسته به مجموعه داده به عنوان بالای ۱.۵ یا ۲ تفسیر می‌شود — نشان می‌دهد که همسایگی نقطه بسیار پراکنده‌تر از همسایگی‌های همسایگان آن است. هیچ برش جهانی وجود ندارد؛ آستانه باید با بررسی توزیع امتیازات LOF برای مجموعه داده خاص انتخاب شود.

آیا LOF می‌تواند نقاط جدید و دیده نشده را بدون آموزش مجدد امتیازدهی کند؟

LOF یک روش استنتاجی است: برای محاسبه همسایگی‌ها و چگالی‌ها برای هر نقطه جدید، نیاز است که مجموعه آموزشی موجود باشد. برای امتیازدهی به مشاهدات جدید، مجموعه آموزشی باید حفظ شود و هر نقطه جدید باید برای محاسبه مجدد k-همسایگی آن در برابر نقاط آموزشی ذخیره شده، وارد شود. برخی از پیاده‌سازی‌ها این قابلیت را ارائه می‌دهند، اما این روش اساساً با مدل‌های پارامتری که یک تابع امتیازدهی فشرده را یاد می‌گیرند، متفاوت است.

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.

    شابک: 978-3-319-47577-6
    کپی شد.
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    شابک: 978-0-387-84857-0
    کپی شد.