تشخیص ناهنجاری تک‌کلاسه مبتنی بر پوش‌محدب ضمنی و یادگیری دسته‌جمعی

چکیده

در این پژوهش چارچوبی نوین برای تشخیص ناهنجاری ارائه می‌شود که بر پایه‌ی طبقه‌بندی تک‌کلاسه و بازنمایی پوش محدب ضمنی از ناحیهٔ داده‌های عادی طراحی شده است. ایدهٔ اصلی، برآورد مرز تصمیم به‌صورت غیرصریح و با اتکا به منظم‌سازی تور کشسان است؛ ترکیب همزمان $\ell_1$ و $\ell_2$ در تور کشسان از یک سو به تُنُک‌سازی و انتخاب ویژگی‌های مؤثر می‌انجامد و از سوی دیگر پایداری عددی و اثر گروهی را در میان ویژگی‌های همبسته فراهم می‌کند. برای ارتقای دقت و کاهش سوگیری ناشی از نامتوازنی داده، از یادگیری دسته‌جمعی مبتنی بر نمونه‌برداری و زیرفضای تصادفی بهره گرفته‌ایم. حل مسئله بهینه‌سازی نیز با استفاده از روش‌های گرادیان پروکسیمال و الگوریتم‌های AMP انجام می‌شود. به‌منظور رفع محدودیت‌های همگرایی AMP، نسخه‌ی پیشرفته‌ی آن یعنی KAMP به‌کار گرفته شده است که با ترکیب ایده‌های فیلتر کالمن و AMP، همگرایی را در شرایط نویزی و ماتریس‌های بد‌حالت پایدارتر و سریع‌تر می‌کند. همچنین گونه‌ی توزیع‌شده‌ی آن، DKAMP، با تقسیم ماتریس اندازه‌گیری میان گره‌ها و تبادل پیام‌های کم‌حجم از طریق توپولوژی‌های متنوع گراف، مقیاس‌پذیری و کارایی را در شبکه‌های بزرگ تضمین می‌نماید.
چارچوب پیشنهادی روی مجموعه‌داده‌های مرجع متنوع ارزیابی و با روش‌های مطرحی همچون OCSVM، SVDD، LOF، IF و EE مقایسه شده است. نتایج نشان می‌دهد مدل پیشنهادی نه‌تنها میانگین حسابی و هندسی امتیازها، بلکه شاخص‌هایی مانند دقت، صحت، بازخوانی، F1 و کاپا را به‌طور معناداری بهبود می‌دهد و در برابر ساختارها و توزیع‌های مختلف داده عملکردی پایدار و قابل اعتماد دارد. بدین‌ترتیب، ترکیب پوش محدب ضمنی، منظم‌سازی تور کشسان، AMP،KAMP،DKAMP
و یادگیری دسته‌جمعی چارچوبی منسجم، مقیاس‌پذیر و استوار برای تشخیص ناهنجاری در سناریوهای واقعی و داده‌های پیچیده فراهم می‌آورد.

تعریف مساله

