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

در قسمت پنجم از مجموعه “گذر به مدیریت داده و مدیریت محصول” قصد داریم کمی انجام دهیم. علم داده بیایید عمیق تر کاوش کنیم و با یک الگوریتم نسبتا جدید و کاربردی برای شناسایی داده های منسوخ و غیرعادی آشنا شویم. با توسعه فناوری اطلاعات، دامنه فعالیت های مدیران محصول متنوع تر می شود. امروزه در اکثر شرکت ها نرم افزار و تجزیه و تحلیل داده ها به خصوص این محصولات انجام می شود پایان علم موقعیت مدیر محصول AI / ML و مدیر محصول داده ایجاد شده است و این افراد مستقیماً فرآیندهای یادگیری ماشین و هوش مصنوعی را در توسعه محصول نظارت می کنند.

در تجزیه و تحلیل آماری، شناسایی ناهنجاری ها و یافتن انحرافات بسیار مهم است. در برخی موارد وجود این نقاط باعث ایجاد خطا در طراحی مدل آماری می شود و دقت پیش بینی را به میزان قابل توجهی کاهش می دهد. مواردی نیز وجود دارد که این نقاط نشان دهنده وقوع نفوذ و فعالیت غیرعادی کاربر است که برای افزایش امنیت سیستم قابل بررسی است.

در آمار، ناهنجاری یک مشاهده، رویداد یا مقدار غیرمعمول است که تفاوت ها و انحرافات قابل توجهی از سایر مقادیر دارد و رفتار متفاوتی نسبت به جاهای دیگر دارد. به عنوان مثال، در میان توپ های غمگین، توپ شانس یک منظره غیرعادی است.

01 قطب آی تی

نقاط غیرعادی می توانند معانی مختلفی داشته باشند. به عنوان مثال، نمودار زیر ترافیک ورودی وب سایت را نشان می دهد که بر اساس تعداد درخواست ها در یک بازه زمانی سه ساعته در یک دوره یک ماهه نمایش داده می شود.

02 قطب آی تی

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

بدیهی است که تشخیص ناهنجاری ها و انحرافات از تمامی مجموعه داده ها چندان آسان نیست و در موارد خاص هنگام کار با مجموعه داده های بزرگ، شناسایی انحرافات کاری بسیار پیچیده است و نیازمند استفاده از الگوریتم های هوشمند است.

چندین روش آماری برای شناسایی ناهنجاری ها وجود دارد که در این مقاله به آنها پرداخته شده است الگوریتم جنگل ایزوله (عایق الگوریتم جنگل) ما معتقدیم که این یکی از رایج ترین و کاربردی ترین الگوریتم ها برای علم داده در زمینه شناسایی ناهنجاری ها و یافتن انحرافات است.

منشا یک الگوریتم جنگل ایزوله

در سال 2008، سه دانشمند کامپیوتر، فی تونی لیو، کای مینگ تینگ و ژو هوآ ژو، برای اولین بار یک الگوریتم جنگل ایزوله (به اختصار iForest) توسعه دادند. ایده اصلی آنها برای طراحی این الگوریتم دو ویژگی مشترک داده های ناخواسته و غیرعادی بود:

  • تعداد این نقاط کمتر از سایر نقاط است
  • تفاوت قابل توجهی در مقادیر این نقاط در رابطه با جرم کل (عادی) داده ها
  فلایتیو در گزارشی تحلیل خود را از وضعیت گردشگری ایران منتشر کرد

از آنجایی که ناهنجاری ها از نظر تعداد کم هستند و اندازه آنها متفاوت است، جداسازی و طبقه بندی آنها نسبت به نقاط عادی آسان تر است. راه حل کلی الگوریتم جنگل ایزوله ایجاد گروه هایی از “درختان جداسازی” در مجموعه داده است. بنابراین ناهنجاری ها نقاطی هستند که مسیر متوسط ​​کوتاه تری نسبت به سایر نقاط در «درختان ایزوله» دارند. لازم به ذکر است که نویسندگان نام مقاله را «درختان جداسازی» که به اختصار iTrees است و الگوریتم جنگل ایزوله – iForest را نامگذاری کرده اند.

