شناسایی ناهنجاری به کمک جنگل ایزوله؛ زیر میز بزنید!

در پنجمین قسمت از مجموعه مقاله «گذری بر داده‌محوری و مدیریت محصول» قصد داریم کمی در علم داده عمیق شده و با یک الگوریتم نسبتا جدید و کاربردی در زمینه شناسایی داده‌های پرت و ناهنجار آشنا شویم. با گسترش فناوری‌های انفورماتیک، دامنه فعالیت مدیران محصول نیز روزبه‌روز توسعه و تنوع بیشتری می‌یابد. امروزه در اکثر شرکت‌های مطرح نرم‌افزاری و تحلیل داده به‌خصوص آن‌هایی که محصولات لبه علم تولید می‌کنند، موقعیت شغلی AI/ML Product Manager و Data Product Manager ایجاد شده است و این افراد به صورت مستقیم بر فرایندهای یادگیری ماشینی و هوش مصنوعی موجود در توسعه محصول نظارت دارند.

در تحلیل‌های آماری شناسایی ناهنجاری‌ها و یافتن نقاط پرت (Outlier Points) اهمیت بسیار زیادی دارد. در بعضی موارد وجود این نقاط باعث ایجاد خطا در طراحی مدل‌ آماری شده و دقت پیش‌بینی انجام شده را به طرز محسوسی کاهش می‌دهد. مواردی نیز وجود دارند که این نقاط نشانگر بروز نفوذ و فعالیت غیرعادی کاربران است که با بررسی آن‌ می‌توان امنیت سیستم را افزایش داد.

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

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

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

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

روش‌های آماری متعددی برای شناسایی ناهنجاری‌ها وجود دارد که در این مقاله به بررسی الگوریتم جنگل ایزوله (Isolation Forest Algorithm) می‌پردازیم که یکی از به‌روزترین‌ و کاربردی‌ترین الگوریتم‌های علوم داده در حوزه شناسایی ناهنجاری‌ها و یافتن نقاط پرت است.

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

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

• کم بودن تعداد این نقاط نسبت به سایر نقاط
• تفاوت چشمگیر مقادیر این نقاط نسبت به توده‌ی کلی (هنجار) داده‌ها 

از آن‌جایی که ناهنجاری‌ها تعدادشان کم و مقادیرشان متفاوت است، جداسازی و دسته‌بندی آن‌ها در مقایسه با نقاط هنجار آسان‌تر است. راهکار کلی الگوریتم جنگل ایزوله این است که گروه‌هایی از «درختان جداسازی» (Isolation Trees) در مجموعه‌ی داده ایجاد کند. بدین ترتیب ناهنجاری‌ها نقاطی هستند که به‌طور میانگین مسیر کوتاه‌تری نسبت به دیگر نقاط در «درختان جداسازی» دارند. لازم به ذکر است که نویسندگان مقاله «درختان جداسازی» را به اختصار iTrees و الگوریتم جنگل ایزوله را iForest نام‌گذاری کرده‌اند.

در سال ۲۰۱۰ افزونه‌ای از این الگوریتم به نام SCiforest با تمرکز بر بررسی مباحث ناهنجاری‌های خوشه‌ای و به کارگیری از اَبرصفحه‌های تصادفی به منظور افزایش توانایی تشخیص ناهنجاری‌های موازی منتشر شد. این توانمندی‌ها در نسخه اولیه این الگوریتم وجود نداشت. کمی بعدتر در سال ۲۰۱۲ نویسندگان نسخه اولیه مقاله «الگوریتم جنگل ایزوله» مجموعه‌ای از آزمایش‌ها را طراحی کردند تا ثابت کنند iForest دارای ویژگی‌های زیر است:

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

در سال ۲۰۱۳ دو دانشمند علوم کامپیوتر به نام «ژینگو دینگ» و «مینوری فی» ساختاری را بر مبنای iForest طراحی کردند که در آن مشکل تشخیص ناهنجاری‌ها در جریان داده‌ها (Streaming Data) برطرف شده بود. این اتفاق نقطه عطفی در توسعه الگوریتم iForest به حساب می‌آمد، چرا که اکنون بسیاری از سیستم‌های کلان‌‌داده‌ای نیز می‌توانستند از این الگوریتم برای شناسایی نقاط ناهنجار و پرت استفاده کنند و همین امر سرعت انجام تحلیل‌های آتی این جنس از داده‌ها و انجام فعالیت‌هایی نظیر «داده کاوی» و «یادگیری ماشین» را به طور محسوسی افزایش می‌داد.

زیر میز بزنید!

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

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

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

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

برای فهم بهتر این مفهوم با یک مثال ساده شروع می‌کنیم؛ حدودا نزدیک به ۸ میلیارد انسان روی کره زمین وجود دارند و آن‌ها را به عنوان یک مجموعه داده درنظر می‌گیریم. این مجموعه داده را می‌توان به بُعد‌هایی نظیر سن، دارایی، محل تولد، موقعیت شغلی و ... تقسیم‌بندی کرد. حال می‌خواهیم در این مجموعه‌ داده، نقاط ناهنجار را شناسایی کنیم. دقت کنید که نقاط ناهنجار لزوما داده‌های اشتباهی نیستند و تنها تفاوت معناداری با دیگر نقاط دارند. رسم درخت تصمیم‌گیری را با بُعد «برخورداری از دارایی ۱۷۰ میلیارد دلاری» آغاز می‌کنیم.

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