ناهنجاری‌ها الگوهایی در داده‌ها هستند که با یک مفهوم خوب تعریف شده از رفتار عادی مطابقت ندارند. تشخیص ناهنجاری به مشکل یافتن الگوهایی در داده‌ها اشاره دارد که از رفتار عادی مورد انتظار پیروی نمی‌کنند. این الگوهای غیرقابل تطابق معمولاً در زمینه‌های مختلف به عنوان ناهنجاری‌ها ، نقاط پرت، مشاهدات ناهماهنگ و استثناها شناخته می‌شوند. از این میان، ناهنجاری‌ها و نقاط پرت دو اصطلاحی هستند که به طور معمول در زمینه‌های مختلف تشخیص ناهنجاری استفاده می‌شوند و گاهی به طور متناوب به کار می‌روند. اهمیت تشخیص ناهنجاری به این واقعیت برمی‌گردد که ناهنجاری‌ها معمولا به اطلاعاتی برای اقدامات بحرانی تبدیل می‌شوند. بسیاری از سیستم‌های یادگیری ماشین فرض می‌کنند که تجربه آموزشی آنها نماینده‌ای از تجربه آزمون است، اما در دنیای واقعی، این فرض نادرست است؛ داده‌های “نو” یا “ناهنجار” که در داده‌های آموزشی وجود نداشته‌اند، می‌توانند منجر به کاهش دقت پیش‌بینی‌ها و بروز نگرانی‌های ایمنی شوند؛ بعنوان مثال، سیستم‌های خودران باید در صورت مشاهده‌ی شرایط یا اشیاء ناشناخته‌ای که از قبل آموزش ندیده‌اند به انسان‌ها هشدار دهند و یا یک تصویر MRI ناهنجار ممکن است نشان‌دهنده وجود تومورهای بدخیم باشد.
موضوع دیگری که به تشخیص ناهنجاری مربوط می‌شود، تشخیص نوآوری است که هدف آن شناسایی الگوهای قبلاً مشاهده نشده (نوظهور، جدید) در داده‌ها است. تفاوت بین الگوهای جدید و ناهنجاری‌ها این است که الگوهای جدید اغلب ممکن است پس از شناسایی به مدل عادی اضافه ‌شوند.
بعلاوه در شرایط واقعی، به دلیل کاربردهای عملی در شرکت‌ها یا صنایع، داده‌های تولید شده اغلب توزیع نامتوازن دارند؛ به عنوان مثال، مسائلی مانند تشخیص بیماری، تحلیل اختلال‌های بیولوژیکی، پیش‌بینی بلایای طبیعی، تشخیص ناهنجاری، کشف تلقب و همچنین کاربردهای بیومتریکی‌ای مانند احراز هویت دارای مجموعه دادگانی نامتوازن هستند. گرابز در سال 1969 اولین کسی بود که ناهنجاری را به عنوان: “مشاهده بیرونی یا پرت که به وضوح از سایر اعضای نمونه‌ای که در آن رخ می‌دهد منحرف می‌شود” تعریف کرد. بنابراین، یک رویکرد ساده برای تشخیص ناهنجاری این است که یک منطقه نمایانگر رفتار عادی تعریف کنیم و هر مشاهده‌ای در داده که به این منطقه عادی تعلق ندارد را به عنوان یک ناهنجاری اعلام کنیم. اما عوامل مختلفی این رویکرد ظاهراً ساده را به چالشی بزرگ تبدیل می‌کند. بعنوان مثال، در زمینه یادگیری ماشین، به طور معمول فرض می‌شود که تعداد نمونه‌ها در هر کلاس مورد مطالعه، تقریباً برابر است. این در‌حالی است که در مسائل مربوط به تشخیص ناهنجاری که معمولا با داده‌های نامتوازن در ارتباط هستند استفاده از روش‌های مرسوم طبقه‌بندی (دو یا چندکلاسه) منجر به انحراف به سمت کلاس یا کلاس‌هایی می‌شود که نمونه بیشری دارند. در چنین شرایطی که مدل‌سازی و تشخیص نمونه‌های کلاس اقلیت، بسیار دشوار است، استفاده از طبقه‌بند تک کلاسه (OCC) رویکردی مناسب برای تشخیص داده‌های غیرعادی نسبت به داده‌‌های کلاس شناخته شده(اکثریت) می‌باشد. OCC (شکل ۱) یک حالت خاص از دسته‌بندی چندکلاسه است، جایی که داده‌های مشاهده‌شده در طول آموزش تنها از یک کلاس مثبت هستند و کلاس منفی یا وجود ندارد، یا به خوبی نمونه‌برداری نشده و یا به وضوح تعریف نشده است. OCC همچنین در مسائل خاصی مانند داده‌های نویزی، انتخاب ویژگی‌ و کاهش حجم داده‌های کلان مورد بحث و مطالعه قرار می‌گیرد . تشخیص ناهنجاری با استفاده از تحلیل محدب (CA) در قالب طبقه‌بندی تک‌کلاسه (OCC) یک تکنیک مهم برای شناسایی نمونه‌های “نو” یا “ناهنجار” است که کاربرد گسترده‌ای در زمینه‌های مختلف دارد. تحلیل محدب از تکنیک‌های تعیین مرزهای هندسی مجموعه هدف استفاده می‌کند.
تحلیل محدب(پوش محدب) علاوه‌بر پیچیدگی زمانی زیاد $\mathcal{O}(n^{\lfloor\frac{p}{2}\rfloor})$ و مقیاس‌ناپذیری آن، در مواجهه با مجموعه‌های غیرمحدب کارایی کمتری دارد. افزون بر این، بسیاری از روش‌های مبتنی بر پوش محدب در مواجهه با داده‌های چندمدی و غیرمحدب دچار ضعف هستند. از سوی دیگر، اغلب روش‌های OCC به یک مسئلهٔ برنامه‌ریزی درجه‌دو منتهی می‌شوند که حل آن در مقیاس‌های بزرگ بسیار پرهزینه است. برای رفع این محدودیت‌ها، در سال‌های اخیر الگوریتم‌های پیام‌رسانی تقریبی (AMP) به‌عنوان یک روش تکراری کارآمد برای حل مسائل بازسازی سیگنال تبدیل شده‌اند. AMP دارای سرعت همگرایی بالا است، اما تضمین همگرایی آن تنها در شرایط ایده‌آل مانند ماتریس‌های تصادفی زیرگاوسی برقرار است. به‌منظور غلبه بر این محدودیت، نسخهٔ توسعه‌یافته‌ای به نام Kalman-AMP (KAMP) معرفی شده است که با ترکیب ایده‌های فیلتر کالمن و AMP، پایداری و همگرایی الگوریتم را در شرایط نویزی و ماتریس‌های بدحالت بهبود می‌دهد. همچنین برای افزایش مقیاس‌پذیری، نسخهٔ غیرمتمرکز این الگوریتم با نام Distributed KAMP(DKAMP) توسعه داده شده است. در این نسخه، ماتریس اندازه‌گیری بین گره‌های یک گراف توزیع می‌شود و هر گره با اجرای محلی الگوریتم KAMP و تبادل اطلاعات با همسایگان (از طریق راهبردهایی نظیر ارتباط تصادفی) به یک برآورد جمعی و مقاوم همگرا می‌شود. این طراحی امکان استفاده عملی از روش‌های مبتنی بر AMP و KAMP را در محیط‌های گرافی بزرگ و پویا فراهم می‌کند و نسبت به نویز و ساختارهای پیچیده داده مقاوم است. به طور خلاصه، مسئلهٔ مورد بررسی در این پژوهش را می‌توان چنین بیان کرد: طراحی و توسعهٔ یک چارچوب طبقه‌بندی تک‌کلاسه مبتنی بر مرز پوش محدب ضمنی که با استفاده از الگوریتم‌های تکراری کارآمد (AMP) و توسعه‌های آن (KAMP و DKAMP) بتواند چالش‌های مربوط به محاسبهٔ پوش محدب، مقیاس‌پذیری، پایداری در شرایط نویزی و داده‌های بدحالت را برطرف سازد.

