Document Type : Research Article
Authors
1 Dept. of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
2 Center for Applied Intelligent Systems Research (CAISR), Halmstad University, Halmstad, Swede
3 Dept. of Computer Science, Tarbiat Modares University, Tehran, Iran
Abstract
Keywords
یکی از مهمترین مسائل در حوزۀ دادهکاوی، تشخیص ناهنجاری در دادهها است. [1]–[3] ناهنجاری، هرگونه انحراف از رفتار طبیعی شناخته میشود. رویکردهای سنتی بر پایۀ یادگیری رفتار طبیعی و استفاده از مدل ساختهشده برای استخراج دادههای ناهنجار بنا شدهاند[4]–[6]. در این میان در دادههای جریانی به دلیل ماهیت پویایشان مسئله کمی پیچیدهتر خواهد بود؛ زیرا مدل ساختهشده باید به اندازۀ کافی در مقابل پویایی و تغییرات داده، تطبیقپذیر باشد. بدین ترتیب مدلهای یادگیری برونخط منسوخ و به مدلهای یادگیری برخط تطبیقپذیر نیاز است.
مفهوم تحقیقات بسیار گستردهای در حوزۀ رانش انجام شده است و در مقالاتی مثل [7], [8] روشهای باناظر یا در [9] روشهای بیناظر مرور شدهاند. در متون فارسی نیز در [1] و [2] روشهای باناظر برای تشخیص رانش مفهوم در فرآیندهای کسبوکار ارائه شدهاند؛ اولی با تکیه بر شبکههای عمیق، روشی خودکار و مستقل از پنجره برای تعدیل دو چالش انتخاب ویژگی و اندازۀ پنجرۀ لغزان ارائه کرده است. پژوهش دوم نیز یک روش ابتکاری با معرفی یک تابع فاصلۀ اصلاحشده، برای شناسایی محل و زمان ایجاد رانش مفهوم ارائه کرده است؛ اما تحقیقات محدودتری در مواجهۀ رانش مفهوم و ناهنجاری انجام شدهاند که عمدتاً روشهای باناظر و شبکههای عمیقاند [10], [11]. در متون فارسی نیز در [3] راهکاری برای بهروزرسانی پروفایل مشتریان با لحاظکردن رانش در رفتار آنها در سیستمهای کشف تقلب برای کاهش هشدارهای نادرست ارائه شده است. در این پژوهش بر استفاده از الگوریتمهای فرابتکاری در انتخاب طول مناسب پنجرۀ لغزان تمرکز شده است.
در این میان، رویکردهای برخط مبتنی بر تجزیه، ازجمله رویکردهای برجسته در تشخیص ناهنجاری در شبکههای در حال تکاملاند [12]–[15]. این روشها ویژگیهای جریان داده را به شکلی انعطافپذیر و کارآمد مدل میکنند تا الگوهای پایه و مخفی را در قالب زیرفضای اصلی[1] یا پنهان، تخمین بزنند و ردیابی کنند. در ادامه، خطای تخمین، مبنای تشخیص ناهنجاری قرار میگیرد. نسخههای توسعهیافتۀ این روشها که در مقابل نویز استوارند[2]، از ابتدا و در مدل ساختهشده علاوه بر زیرفضای اصلی، مؤلفهای با عنوان مؤلفه خلوت[3] در نظر میگیرند. این مؤلفه در حین ردیابی و تخمین زیرفضای اصلی، انحرافات در دادهها را جمعآوری میکند که از آن برای تشخیص ناهنجاری استفاده میشود. همچنین، همانگونه که اشاره شد دادههای جریانی در بستر زمان با تغییرات زیادی مواجهاند. تغییر در توزیع داده در طول زمان به پدیدهای به نام رانش مفهوم منجر میشود. گرچه رویکردهای مبتنی بر تجزیه برای تطبیقپذیری با تغییرات ارائهاند، پدیدۀ رانش مفهوم بهتازگی و در قالب رانش در زیر فضای اصلی، معرفی شده است [16].
بهتازگی مدلهای برخط مبتنی بر تجزیۀ ماتریسی که قابلیت مدیریت رانش مفهوم را داشته باشند، به تعداد اندکی ارائه شدهاند. در [17] روشی با عنوان تجزیۀ ماتریس موقتی[4] برای ردیابی رانش مفهوم در آرایۀ پنهان هر کاربر در سیستمهای توصیهگر ارائه شده است. این راهکار از یک نسخۀ اصلاحشدۀ کاهش گرادیان تصادفی استفاده میکند تا آرایۀ فضای پنهان کاربر را در هر گام زمانی آموزش دهد. سپس با استفاده از رگرسیون لاسو یک مدل خطی را برای انتقال هر آرایۀ پنهان آموزش میدهد. درواقع این مدل خطی، رانش مفهوم را آموزش و اثر آن را به گامهای زمانی بعدی انتقال میدهد؛ بنابراین، در این راهکار، ردیابی و انتقال اثر رانش مفهوم یا به عبارتی تطبیق ضمنی یادگیرنده با رانش مفهوم مدنظر است و هیچ استراتژی صریحی برای تشخیص و اعلام رانش مفهوم ندارد. علاوه بر این، به بحث تشخیص ناهنجاری نیز نپرداخته است.
در [12] نیز روشی مبتنی بر تجزیۀ ماتریسی برخط با عنوان تجزیۀ ماتریس فصلی SMF[5] ارائه میشود که با ردیابی تغییرات در فضای پنهان، وجود رانش را در دادهها تحلیل میکند. مدل ارائهشده در این پژوهش نیز رانش را بهصورت ضمنی و تأثیرگذار بر فرآیند یادگیری، مدیریت میکند و آگاهی از آن، تنها با تحلیل برونخط مؤلفههای مدل، امکانپذیر است و درواقع استراتژی مشخصی برای تشخیص و اعلام وقوع رانش ندارد.
بحث رانش مفهوم در حوزۀ روشهای تجزیۀ تانسوری برای نخستینبار در [16] مطرح و الگوریتمی برای تشخیص مفاهیم رانشیافته ارائه شد. عملکرد روش ارائهشده بدین شکل است که با رسیدن هر تانسور جدید، ابتدا رتبه[6] آن، مشخص و به فاکتورهایش تجزیه میشود. سپس با مقایسۀ شباهت مفاهیم جدید با مفاهیم قبلی، مفاهیم جدید، همپوشان یا حذفشده تعیین میشوند؛ بنابراین، در این راهکار، رانش مفهوم تنها در قالب ایجاد یا حذف مفهوم پوشش داده شده است و برای تشخیص ناهنجاری نیز راهکاری ندارد.
یکی از مشکلات اساسی در این حوزه، نبود راهکاری با امکان تشخیص همزمان و خودکار رانش و ناهنجاری است. همچنین، در روشهای فوق، استراتژی صریحی برای تشخیص رانش مفهوم و تطبیق مدل با تغییرات وجود ندارد و مدل بهطور ناآگاهانه و کورکورانه[7] و در همۀ گامهای زمانی بهروز میشود. توجه به این نکته نیز حائز اهمیت است که درست است که ناهنجاری، انحراف از رفتار طبیعی است، اما رفتار طبیعی در بستر زمان تغییر میکند؛ بنابراین، این پدیده یعنی همان رانش مفهوم، بر معنای ناهنجاری نیز تأثیر میگذارد. بدین ترتیب تشخیص رانش مفهوم و تفکیک آن از ناهنجاری به کاهش تشخیص هشدار نادرست در فرآیند تشخیص ناهنجاری منجر میشود. همچنین، تشخیص رانش مفهوم و اعلام صریح آن با یک آشکارساز به طراحی یک یادگیرند رانش - آگاه[8] منجر میشود. بدین ترتیب یادگیرنده بهطور آگاهانه[9] و تنها در نقاط رانش، بهروز و در فرآیند پرهزینۀ یادگیری صرفهجویی میشود.
با توجه به توضیحات ارائهشده، این مقاله مکانیزمی برای تشخیص صریح رانش مفهوم و به تبع آن، تطبیق آگاهانۀ یادگیرنده ارائه میکند. همچنین، ناهنجاری را بهطور همزمان و برخط و در هر گام زمانی در کنار وقوع رانش، بررسی و اطلاعرسانی میکند.
در ادامه، مفاهیم پایه در بخش دوم مرور میشوند. روش پیشنهادی در بخش سوم و آزمایشات انجامشده به همراه نتایج بهدستآمده در بخش بعدی ارائه میشوند. نتایج و معرفی کارهای آینده در بخش انتهایی ارائه میشوند.
اگر فرآیندی که به تولید دادۀ جریانی منجر میشود با متغیر تصادفی χ مدل شود، رانش مفهوم بهصورت «تغییر در احتمال توزیع متغیر تصادفی تحت زمان» [16] تعریف میشود. در یادگیری باناظر، متغیر تصادفی χ به شکل XY (X مجموعه صفات و Y متغیر هدف) و رانش مفهوم به معنی تغییر در توزیع تجمعی X و Y است؛ اما در یادگیری بیناظر متغیر تصادفی تنها شامل X است و متغیر هدف یا برچسبی وجود ندارد [18]. در روشهای مبتنی بر تجزیۀ تانسور برخط، مفهوم همان ساختار مخفی موجود در داده است [16].
در ادامه، واحدهای سازندۀ یک سیستم یادگیری بیناظر تحت رانش مفهوم برگرفته از [8] تشریح میشوند. نخستین بخش، واحد حافظه است که دو وظیفۀ مدیریت داده ورودی و کنترل مکانیسم فراموشی را به عهده دارد. دادۀ ورودی میتواند بهصورت تکنمونه یا تجمعی (مبتنی بر پنجره) مدیریت شود. مکانیسم فراموشی نیز بهصورت تدریجی یا ناگهانی برای کنترل اثر دادههای قدیمی بر مدل اعمال شود. دومین بخش، واحد مدیریت تغییرات، مسئولیت پایش تغییرات و اعلام وقوع رانش را برعهده دارد.
قلب سیستم نیز واحد یادگیری است که سه ویژگی عمده دارد؛ ویژگی نخست، حالت یادگیری را مشخص میکند و مشخص میکند با رسیدن دادۀ جدید، یادگیری از نو آغاز و مدل جدید ساخته شود یا روشهای یادگیری افزایشی، برخط یا جریانی استفاده شوند تا بهطور تدریجی، فرآیند یادگیری تکمیل شود. ویژگی دوم، تطبیقپذیری را مشخص میکند. واحد یادگیری در این بخش، استراتژی خود را برای تطبیق با تغییرات تعیین میکند. اصولاً دو استراتژی کورکورانه و آگاهانه تعریف شده است. در حالت کورکورانه، یادگیرنده بهطور ضمنی و در یک فرآیند پیوسته، تطبیق با تغییرات احتمالی را انجام میدهد؛ بدون اینکه هیچ آگاهی از وقوع رانش داشته باشد. این استراتژی ناآگاهانه و پُرهزینه است. در طرف مقابل، سیستمهای با استراتژی آگاهانه یا رانش - آگاه، با واحد تشخیص رانش در ارتباط است و فرآیند تطبیق و بهروزرسانی یادگیرنده، تنها در صورت بهروز رانش انجام میشود. توجه به این نکته نیز حائز اهمیت است که در ادبیات این حوزه، گاهی روش کورکورانه را یادگیری تکاملی و روش آگاهانه را یادگیری خود - تطبیقی مینامند [19]. ویژگی سوم واحد یادگیرنده نیز مشخص میکند یادگیرنده از یک مدل بهره میبرد یا مبتنی بر چندین مدل و یادگیری تجمعی بنا شده است.
تانسور یک آرایۀ چندبعدی است که مرتبه[10] آن بیانکنندۀ تعداد ابعاد آن است. تانسور مرتبه یک معادل یک بردار، تانسور مرتبه دو معادل ماتریس و تانسور برای اشاره به تانسورهای با مرتبه سه و بالاتر استفاده میشود. بدین ترتیب، تانسور یک ابزار قدرتمند برای پردازش دادهها از جنبههای مختلف است؛ برای نمونه، تعامل افراد در یک شبکۀ اجتماعی در بستر زمان در قالب یک تانسور با سه بعد کاربر، کاربر و زمان مدل میشود.
روشهای تجزیۀ تانسور، ابزار قدرتمندی برای پردازش اینگونه دادهها هستند که زیرفضای اصلی و بهعبارتی الگوهای معنادار را استخراج میکنند. پرکاربردترین تجزیۀ تانسوری تجزیه CANDECOMP/PARAFAC (CP) است که طبق رابطه زیر تانسور χ (L×W×T) را به ماتریس فاکتورهایش یعنی ، و تجزیه میکند [20].
(1) |
|
در دستۀ مهمی از روشهای تشخیص ناهنجاری، دادههای بعد بالا را به زیرفضای با رتبه پایین[12] نگاشت میکنند؛ به گونهای که در فضای جدید، ناهنجاریها بهراحتی تشخیص داده میشوند. این مسئله با عنوان یادگیری زیرفضا (یا تخمین رتبه پایین) یا تخمین آنها شناخته میشود. یادگیری زیرفضا در محیط نویزی را یادگیری استوار زیرفضا مینامند که تخمین به دو مؤلفۀ زیرفضا و مؤلفۀ خلوت انجام میشود. این مفاهیم در داده جریانی که دادهها بهصورت یکجا در اختیار نیستند، مفهوم ردیابی برخط زیرفضا را پیدا میکنند؛ زیرا فرآیند یادگیری با بهروزرسانی و ردیابی زیرفضا در زمان انجام میشود. در اینجا نیز در حضور نویز، هم زیرفضا و هم مؤلفۀ خلوت ردیابی میشوند و مسئلۀ ردیابی برخط و استوار زیرفضا شکل میگیرد.
روشهای مبتنی بر ردیابی برخط و استوار زیرفضا، داده را به دو بخش زیرفضای اصلی و مؤلفۀ خلوت، تخمین میزنند و با تحلیل بخش خلوت، به استخراج ناهنجاری در دادهها میپردازند. این روشها برای مدلسازی دادههای جریانی بسیار انعطافپذیرند؛ زیرا ویژگیهای مختلف مربوط به آنها بهراحتی در مدل منعکس میشوند. یکی از مهمترین ویژگی دادههای جریانی، تغییر و پویایی آنها در گذر زمان است؛ بنابراین، یک مدل کارآمد باید در مقابل این تغییرات، تطبیقپذیر باشد. نوعی از این تغییرات مربوط به تغییرات ناگهانی یا افزایشی الگوهای اصلی پنهان در دادهها یا همان زیرفضای اصلی است. بهتازگی در [21] الگوریتمی بر پایه مدل زیر ارائه شده است که تطبیقپذیری بسیار خوبی در مقابل این دسته از تغییرات دارد.
(2) |
|
بر مبنای مدل فوق، Ytبهعنوان ماتریس مجاورت گراف ورودی در هر گام زمانی به زیرفضای اصلی و تغییراتش به شکل و ماتریس خلوت تجزیه میشود. یادآوری میشود این تجزیه یک فرم توسعهیافته از تجزیه برخط CP است که ماتریسهای و ماتریسهای فاکتور غیر زمانی و b فاکتور زمان و R رتبه ماتریس داده ورودی است. با اعمال نرم فربنیوس و استفاده از مکانیسم کمترین مربعات نمایی وزندار مبتنی بر فاکتور فراموشی λ بر ماتریسهای A و C، زیرفضای اصلی با رجوع به سابقۀ داده در طول زمان ردیابی میشود. همچنین، با اعمال نرم یک بر و بهعنوان ماتریسهای خلوت مربوطه به فاکتورهای A و C انحرافات الگوهای اصلی محاسبه میشوند. به این ترتیب، زیرفضای اصلی در یک روند تکاملی و با نگاه به سابقۀ دادهها بهروز میشود؛ اما انحرافات، در لحظه و برخط بهازای هر گام زمانی محاسبه میشوند. ماتریس خلوت V هم در هر گام زمانی انحرافات سراسری را جمع آوری میکند که مبنای استخراج ناهنجاری است.
در این رابطه، پارامتر μ و λ2 برای کنترل دقت تقریب ماتریسهای مربوط به زیرفضا و پارامتر λ1میزان خلوتبودن ماتریس V را کنترل میکنند. در مواقعی که نرخ خطا در سیستم کم تخمین زده میشود، μ مقدار کمتری خواهد داشت. λ نیز مقداری بین صفر و یک دارد. مقدار یک به معنی استفاده از همۀ سوابق دادهها و معادل مدل برونخط است؛ اما در مقادیر کمتر از یک بهصورت نمایی از اهمیت و وزن دادههای قدیمی برای محاسبۀ فاکتورهای جدید کاسته میشود.
مدل فوق یک مسئلۀ بهینهسازی نامحدب است که تخمین فاکتور زمان با استفاده از تخمینگر کمترین مربعات، تخمین ماتریس خلوت V براساس عملگر آستانهگیری نُرم، تخمین A’ وC’ در قالب تخمینگر لاسو و تخمین فاکتورهای A و C با استفاده از کمترین مربعات بازگشتی بهصورت متناوب انجام میشوند. محاسبات مربوطه بهطور کامل در مقاله [21] آمدهاند.
با ارجاع به شکل (1) بهعنوان اجزای پایۀ سیستم مبتنی بر رانش و انتخاب راهکار و مدل مرجع [21] برای حل مسئلۀ این پژوهش، چند نکته مهم درخور ذکر است: نخست اینکه این راهکار بین رانش و ناهنجاری تمایزی قائل نیست و رانش، مفهوم را بهعنوان ناهنجاری شناسایی میکند؛ زیرا واحد تشخیص رانش مفهوم ندارد و خطای باقیماندۀ کل، مبنای تشخیص انحراف است که تمایزی بین تغییرات ناشی از رانش مفهوم و ناهنجاری قائل نمیشود. نکتۀ دوم به دلیل ناآگاهی از بروز رانش، در همۀ گامهای زمانی، تطبیق با تغییرات یا همان یادگیری ماتریسهای زیرفضا تکرار میشود. این در حالیست که محاسبۀ این ماتریسها بسیار پُرهزینه است. بر اساس این، برای رفع موانع فوق، چارچوب پیشنهادی این مقاله با عنوان ردیاب برخط استوار تطبیقپذیر آگاهانه[13]، IAROST، شامل سه واحد یادگیری، تشخیص رانش مفهوم و تشخیص ناهنجاری تشریح میشود.
یکی از الزامات یادگیرندۀ برخط رانش - آگاه در یک محیط تغییرپذیر، وجود مکانیزم تشخیص رانش مفهوم بهصورت صریح و مجزا از ناهنجاری است [8]. این مکانیزم اطلاعات مفیدی را در ارتباط با پویایی دادهها فراهم میکند. در این بخش، مکانیزم پیشنهادی تشریح میشود.
با توجه به اینکه دو ماتریس A’ وC’ در رابطه (2) انحرافات در زیرفضای اصلی را نشان میدهند، بهترین نشانه برای رانش مفهوم در دادهها هستند. همچنین اندازۀ بزرگی این ماتریسها شدت رانش را نشان میدهد. بدین ترتیب، مکانیزم زیر برای پایش این ماتریسها و اعلام وقوع رانش مفهوم طراحی شده است. با توجه به توضیحات مدل رابطه (2) در محاسبۀ زیرفضای اصلی و استفاده از مکانیسم فراموشی تدریجی، رانش مفهوم ناگهانی و افزایشی بهراحتی با این روش تشخیص داده میشود. رانش متناوب تنها در صورتی شناسایی میشود که در دادۀ اخیر در محدودۀ تنطیمات فاکتور فراموشی بهوفور الگوی متناوبی اتفاق افتاده باشد و امکان آموختن آن فراهم باشد که در این مقاله به آن پرداخته نمیشود.
با توجه به اینکه هر ستون از ماتریسهای A’ وC’ به یک مؤلفه در داده اشاره دارد، اعمال نرم L2.1 بهصورت بر روی این ماتریسها سنجۀ مناسبی برای اندازهگیری میزان تغییرات است؛ بنابراین، در هر گام زمانی، این نرم، محاسبه و سری زمانی حاصل از آن بهمنظور تشخیص قله[14]، پایش میشود. سریهای زمانی بهدستآمده بهصورت برخط با الگوریتم smoothed z-score[22] تحلیل میشوند. این الگوریتم با ورود دادۀ جدید در سری زمانی، میزان انحراف آن نقطه را نسبت به میانگین متحرک به طول m محاسبه میکند. در صورتی که z-score بهدستآمده از مقدار حد آستانه بیشتر باشد، یک قله گزارش میشود. میانگین متحرک (s) و انحراف از معیار (σ) طبق روابط زیر محاسبه میشوند:
(3) |
|
(4) |
|
با توجه به اینکه یک قله ممکن است از تشخیص قلههای بعدی جلوگیری کند، قبل از بهروزرسانی میانگین متحرک و انحراف معیار، لازم است دادۀ جدید با رابطۀ زیر فیلتر شود:
(5) |
|
بدین ترتیب، دادۀ جدید بهوسیلۀ مقدار خواندهشدۀ فعلی و مقدار فیلترشدۀ قبلی تعدیل میشود. در این رابطه میزان مصالحه بین دو نقطه دادۀ جاری و قبلی را تعیین میکند. بر اساس این، با اعلام قله توسط این الگوریتم، وقوع رانش مفهوم گزارش میشود. شکل (2) شبهکد این الگوریتم را نشان میدهد.
براساس ویژگیهای قلب یک سیستم یادگیری مبتنی بر رانش طبق شکل (1) و با استناد به رابطه (2)، حالت یادگیری بهصورت برخط است.
ویژگی دوم مربوط به تطبیقپذیری مدل است که نحوۀ سازگاری مدل در مواجهه با دادههای جدید را مشخص میکند. همانطور که قبلاً گفته شد در رویکردهای یادگیری تحت رانش، دو استراتژی عمده تطبیقپذیری معرفی شده است، کورکورانه و آگاهانه. استراتژی کورکورانه در واکنش به رانش بهصورت پیشگیرانه[15] و کند عمل میکند. علاوه بر این، به دلیل بهروزرسانی منظم مدل در هر گام زمانی، بسیار هزینهبر و زمانبر است؛ در حالی که یک استراتژی آگاهانه، بهصورت واکنشی[16] عمل میکند و در هر گام زمانی، وقوع رانش را بررسی و در صورت مثبتبودن، فرآیند تطبیق مدل با دادۀ جدید انجام میشود. در این حالت، مدل فقط در صورت نیاز بهروز میشود؛ بنابراین، این استراتژی کارآمدتر است. یکی دیگر از مزایای یک استراتژی آگاهانه، ارائۀ اطلاعات دربارۀ پویایی فرآیند تولید داده است. این پژوهش، یک استراتژی آگاهانه برای تطبیقپذیری ردیاب برخط و استوار زیرفضا در مواجهه با رانش ارائه میکند.
اولین نیاز برای یک سیستم تطبیقپذیر آگاهانه، فراهمسازی سازوکار پایش و هشدار است تا تنها در زمان وقوع رانش، فرآیند تطبیقپذیری را فعال کند. در بخش قبل، پایش اندازۀ ماتریسهای A’ وC’ در واحد تشخیص رانش مفهوم تشریح شد. وقتی وقوع رانش با این واحد اعلام شد، روال بهروزرسانی ماتریسهای A و C فراخوانی میشود. در این حالت، محاسبۀ هزینهبر و سنگین این ماتریسها که همان زیرفضای اصلی و الگوی اصلی دادهها هستند، تنها در زمان وقوع رانش انجام میشود. شکل (3) الگوریتم مربوط به فرآیند یادگیری راهکار پیشنهادی را نشان میدهد.
ویژگی سوم یک یادگیرنده در سیستمهای مبتنی بر رانش این است که فرآیند یادگیری با استفاده از یک یادگیرندۀ واحد انجام میشود یا ترکیبی از چندین یادگیرنده. در این پژوهش، یک یادگیرندۀ واحد در نظر گرفته شده است که با گذشت زمان تکامل مییابد.
با توجه به اینکه ماتریس V، بخش خلوت را نشان میدهد، اندازۀ بزرگی آن، سنجۀ خوبی برای تعیین زمان بروز ناهنجاری است. با استفاده از الگوریتم smoothed z-score، استفادهشده در شکل (2)، سری زمانی حاصله از نرم دو ماتریس V (سنجۀ اندازۀ بزرگی ماتریس بهصورت ) پایش و با شناسایی یک قله، بروز ناهنجاری، اعلام و محرک لازم به واحد تشخیص ناهنجاری صادر میشود تا یال و گره ناهنجار تعیین شوند؛ بدین شکل که ضمن اعمال تابع z-score روی ماتریس V، درایههای با بیش از مقدار آستانه δ، یال ناهنجار اعلام میشوند. همچنین، بهمنظور تشخیص گرههای ناهنجار، نُرم دو هر ردیف از ماتریس، محاسبه و با اعمال تابع z-score موارد بیش از حد آستانه δ اعلام میشوند. با این روال، بهصورت برخط، در هر گام زمانی با کمترین هزینه، موارد ناهنجار شناسایی و اعلام میشوند. شکل (3) شبه کد این بخش را نشان میدهد.
الگوریتم روش پیشنهادی بهطور کامل در شکل (4) نمایش داده شده است. با توجه به شکل (4)، با دریافت داده جدید در گام زمانی t، متغیرهایb[t] ، V[t] ، A’[t] و C’[t] طی فرآیند یادگیری محاسبه میشوند. در ادامه، بهمنظور تشخیص رانش مفهوم، A’[t] و C’[t] با الگوریتم تشخیص رانش مفهوم پایش میشوند. وقتی یک قله شناسایی میشود، ضمن اعلام وقوع رانش، متغیر Triger سیگنال فعالسازی بخش تطبیقپذیری در واحد یادگیری را برای بهروزرسانی و تطبیق ماتریسهای A و C صادر میکند. علاوه بر این، اندازۀ ماتریس V، با الگوریتم تشخیص قله پایش میشود. هنگامی که یک قله شناسایی شد، Triger، فعال و الگوریتم تشخیص ناهنجاری، فراخوانی میشود تا عوامل ناهنجار را شناسایی و اعلام کند. شکل (5) شبهکد کامل این الگوریتم را نشان میدهد.
بدین ترتیب، نویز با تحلیل خطای کل حاصل از تخمین، ناهنجاری ازطریق تحلیل ماتریس خلوت V در بخش تشخیص ناهنجاری و رانش مفهوم با واحد تشخیص رانش، بهصورت مجزا از هم تعیین میشوند. درنهایت، همانگونه که ادعا شد و الگوریتم پیشنهادی نیز تأیید میکند، تنها با پسپردازشهای ساده و کمهزینه روی متغیرهای مدل در هر گام زمانی، بهطور خودکار و همزمان ناهنجاری و رانش مفهوم بهصورت مجزا و برخط تشخیصپذیر و تفکیکشدنیاند.
در این بخش، ابتدا توانایی یادگیرندۀ روش پیشنهادی از جنبۀ همگرایی و تطبیقپذیری بررسی میشود. سنجۀ استفادهشده برای ارزیابی، سری زمانی ساختهشده از محاسبۀ خطای باقیماندۀ نرمالشده (NRE[17]) براساس رابطه زیر است:
(6) |
|
Yt نمونۀ دادۀ دریافتی در زمان جاری و Xt تخمین رتبۀ پایین انجامشده با مدل است. هر چقدر مقدار این سنجه بیشتر باشد، نشاندهندۀ این است که مدل در تخمین دادۀ واقعی، خطای بیشتری داشته است. اگر میزان این خطا با نرخ بیشتری بعد از تغییرات کاهش یابد، نشان از سرعت بیشتر در یادگیری و تطبیقپذیری مدل با تغییرات دارد. مقدار خطای میانگین در حال اجرا در گام زمانی آخر، نمایش عددی از توان همگرایی مدل است که طبق رابطه زیر محاسبه میشود.
(7) |
|
یکی از بزرگترین مشکلات حوزۀ تشخیص ناهنجاری، وجود مجموعهداده برچسبدار برای ارزیابی است. بهسختی میتوان یک مجموعه دادۀ جریانی در حال تکامل از یک شبکه پیدا کرد که با دقت رضایتبخشی برچسبگذاری شده باشد. یکی از راههای متدوال، ساخت مجموعهدادۀ انسانی است که علاوه بر هزینهبربودن، به دلیل خطای بالای «هشدار نادرست» چندان کارآمد نخواهد بود. علاوه بر این، به دلیل کمبودن تعداد ناهنجاری در دادهها، امکان ارزیابی روشها از جنبههای مختلف و درمقابل، انواع مختلف ناهنجاری بهخوبی فراهم نمیشود. یکی از راهکارهای دیگر برای ساخت مجموعه دادۀ آزمایشی، براساس تحقیقات مختلف و استفاده از داده تمیز و تزریق ناهنجاری به آن است.
بدین منظور، مجموعهدادههای گراف مربوط به سفر تاکسیهای نیویورک بین 71 ناحیه در ژانویه 2013 انتخاب میشوند و در مرحلۀ اول، تابع موجک Daubechies-5 روی سیگنال حاصل از وزن هر یک از یالهای گراف در طول زمان (تکامل وزن یال در زمان) اعمال میشود تا نمودار حاصله هموار شود. در مرحلۀ دوم، برش زمانی از مجموعهداده انتخاب میشود که روند تقریباً هموار و یکنواختی دارد. در مرحلۀ سوم، تجزیه CP اعمال میشود تا فاکتورهای پایه استخراج شوند. در ادامه، تابع زمان مربوط به هر سیگنال با استفاده از تکنیکهای برازش منحنی، استخراج و روی فاکتورهای پایه اعمال میشود. در انتها نویز گوسی به دادهها اعمال میشود. به این شکل، ابتدا دادۀ تمیز با پایۀ دادۀ واقعی تولید میشود.
برای تزریق یال ناهنجار به مجموعه فوق، در زمانهای 50، 125 و 150 تعدادی از درایههای ماتریس، معادل یالها در شبکه، انتخاب میشوند و وزن آنها به مقدار دیگری تغییر میکند. میزان این تغییر با یک فاکتور ضربی، تنظیمشدنی است. با مقادیر مختلف این فاکتور، ناهنجاریهایی با میزان انحراف متفاوت به مجموعهداده تزریق میشوند. در این تحقیق، فاکتور ضربی بین مقدار 0.5 تا 1.5 در نوسان بوده است.
برای تزریق گره ناهنجار به شبکه، در گامهای زمانی 70 و 200 تعداد محدودی از گرههای شبکه انتخاب میشوند و وزن ده درصد از یالهای متصل به آنها متناسب با فاکتور ضربی تغییر داده میشود. بهمنظور تغییر زیرفضا، روال زیر در گامهای زمانی 100، 250 و 300 در پیش گرفته شد. تنها 2 درصد از عناصر مربوط به ماتریس فاکتورهای اصلی انتخاب شد و مقادیر آنها براساس فاکتور ضربی تغییر داده شدند. سپس ماتریسهای فاکتور جدید برای بازسازی و تولید دادۀ جدید استفاده شدند. در انتها با مقایسۀ دادهها، همۀ یالهای تأثیرگرفته از این فرآیند تعیین شدند و بهعنوان یالهای ناهنجاری برچسب خوردند که بهصورت گروهی باعث تغییر زیرفضا شدهاند.
روشهای مقایسهپذیر انتخابی برای این بخش باید از بین راهکارهای مبتنی بر تجزیۀ تانسور یا ماتریس باشند که با دو استراتژی ضمنی یا صریح، رانش را مدیریت میکنند. بیشتر روشهای ارائهشده رانش مفهوم را بهصورت ضمنی مدیریت میکنند. همچنین، تحقیقاتی که بهطور همزمان به تشخیص ناهنجاری و رانش پرداخته باشند، بسیار اندکاند. مرتبطترین راهکار SMF[12] است که مدل برخط مبتنی بر تجزیۀ ماتریسی ارائه داده و امکان رانش مفهوم و تشخیص ناهنجاری را بهصورت ضمنی و غیرخودکار فراهم ساخته است. روشهای OLSTEC[23]، OSTD[24] و TeCPSGD[15] روشهای دیگریاند که بحث رانش یا تغییر زیرفضا را بهصورت ضمنی انجام میدهند و برای تجهیز تشخیص ناهنجاری، نسخه استوار آنها در این مقاله طراحی و پیادهسازی شد. برای ایجاد شرایط یکسان برای همۀ الگوریتمها، مقادیر پارامترهای λ1 و μ به 0.4 و 0.1 تنظیم شدهاند. گام آموزش یا stepsize در الگوریتم TeCPSGD به مقدار0.1 براساس دستورالعمل ذکرشده در [25] تنظیم شد. λ2 در روش پیشنهادی براساس دستورالعمل [23] به 0.1× λ1=0.04 و با توجه به دانش اولیه از میزان همواربودن دادهها، پارامتر lag به 10 مقداردهی شدند. مقدار δ به مقدار معمول، یعنی عدد 3 تنظیم شده است؛ البته مقادیر مختلف در محاسبات مربوط به جدول (3)، ارزیابی شدند.
نتایج NRE بهدستآمده از اجرای الگوریتمها در شکل (6) نشان داده شدند.
شکل (6): نمودار خطای باقیماندۀ نرمالشدۀ همۀ روشها
با توجه به شکل (6)، کلیۀ روشها در نقاط مربوط به ناهنجاری (گامهای زمانی 50، 70، 125، 150 و 200) و رانش مفهوم (نقاط زمانی 100 ، 250 و 30) دچار خطا شدهاند؛ به این دلیل که در داده تغییر ایجاد شده است؛ اما نکتۀ درخور توجه، تفاوت بین ناهنجاری و رانش است. خطای بهوجودآمده در ناهنجاری لحظهای و نقطهای است؛ اما خطای مربوط به نقاط رانش مفهوم، طولانیترند؛ زیرا مدت زمانی طول میکشد تا مدل، الگوی جدید را آموزش ببیند؛ اما روش پیشنهادی زودتر از بقیه همگرا شده و زودتر از بقیه تغییر در الگو را آموزش دیده است. در این میان، روشهای OSTD و SMF کمترین انعطاف را در مقابل رانش مفهوم دارند؛ زیرا نتوانستهاند همگرا شوند. همچنین، با استناد به اینکه روش TeCPSGD مبتنی بر کاهش در امتداد گرادیان است، همگرایی مطلوبی در نقاط رانش مفهوم ندارد.
بهمنظور بررسی دقیقتر عملکرد روش پیشنهادی، آزمایشات بیشتری برای مجموعهدادههای جدول (1) انجام شدهاند و مقدار خطای میانگین در حال اجرا، طبق رابطه (7) در جدول (2) ثبت شد. براساس نتایج، روش پیشنهادی با خطای بسیار کمتری همگرا شده و فرآیند یادگیری را بهتر انجام داده است. با استناد به نتیجۀ مشاهدهشده در شکل (6) و تعمیم آن، خطای کمتر به دلیل همگرایی سریعتر روش پیشنهادی در نقاط رانش است.
در ادامه، برای نشاندادن عملکرد تشخیص رانش مفهوم بهصورت ملموس و شهودی، روش پیشنهادی روی دادۀ ویدئویی بهعنوان یک دادۀ جریانی دنیای واقعی پیادهسازی شد و نتایج تجزیهوتحلیل شدند.
در حوزۀ پردازش ویدئو، شاخهای با عنوان جداسازی پسزمینه[18] وجود دارد که در یک جریان ویدئو، اشیای متحرک (پیشزمینه) را از پسزمینه جدا میکند. اشیای پیشزمینه معمولاً شامل تعداد کمی از پیکسلها در یک فریم فیلماند که بهعنوان ناهنجاری در نظر گرفته میشوند [26].
یک دادۀ ویدئویی در قالب جریانی از فریمها و بهعنوان یک توالی طولانی از تصویر، در قالب یک تانسور، مدل و بهصورت برخط و فریم به فریم پردازش میشود. به این ترتیب، برخی از رویکردهای برخط مبتنی بر ردیابی زیرفضایی استوار ارائه شدهاند که پسزمینه را بهعنوان زیرفضای اصلی یا دادۀ رتبۀ پایین و اجسام متحرک را بهعنوان یک بخش خلوت، مدل و ناهنجاری اعلام میکنند [24], [27].
با تغییر پسزمینه در ویدئو، زیرفضای اصلی در طول زمان تغییر میکند؛ بنابراین، یک ردیاب برخط و استوار زیرفضا لازم است تا تغییرات پسزمینه را مدیریت کند. بهتازگی روشی برای تعدیل و تطبیق یادگیرنده با تغییرات پسزمینه معرفی شده است؛ اما این روش، توانایی تشخیص و اعلام رانش را ندارد.
رانش مفهوم در یک جریان ویدئویی بهعنوان یک نقطۀ زمانی است که در آن پسزمینه تغییر میکند. در ادامه، الگوریتم IAROST روی یک جریان ویدئویی با پسزمینۀ پویا به نام “Airport hall” از مجموعهداده “I2R”[28] اعمال میشود تا عملکرد الگوریتم از جنبۀ یادگیری و تشخیص رانش مفهوم ارزیابی شود. این ویدئو شامل 500 فریم با اندازه 288 × 352 است. رانش مفهوم یا تغییر پسزمینه در سه بازه زمانی شامل فریمهای 38 تا 113، فریمهای 190 تا 265 و فریمهای 342 تا 417 رخ میدهد. روش پیشنهادی برای تشخیص رانش مفهوم بر مجموعهداده اعمال شد. شکل (7) بهترتیب سری زمانی دو شاخص رانش مربوط به ماتریسهایA’ وC’ را نشان میدهد. سه ناحیۀ نشان داده شده در این شکل، مطابق با قلههای تشخیص داده شده در واحد تشخیص رانش مفهوم و فواصل زمانی حرکات پسزمینه است. بدین ترتیب، نتایج بهدستآمده توانایی روش پیشنهادی را برای تشخیص رانش مفهوم بهصورت صریح تأیید میکند.
تشخیص ناهنجاری همزمان با رانش و تفکیک این دو از یکدیگر بهصورت برخط و خودکار، یکی از مهمترین دستاوردهای IAROST است. بر اساس این، انتظار میرود IAROST خطای کمتری در تشخیص هشدار نادرست و درنتیجه، عملکرد بهتری نسبت به روشهای دیگر داشته باشد. بدین منظور، در ادامه، توانایی آن در تشخیص ناهنجاری با همتایش BAROST[21] ارزیابی میشود که مدل مشابه اما رویکرد کورکورانه دارد.
با توجه به نادربودن نمونههای ناهنجار (کلاس مثبت) در مقایسه با نمونههای عادی (کلاس منفی)، مجموعهداده بسیار نامتوازن است؛ بنابراین، لازم است معیاری برای ارزیابی انتخاب شود که به کلاس نادر اهمیت بیشتری دهد. دقت[19] و فراخوانی[20] بهعنوان دو سنجه عملکرد مناسب و F-measure بهعنوان میانگین هارمونیکی آنها بهطور معمول استفاده میشوند. در ادامه، مقادیر F-measure مربوط به حد آستانههای مختلف، در جدول (3) نشان داده شدهاند. مقادیر بیشتر این سنجه در روش IAROST، کارایی بیشتر آن را در تشخیص ناهنجاری تأیید میکند.
جدول (3): سنجه F-measure در مقادیر مختلف حد آستانه در تشخیص ناهنجاری با دو روش IAROST و BAROST
BAROST |
IAROST |
مقدار حد آستانه |
0.6645 |
0.8016 |
1 |
0.6484 |
0.478 |
2 |
0.5935 |
0.6731 |
3 |
0.5513 |
0.6246 |
4 |
0.5547 |
0.6241 |
5 |
0.5663 |
0.6223 |
6 |
0.5787 |
0.6322 |
7 |
0.5754 |
0.611 |
8 |
0.575 |
0.6062 |
9 |
0.4661 |
0.9437 |
10 |
علاوه بر این، سنجۀ کشف هشدار نادرست یا FPD براساس رابطه زیر محاسبه میشود تا بهطور صریحتر و واضحتر امکان ارزیابی و مقایسۀ دو روش را فراهم کند.
(8) |
|
مقدار کمتر برای FPD نشاندهندۀ مقدار کمتر هشدار نادرست و کارایی بهتر است. مقادیر این سنجه برای دو روش IAROST و BAROST در جدول (4) بهازای سطوح مختلف حدآستانه نمایش داده شدهاند. همانطور که نتایج نشان میدهد IAROST عملکرد بهتری داشته است؛ بنابراین، تشخیص همزمان رانش و ناهنجاری و تفکیک این دو از یکدیگر، بهطور مستقیم کارایی سیستم را در تشخیص ناهنجاری افزایش میدهد.
جدول (4): مقدار FPD در حد آستانه های متفاوت
مقدار حد آستانه |
IAROST |
BAROST |
1 |
0.3221 |
0.4975 |
1.5 |
0.3198 |
0.4771 |
2 |
0.3228 |
0.4738 |
2.5 |
0.3391 |
0.4842 |
3 |
0.3393 |
0.4751 |
در این مقاله، راهکاری مبتنی بر ردیابی برخط و استوار زیرفضا ارائه شده است که بهطور همزمان و خودکار رانش مفهوم و ناهنجاری را در دادۀ جریانی تشخیص میدهد. در این مقاله، یک آشکارساز تشخیص رانش مفهوم، طراحی شده است که علاوه بر اعلام وقوع رانش، اطلاعات مفیدی دربارۀ پویایی دادهها در اختیار قرار میدهد. مهمترین دستاورد تفکیک رانش مفهوم و ناهنجاری از یکدیگر، کاهش درخور توجه میزان تشخیص هشدار نادرست روش پیشنهادی در تشخیص ناهنجاری است. نتایج بهدستآمده از آزمایشها روی یک دادۀ ویدئویی، توانمندی روش پیشنهادی را در تشخیص رانش مفهوم تأیید میکند.
علاوه بر این، وجود آشکارساز رانش به طراحی مکانیزمی آگاهانه برای تطبیقپذیری یادگیرنده با رانش مفهوم منجر شده است؛ بنابراین، تنها در مواقع ضرورت، فرآیند پرهزینۀ یادگیری الگوهای اصلی انجام میشود.
این مقاله در کارهای آتی میتواند از ابعاد مختلف، ازجمله امکان تشخیص ناهنجاریهای ساختهیافتهتر در دادهها یا حل مسئلۀ بهینهسازی با روشهای دیگر بهمنظور افزایش سرعت یادگیرنده توسعه یابد.
شکل (1): واحدهای اصلی یک سیستم یادگیری تحت رانش مفهوم [8]
Peak Detection Procedure |
Trigger=0 If t>lag Calculating zt for according to equation (3) If obtained zt >threshold Trigger=1 End if Calculate st according to equation (5) Calculating new mean and variance according to equation (4) End if Output: Trigger |
شکل (2): الگوریتم شناسایی قله
Anomaly Detection Procedure |
Input Vt,𝛅 Apply Zscore on vectorized Vt For each element of Vt if the connected edge between l and w is returned as anomalous end if end for Output: list of anomalous edges |
شکل (3): روال تشخیص ناهنجاری
شکل (4): نمودار مربوط به الگوریتم روش پیشنهادی
Informed Adaptive Robust Online Subspace Tracking |
Input: Initialize: For t=1,2,…. Do Calculating b[t], V[t], A[t]’, C[t]’ according to [21] |
Drift Detection and adaptation |
SignalA[t]= ℓ2.1-norm of A’ SignalC[t]= ℓ2.1-norm of C’ Apply peak detection procedure on SignalA (Monitoring A’) and return triggerA Apply peak detection procedure on SignalC (Monitoring C’) and return triggerC If triggerA or terrigerC=1 Current time point is returned as drift Adaptation is performed by updating the main subspace A and C %( calculating A and C according to appendix) End if |
Anomaly Detection |
SignalV[t]= ℓ2-norm of V Apply peak detection procedure on SignalV (Monitoring V) If trigger=1 Call anomaly detection procedure End if End for |
شکل (5): شبهالگوریتم روش پیشنهادی
جدول (1): فهرست مجموعهدادههای استفادهشده
عنوان |
تعداد گرهها |
شرح |
NYC Taxi [29] |
71 |
سفرهای بین 71 ناحیه شهری نیویورک توسط تاکسیهای زرد در ژانویه 2013 |
Boston Bike-Sharing [6] |
95 |
سفرهای مربوط به دوچرخههای اشتراکی در شهر بوستون در بازه زمانی 28 جولای 2011 تا آخر سپتامبر 2012 |
Enron [30] |
148 |
تعاملات کاربران با پست الکترونیکی در بازه زمانی بین سالهای 1998 تا 2002 |
Trade [31] |
200 |
حجم تبادلات تجاری سالانه بین کشورها در بازه زمانی 1870 تا 2009 میلادی |
Immigration [32] |
222 |
مهاجرت بین کشورها در یک دوره پنج ساله |
Car [33] |
771 |
سفرهای مربوط به روزهای کاری وسائل نقلیه ظرفیت بالا (HOV) در پاسادنا و حومه |
جدول (2): خطای میانگین در حال اجرای مربوط به روشهای مختلف روی کلیۀ مجموعهدادهها
عنوان |
NYC Taxi [29] |
Boston Bike-Sharing |
Enron |
Trade |
Immigration |
Car |
IAROST |
0.035 |
0.1 |
0.020 |
0.025 |
0.025 |
0.026 |
SparseOLSTEC |
0.067 |
0.14 |
0.060 |
0.046 |
0.041 |
0.051 |
TeCPSGD |
0.154 |
0.18 |
0.168 |
0.216 |
0.138 |
0.126 |
OSTD |
0.262 |
0.213 |
0.061 |
0.050 |
0.074 |
0.06 |
SMF |
0.391 |
0.31 |
0.075 |
0.067 |
0.143 |
0.063 |
شکل (7): تشخیص رانش مفهوم در قالب جابهجایی پسزمینه در مجموعهداده “Airport hall”
[1] تاریخ ارسال مقاله: 07/10/1399
تاریخ پذیرش مقاله: 21/04/1400
نام نویسندۀ مسئول: بهروز مینایی بیدگلی
نشانی نویسندۀ مسئول: ایران - تهران - دانشگاه علم و صنعت ایران - دانشکده مهندسی کامپیوتر
[1] Main subspace
[2] Robust
[3] Sparse
[4] Temporal Matrix Factorization
[5] Seasonal Matrix Factorization
[6] Rank
[7] Blind
[8] Drift aware
[9] Informed
[10] Order
[11] Robust Online Subspace Tracker
[12] Low rank
[13] Informed Adaptive Robust Online Subspace Tracker
[14] Peak
[15] Proactive
[16] Reactive
[17] Normalized Residual Error
[18] Background Subtraction
[19] Precision
[20] Recall