در سال 2010 افزونه ای به نام SCiforest برای این الگوریتم راه اندازی شد که بر موضوعات ناهنجاری خوشه ای تمرکز دارد و از هایپرسطح های تصادفی برای بهبود توانایی تشخیص ناهنجاری های موازی استفاده می کند. این قابلیت ها در نسخه اصلی این الگوریتم وجود نداشت. بعداً در سال 2012، نویسندگان اولین نسخه از مقاله الگوریتم جنگل ایزوله، مجموعه ای از آزمایشات را طراحی کردند تا ثابت کنند iForest دارای ویژگی های زیر است:

  • پیچیدگی زمانی کمی دارد و برای اجرا حافظه کمی می گیرد
  • می تواند برای داده های بزرگ با توابع نامرتبط استفاده شود
  • الگوریتم توانایی یادگیری و آموزش را دارد
  • دارای قابلیت ارائه نتایج تشخیصی با سطوح مختلف طبقه بندی بدون نیاز به بازآموزی

در سال 2013، دو دانشمند کامپیوتر به نام‌های Jingo Ding و Minori Phi ساختاری مبتنی بر iForest ایجاد کردند که مشکل تشخیص ناهنجاری‌ها در جریان داده‌ها را حل کرد. این یک نقطه عطف در توسعه الگوریتم iForest بود، زیرا بسیاری از سیستم های مقیاس بزرگ اکنون می توانند از این الگوریتم برای شناسایی نقاط غیرعادی استفاده کنند، بنابراین تجزیه و تحلیل های آینده این نوع داده ها و انجام فعالیت هایی مانند داده کاوی را سرعت می بخشند. و «یادگیری ماشینی» به میزان قابل توجهی افزایش یافته است.

بزن زیر میز!

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

iForest به جای تلاش برای ساخت یک مدل معمولی، ابتدا نقاط غیرعادی را شناسایی کرده و آنها را از مجموعه داده جدا می کند. الگوریتم ابتدا یک ویژگی دلخواه (بعد) را انتخاب می کند و سپس یک مقدار دلخواه را در فاصله بین حداقل و حداکثر مجموعه داده انتخاب می کند و این بعد را بر یک خط تقسیم تقسیم می کند. این باعث ایجاد مجموعه ای از درختان می شود و درختان کوتاه تر به عنوان شکست داده ها و ناهنجاری ها شناسایی می شوند. لازم به ذکر است که iForest الگوریتمی برای یادگیری کنترل نشده است. در قسمت بعدی مقاله با نحوه عملکرد این الگوریتم بیشتر آشنا خواهیم شد.

  ترافیک اینترنت بین المللی محدود است

جنگل ایزوله زیر ذره بین

همانطور که در بخش قبل ذکر شد، رویکرد کلی برای شناسایی ناهنجاری ها مدل سازی نقاط عادی است، اما iForest از رویکرد متفاوتی استفاده می کند. ایده اصلی الگوریتم این است که اگر درخت تصمیم بر روی یک مجموعه داده رسم شود، نقاط ناهنجاری از نظر طول کوتاهتر و به ریشه نزدیکتر هستند.

03 قطب آی تی

برای درک بهتر این مفهوم، با یک مثال ساده شروع می کنیم. حدود 8 میلیارد نفر روی زمین زندگی می کنند و ما به آنها به عنوان مجموعه ای از داده ها نگاه می کنیم. این مجموعه داده را می توان به ابعادی مانند سن، دارایی، محل تولد، موقعیت و غیره تقسیم کرد. حال می خواهیم نقاط غیرعادی این مجموعه داده را شناسایی کنیم. توجه داشته باشید که نقاط غیرعادی لزوماً داده های نادرستی نیستند و تفاوت قابل توجهی با سایر نقاط دارند. با ترسیم درخت تصمیم با بعد “دارایی 170 میلیارد دلار” شروع می کنیم.

در این درخت تصمیم، جف بزوس، یکی از بنیانگذاران آمازون، به عنوان یک مکان غیرعادی شناخته شده است. شکل نشان می دهد که بسیار نزدیک به ریشه درخت است. البته این درخت تصمیم هرس نمی شود و احتمالا ناهنجاری های دیگری نیز وجود دارد.

برای جدا کردن درخت جف بزوس، فقط بپرسید: “آیا بیش از 170 میلیارد دلار دارایی وجود دارد؟” اما از آنجایی که جلیل علیزاده (نویسنده مقاله) بسیار رایج تر از جف بزوس است، باید حداقل 10 سوال بپرسید. بله. / نه جدا کردنش