(آ) طبقه‌بندی چند‌کلاسه

(ب) طبقه‌بندی تک‌کلاسه

شکل 1: تفاوت بین طبقه‌بند تک‌کلاسه و چند‌کلاسه

قسمتی از پیشینه‌تحقیق بررسی شده

بخشی از پیشینه‌تحقیق مربوط به روش‌های تُنُک‌سازی

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

الگوریتم پیام‌رسانی تقریبی مبتنی‌بر کالمن

نسخه غیرمتمرکز روش پیشنهادی

برای پیاده‌سازی الگوریتم‌هایی نظیر AMP و نسخه‌ی توسعه‌یافته‌ی آن KAMP (یا KAMP) به شکل غیرمتمرکز، شبکه‌ای از گره‌ها را می‌توان به‌صورت یک گراف جهت‌دار $(\mathcal{G}=(\mathcal{V},\mathcal{E}))$ مدل کرد که $

\mathcal{V}

= L$ تعداد گره‌ها است. هر گره $l$ مجموعه‌ای از مشاهدات محلی شامل زیرماتریس $(\mathbf{A}_l)$ و زیربردار $(\mathbf{y}_l)$ را در اختیار دارد، به‌طوری‌که با تجمع این زیرماتریس‌ها و بردارها، ماتریس اندازه‌گیری و بردار مشاهده‌ی کلی به‌دست‌می‌آید:

\[\mathbf{A} = \begin{bmatrix} \mathbf{A}_1 \\ \mathbf{A}_2 \\ \vdots \\ \mathbf{A}_L \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} \mathbf{y}_1 \\ \mathbf{y}_2 \\ \vdots \\ \mathbf{y}_L \end{bmatrix},\]

که در آن $(\mathbf{y}\ell = \mathbf{A}\ell \mathbf{x} + \boldsymbol{\omega}\ell)$ مدل مشاهده‌ی محلی گره $(\ell)$ است (بردار نویز $(\boldsymbol{\omega}\ell)$ نیز دارای واریانس $(\sigma^2)$ می‌باشد). بنابراین هر گره فقط بخشی از معادله‌ی $(\mathbf{y}=\mathbf{A}\mathbf{x} + \boldsymbol{\omega})$ را مشاهده می‌کند و نیازی به دانستن کل ماتریس $(\mathbf{A})$ یا بردار $(\mathbf{y})$ ندارد.

در الگوریتم KAMP توزیع‌شده، هر گره الگوریتم KAMP را روی داده‌های محلی خود اجرا می‌کند و یک تخمین اولیه از بردار $(\mathbf{x})$ به‌دست‌می‌آورد. سپس گره‌ها برای رسیدن به تخمین مشترک، نتایج خود را با همسایگان مبادله می‌کنند. مکانیزم معمول برای این تبادل، میانگین‌گیری اجماعی مقادیر همسایگان است؛ بدین صورت که هر گره $l$ مقدار تخمین خود را با مقادیر دریافتی از همسایگان $(\mathscr{N}_l)$ ترکیب می‌کند.

الگوریتم نسخه غیرمتمرکز روش پیشنهادی

الگوریتم غیرمتمرکز پیام‌رسانی تقریبی مبتنی‌بر کالمن

آزمایشات

بررسی کارایی روش پیشنهادی برروی مجموعه دادگان ODDS

مقایسه معیارهای عملکرد برای مدل‌های مختلف تشخیص ناهنجاری، از جمله LOF، IF، EE، SVDD، OCSVM و روش پیشنهادی. معیارهایی مانند F1-score (F1)، دقت (P)، صحت (A)، بازخوانی (R)، کاپا (K)، میانگین هندسی (GM) و میانگین حسابی (AM) برای ارزیابی اثربخشی هر مدل استفاده می‌شوند. نمودار میله‌ای میانگین نمرات عملکرد را به‌همراه نوار‌های خطا نشان می‌دهد. روش پیشنهادی به طور مداوم نمرات بالایی را در چندین معیار به دست می‌آورد، که عملکرد قوی و قابلیت اطمینان آن را در مقایسه با سایر مدل‌ها نشان می‌دهد.

بررسی عملکرد مرز‌بندی روش‌پیشنهادی برروی داده‌های تصویری

شکل 1: مرز تصمیم‌گیری بر روی کلاس هدف مجموعه داده CIFAR-10 با استفاده از نگاشت Isomap.

شکل 2: مرز تصمیم‌گیری بر روی دادگان CIFAR-10 با استفاده از نگاشت Isomap (تمامی کلاس‌های مجموعه داده CIFAR-10 استفاده شده است).

بررسی انعطاف‌پذیری روش‌پیشنهادی در فضای ورودی