برای ایزوله کردن درخت جف بزوس، تنها کافیست این سوال را بپرسید که «آیا او بیش از ۱۷۰ میلیارد دلار دارایی دارد؟» اما از آن جایی که شخص جلیل علیزاده (نویسنده مقاله) بسیار معمولی‌تر از جف بزوس است، برای ایزوله کردن او حداقل نیاز به پرسیدن ۱۰ سوال بله/خیر دارید.

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

اگر بخواهیم این مجموعه داده ‌را به صورت درخت تصمیم‌گیری رسم کنیم، شکل زیر حاصل می‌شود. همان‌طور که مشخص است، نقطه G کوتاه‌ترین طول مسیر (طول مسیر برابر ۱) را دارد و از همه نقاط دیگر به ریشه نزدیک‌تر است و به همین منظور نقطه G یک ناهنجاری و داده پرت به حساب می‌آید. در این شکل به طور مثال نقطه C طول مسیرش برابر ۳ است و بنابراین ناهنجاری نیست!

برای تولید یک جنگل ایزوله باید تعداد زیادی درخت ساخته شود و هر درخت مشخص می‌کند که کدام نقاط زودتر ایزوله می‌شوند که در حقیقت نقاط ناهنجار هستند. در نهایت پس از رسم درخت‌ها به هر نقطه یک امتیاز بین ۰ تا ۱ داده می‌شود، هر میزان امتیاز ناهنجاری به ۱ نزدیک‌تر باشد، این نقطه به احتمال بیشتری یک داده پرت و ناهنجار است. در بحث بعدی به صورت متمرکزتر به بررسی نحوه محاسبه نمره ناهنجاری می‌پردازیم.

ویژگی‌های اصلی جنگل ایزوله

اکنون نگاهی به ویژگی‌های کلی iForest می‌اندازیم و نکات مثبت و منفی آن را مورد بررسی قرار می‌دهیم:

• زیرنمونه‌گیری (Sub-sampling): با توجه به اینکه الگوریتم iForest نیازی به یافتن و جداسازی همه نقاط نرمال ندارد، این الگوریتم می‌تواند توده‌ عظیمی از نقاط نمونه‌ آموزشی را نادیده بگیرد. بنابراین می‌توان ادعا کرد که iForest هنگامی که اندازه نمونه کوچک نگه داشته شود، عملکرد بسیار خوب و دقت بالایی دارد. این ویژگی در میان دیگر الگوریتم‌ها کمتر دیده می‌شود.
• غرق شدن (Swamping): هنگامی که فاصله میان نقاط نرمال و نقاط ناهنجار بسیار کم باشد، تعداد درخت‌های موردنیاز برای جداسازی ناهنجاری‌ها افزایش می‌یابد. در این شرایط ممکن است پدیده‌ای به نام «غرق شدن» رخ دهد. این امر سبب می‌شود که iForest تفاوت میان نقاط ناهنجار و نرمال را به کندی و با اشتباه فراوان تشخیص دهد. بنابراین ممکن است با هربار اجرای الگوریتم، نقاط متفاوتی به عنوان ناهنجاری شناسایی شوند و همین امر باعث می‌شود تا دقت الگوریتم به طرز محسوسی کاهش پیدا کند.
• پوشیده ماندن (Masking): زمانی که تعداد ناهنجاری‌ها زیاد باشد، این احتمال وجود دارد که برخی نقاط در یک خوشه متراکم و بزرگ قرا بگیرند و جداسازی ناهنجاری‌ها توسط iForest بسیار سخت و دشوار شود. این امر شباهت‌های زیادی با پدیده «غرق شدن» دارد و با انجام کارهایی نظیر نمونه‌گیری فرعی می‌توان مشکل را برطرف کرد.
• داده‌های کلان بُعدی (High Dimensional Data): یکی از جدی‌ترین محدودیت‌های روش استاندارد که بر مبنای محاسبه تابع فاصله کار می‌کند، ناکارآمدی الگوریتم در مواجه با مجموعه‌ داده‌های کلان بُعدی است. در فضاهای کلان بُعدی، فواصل نقاط نسبت به یک دیگر تقریبا یکسان است و همین امر اندازه‌گیری مبتنی بر فاصله را عملا ناکارآمد می‌کند. بدیهی است که الگوریتم iForest نیز در مواجه با این شکل از داده‌ها عملکرد ضعیفی دارد، اما با اضافه کردن یک آزمون و انتخاب ویژگی‌های محدود می‌توان باعث افزایش دقت و عملکرد الگوریتم شد.

محاسبه نمره ناهنجاری

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

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

همچنین γ برابر با «ثابت اویلر-ماسکرونی» است که به صورت تقریبی برابر با ۰.۵۷۷ است. همان‌طور که اشاره شد، مقدار c(m) میانگین h(x) است که برحسب m نوشته شده است. بنابراین با انجام یک فرآیند نرمال‌سازی می‌توانیم مقدار نمره ناهنجاری را باتوجه به x و m بدست آوریم که برابر است با:

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

• اگر مقدار s به ۱ میل کند، آن‌گاه می‌توان گفت که نقطه x یک ناهنجاری است.
• اگر مقدار s به ۰.۵ میل کند، آن‌گاه می‌توان گفت که نقطه x یک نقطه نرمال و متعارف است.
• اگر به ازای همه مقادیر x مقدار s به ۰.۵ میل کند، می‌توان گفت که مجموعه‌ داده مذکور فاقد ناهنجاری است و تمام نقاط آن متعارف و نرمال هستند.

رفع مشکل نمره ناهنجاری توسط یک ایرانی

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