حال بهتر است به سراغ مثال آماری تری برویم و مجموعه ای از داده ها را در مختصات xy دو بعدی قرار دهیم. این مجموعه داده ابتدا به یک بعد (خط آبی) تقسیم می شود، سپس تقسیم با بعد دوم (خط نارنجی) و در نهایت آخرین تقسیم (خط سبز) انجام می شود.

04 قطب آی تی

اگر بخواهیم این مجموعه داده را به صورت درخت تصمیم ترسیم کنیم، شکل زیر به دست می آید. همانطور که مشخص است، نقطه G کوتاه ترین طول مسیر (طول مسیر برابر با 1) را دارد و از هر نقطه دیگری به ریشه نزدیکتر است، بنابراین نقطه G یک ناهنجاری و خروجی داده است. در این شکل مثلا نقطه C دارای طول مسیر 3 است و بنابراین یک ناهنجاری نیست!

05 قطب آی تی

برای ایجاد جنگل ایزوله باید تعداد زیادی درخت ساخته شود و هر درخت مشخص می کند کدام نقاط زودتر جدا شده اند که در واقع نقاط غیرعادی هستند. در نهایت، پس از ترسیم درختان، هر نقطه امتیازی بین 0 تا 1 دریافت می کند. در بحث بعدی به نحوه محاسبه نتیجه ناهنجاری می پردازیم.

ویژگی های اصلی جنگل های جدا شده

اکنون به ویژگی های کلی iForest و جوانب مثبت و منفی آن خواهیم پرداخت:

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

برآورد ناهنجاری را محاسبه کنید

استراتژی محاسبه یک نتیجه ناهنجاری در یک نقطه بر اساس معادل سازی مشاهدات ساختاری iTrees با ساختار باینری درخت جستجو است. این بدان معناست که دریافت یک گره خارجی از iTree معادل یک جستجوی شکست خورده BST است. بنابراین، محاسبه طول مسیر متوسط ​​که h (x) است برای به دست آوردن یک گره خارجی از فرمول زیر به دست می آید:

F1 قطب آی تی

در این راستا n تعداد داده های تجربی، m حجم نمونه و H عدد هارمونیک به دست آمده از رابطه زیر است:

F3 قطب آی تی

Γ نیز برابر با «ثابت اویلر- ماسکرونی» است که تقریباً برابر با 0.577 است. همانطور که گفته شد، مقدار c (m) مقدار متوسط ​​h (x) است که بر حسب m نوشته می شود. بنابراین، با انجام یک فرآیند نرمال سازی، می توانیم مقدار تخمین ناهنجاری را با توجه به x و m بدست آوریم که برابر است با:

F2 قطب آی تی

در این رابطه، E (h (x)) انتظار ریاضی برابر با میانگین h (x) در مجموعه درختان iTree است. اکنون که این اتصال را داریم، می توانیم کارهای زیر را انجام دهیم:

  • اگر مقدار s به 1 برسد، می توان گفت که نقطه x یک ناهنجاری است.
  • اگر مقدار s به 0.5 m برسد، می توان گفت که نقطه x یک نقطه نرمال است.
  • اگر برای تمام مقادیر x مقدار s به 0.5 برسد، می‌توان گفت که مجموعه داده هیچ ناهنجاری ندارد و تمام نقاط آن نرمال هستند.
06 قطب آی تی

با نتیجه غیر طبیعی ایرانی مشکل را حل کنید

یکی از مشکلات اصلی نسخه اصلی الگوریتم iForest، محاسبه «نتیجه ناهنجاری» بود. این مشکل در سال ۲۰۱۸ توسط سه دانشمند کامپیوتر به نام‌های سهند حریری، ماتیاس کاراسکو و رابرت برنر از دانشگاه ایلینوی حل شد. این افراد مدل جدیدی به نام «جنگل انزوا گسترده» یا به اختصار EIF معرفی کردند. این الگوریتم تخمین ناهنجاری را با دقت بیشتری محاسبه می کند.

دیدگاهتان را بنویسید

این سایت توسط reCAPTCHA و گوگل محافظت می‌شود حریم خصوصی و شرایط استفاده از خدمات اعمال.