اثبات برتری روش مبتنی‌بر کالمن نسب به پیام‌رسانی تقریبی

شبیه‌سازی‌های انجام شده بر‌روی ماتریس‌های تصادفی گاوسی، متعامد و چوله صورت گرفته‌اند.

دستیابی نسخه مبتنی‌بر کالمن به کران‌های خطای فشرده‌تر

دستیابی نسخه مبتنی‌بر کالمن به واریانس خطای کمتر

جدول ۱: مقایسه میانگین رتبه‌ها و آماره‌های آزمون به تفکیک نوع ماتریس‌ها براساس معیار میانگین مربعات خطا

Matrix Type	Ranks: method	Ranks: N	Ranks: Mean Rank	Test Statistics: Mann-Whitney U	Test Statistics: Wilcoxon W	Test Statistics: Z	Test Statistics: Asymp. Sig. (2-tailed)
Gaussian	AMP	30	45.50	0.000	465.000	-6.653	< 0.001
	KAMP	30	15.50
Heavy	AMP	29	44.72	8.000	473.000	-6.474	< 0.001
	KAMP	30	15.77
Orthogonal	AMP	30	42.73	83.000	548.000	-5.426	< 0.001
	KAMP	30	18.27

جدول ۲: مقایسه میانگین رتبه‌ها و آماره‌های آزمون به تفکیک نوع ماتریس‌ها براساس معیار نسبت سیگنال به نویز

Matrix Type	Ranks: method	Ranks: N	Ranks: Mean Rank	Test Statistics: Mann-Whitney U	Test Statistics: Wilcoxon W	Test Statistics: Z	Test Statistics: Asymp. Sig. (2-tailed)
Gaussian	AMP	30	15.50	0.000	465.000	-6.653	< 0.001
	KAMP	30	45.50
Heavy	AMP	29	15.00	0.000	435.000	-6.595	< 0.001
	KAMP	30	44.50
Orthogonal	AMP	30	15.50	0.000	465.000	-6.653	< 0.001
	KAMP	30	45.50

جدول ۳: مقایسه میانگین رتبه‌ها و آماره‌های آزمون به تفکیک نوع ماتریس‌ها براساس معیار نسبت اوج سیگنال به نویز

Matrix Type	Ranks: method	Ranks: N	Ranks: Mean Rank	Test Statistics: Mann-Whitney U	Test Statistics: Wilcoxon W	Test Statistics: Z	Test Statistics: Asymp. Sig. (2-tailed)
Gaussian	AMP	30	15.50	0.000	465.000	-6.653	< 0.001
	KAMP	30	45.50
Heavy	AMP	29	15.31	9.000	444.000	-6.459	< 0.001
	KAMP	30	44.20
Orthogonal	AMP	30	18.33	85.000	550.000	-5.396	< 0.001
	KAMP	30	42.67

باتوجه به آزمون‌های آماری انجام شده می‌توان دید که روش‌پیشنهادی در تمامی موارد برتری خود نسبت به روش AMP حفظ کرده است.

نمونه‌ای از توپولوژی‌های بررسی شده

رتبه‌بندی میزان‌کارایی توپولوژی‌های مختلف شبکه براساس معیار‌های سراسری شبکه

نتایج

• برتری روش پیشنهادی در تشخیص ناهنجاری تک‌کلاسه نسبت به روش‌های رقیب بررسی شده
• توانایی تشکیل مرز‌های کاملا منعطف در فضای ورودی
• توانایی تشکیل پوش‌محدب در فضای ویژگی منتانهای با استفاده از کرنل چند‌جمله‌ای
• اثبات کارایی روش KAMP برروی انواع ماتریس‌های تصادفی نسبت به روش AMP
• دستابی با واریانس خطای به مراتب کمتر از واریانس‌خطای AMP

جزییات بیشتر در پایان نامه یوسف قلعه‌نوئی کارشناسی ارشد از دانشگاه فردوسی مشهد