ارائۀ یک یادگیرندۀ برخط رانش آگاه برای تشخیص ناهنجاری در داده‌های جریانی

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

1 دانشجوی دکترا گروه مهندسی نرم افزار، دانشکده مهندسی کامپیوتر- دانشگاه علم و صنعت- تهران- ایران

2 دانشیار گروه مهندسی نرم افزار، دانشکده مهندسی کامپیوتر- دانشگاه علم و صنعت- تهران- ایران

3 استادیار مرکز تحقیقات سیستمهای هوشمند کاربردی - دانشگاه هالمستاد- هالمستاد- سوئد

4 دانشیار گروه علوم کامپیوتر، دانشکده علوم ریاضی - دانشگاه تربیت مدرس- تهران- ایران

چکیده

داده‌های جریانی در بستر پویا و در حال تغییر، تکامل می‌یابند؛ بنابراین، رانش مفهوم یا تغییر توزیع اساسی داده‌ها با گذشت زمان، یکی از مهم‌ترین چالش‌های این نوع از داده‌ها است. علاوه بر این، رانش مفهوم بر عملکرد فرآیند تشخیص ناهنجاری نیز تأثیر می‌گذارد. تشخیص ناهنجاری در چنین داده‌هایی در حوزه‌های متعددی ازجمله تشخیص نفوذ در شبکه‌های کامپیوتری  یا مدیریت ترافیک شبکۀ راهها کاربرد دارد. در سال‌های اخیر، رویکردهایی مبتنی بر تجزیۀ تانسور ارائه شده‌اند که به‌صورت برخط زیرفضا را ردیابی می‌کنند و یادگیرنده را با یک استراتژی ناآگاهانه و به‌طور ضمنی در همۀ گام‌های زمانی، در مقابل تغییرات تطبیق می‌دهند. این مقاله، یک رویکرد برخط را پیشنهاد می‌کند که رانش مفهوم را به‌طور صریح تشخیص می‌دهد و اعلام می‌کند. بدین ترتیب یادگیرنده نیز با یک استراتژی آگاهانه و تنها در گام‌های زمانی لازم با تغییرات و رانش، تطبیق پیدا می‌کند. ارزیابی راهکار پیشنهادی با استفاده از مجموعه‌داده‌های واقعی انجام شد و تحلیل نتایج به‌دست‌آمده، عملکرد روش پیشنهادی را از جنبه‌های یادگیری و تشخیص تأیید می‌کند.

کلیدواژه‌ها


عنوان مقاله [English]

A Drift-Aware Online Learner for Anomaly Detection from Streaming Data

نویسندگان [English]

  • Maryam Amoozegar 1
  • Behrouz Minaei-Bidgoli 2
  • Hadi Fanee 3
  • Mansour Rezghi 4
1 Dept. of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
2 Dept. of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
3 Center for Applied Intelligent Systems Research (CAISR), Halmstad University, Halmstad, Swede
4 Dept. of Computer Science, Tarbiat Modares University, Tehran, Iran
چکیده [English]

Streaming data has been evolved in a dynamically changing and evolving environment. Therefore, concept drift or changing the underlying distribution of data over time is considered as an important challenge in processing this type of data. Moreover, concept drift affects the performance of anomaly detection process. The problem of anomaly detection in streaming data is applied to many important applications, for instance, intrusion detection in computer networks or traffic management in the road networks. In recent years, some tensor decomposition based approaches have been presented that track the main pattern or subspace of data in an online manner and adapt the learner with probabilistic changes continuously in all time-intervals by using an implicit strategy. We propose an online approach that detects the concept drift in an explicit manner. Moreover, the learner has been adapted with drift and changes only in their occurrences using informed strategy. Evaluation of the proposed method is performed with real datasets. Analysis of the obtained results confirms the promising performance of the proposed method in terms of learning and detection.

کلیدواژه‌ها [English]

  • anomaly detection
  • informed and blind adaptation
  • tensor decomposition
  • concept drift
  • robust online subspace tracker
    • مقدمه[1]

    یکی از مهم‌ترین مسائل در حوزۀ داده‌کاوی، تشخیص ناهنجاری در داده‌ها است. [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] و تنها در نقاط رانش، به‌روز و در فرآیند پرهزینۀ یادگیری صرفه‌جویی می‌شود.

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

    در ادامه، مفاهیم پایه در بخش دوم مرور می‌شوند. روش پیشنهادی در بخش سوم و آزمایشات انجام‌شده به همراه نتایج به‌دست‌آمده در بخش بعدی ارائه می‌شوند. نتایج و معرفی کارهای آینده در بخش انتهایی ارائه می‌شوند.

     

    2- مفاهیم پایه

    2-1- یادگیری تحت رانش مفهوم

    اگر فرآیندی که به تولید دادۀ جریانی منجر می‌شود با متغیر تصادفی χ مدل شود، رانش مفهوم به‌صورت «تغییر در احتمال توزیع متغیر تصادفی تحت زمان» [16] تعریف می‌شود. در یادگیری باناظر، متغیر تصادفی χ به شکل XY (X مجموعه صفات و Y متغیر هدف) و رانش مفهوم به معنی تغییر در توزیع تجمعی X و Y است؛ اما در یادگیری بی‌ناظر متغیر تصادفی تنها شامل X است و متغیر هدف یا برچسبی وجود ندارد [18]. در روش‌های مبتنی بر تجزیۀ تانسور برخط، مفهوم همان ساختار مخفی موجود در داده است [16].

    در ادامه، واحدهای سازندۀ یک سیستم یادگیری بی‌ناظر تحت رانش مفهوم برگرفته از [8] تشریح می‌شوند. نخستین بخش، واحد حافظه است که دو وظیفۀ مدیریت داده ورودی و کنترل مکانیسم فراموشی را به عهده دارد. دادۀ ورودی می‌تواند به‌صورت تک‌نمونه یا تجمعی (مبتنی بر پنجره) مدیریت شود. مکانیسم فراموشی نیز به‌صورت تدریجی یا ناگهانی برای کنترل اثر داده‌های قدیمی بر مدل اعمال شود. دومین بخش، واحد مدیریت تغییرات، مسئولیت پایش تغییرات و اعلام وقوع رانش را برعهده دارد.

    قلب سیستم نیز واحد یادگیری است که سه ویژگی عمده دارد؛ ویژگی نخست، حالت یادگیری را مشخص می‌کند و مشخص می‌کند با رسیدن دادۀ جدید، یادگیری از نو آغاز و مدل جدید ساخته شود یا روش‌های یادگیری افزایشی، برخط یا جریانی استفاده شوند تا به‌طور تدریجی، فرآیند یادگیری تکمیل شود. ویژگی دوم، تطبیق‌پذیری را مشخص می‌کند. واحد یادگیری در این بخش، استراتژی خود را برای تطبیق با تغییرات تعیین می‌کند. اصولاً دو استراتژی کورکورانه و آگاهانه تعریف شده است. در حالت کورکورانه، یادگیرنده به‌طور ضمنی و در یک فرآیند پیوسته، تطبیق با تغییرات احتمالی را انجام می‌دهد؛ بدون اینکه هیچ آگاهی از وقوع رانش داشته باشد. این استراتژی ناآگاهانه و پُرهزینه است. در طرف مقابل، سیستم‌های با استراتژی آگاهانه یا رانش - آگاه، با واحد تشخیص رانش در ارتباط است و فرآیند تطبیق و به‌روزرسانی یادگیرنده، تنها در صورت به‌روز رانش انجام می‌شود. توجه به این نکته نیز حائز اهمیت است که در ادبیات این حوزه، گاهی روش کورکورانه را یادگیری تکاملی و روش آگاهانه را یادگیری خود - تطبیقی می‌نامند [19]. ویژگی سوم واحد یادگیرنده نیز مشخص می‌کند یادگیرنده از یک مدل بهره می‌برد یا مبتنی بر چندین مدل و یادگیری تجمعی بنا شده است.

    2-2- تجزیۀ تانسور

    تانسور یک آرایۀ چندبعدی است که مرتبه[10] آن بیان‌کنندۀ تعداد ابعاد آن است. تانسور مرتبه یک معادل یک بردار، تانسور مرتبه دو معادل ماتریس و تانسور برای اشاره به تانسورهای با مرتبه سه و بالاتر استفاده می‌شود. بدین ترتیب، تانسور یک ابزار قدرتمند برای پردازش داده‌ها از جنبه‌های مختلف است؛ برای نمونه، تعامل افراد در یک شبکۀ اجتماعی در بستر زمان در قالب یک تانسور با سه بعد کاربر، کاربر و زمان مدل می‌شود.

    روش‌های تجزیۀ تانسور، ابزار قدرتمندی برای پردازش اینگونه داده‌ها هستند که زیرفضای اصلی و به‌عبارتی الگوهای معنادار را استخراج می‌کنند. پرکاربردترین تجزیۀ تانسوری تجزیه CANDECOMP/PARAFAC (CP) است که طبق رابطه زیر تانسور χ (L×W×T) را به ماتریس فاکتورهایش یعنی ، و  تجزیه می‌کند [20].  

    (1)

     

    2-1- ردیاب برخط و استوار زیرفضا[11]

    در دستۀ مهمی از روش‌های تشخیص ناهنجاری، داده‌های بعد بالا را به زیرفضای با رتبه پایین[12] نگاشت می‌کنند؛ به گونه‌ای که در فضای جدید، ناهنجاری‌ها به‌راحتی تشخیص داده می‌شوند. این مسئله با عنوان یادگیری زیرفضا (یا تخمین رتبه پایین) یا تخمین آنها شناخته می‌شود. یادگیری زیرفضا در محیط نویزی را یادگیری استوار زیرفضا می‌نامند که تخمین به دو مؤلفۀ زیرفضا و مؤلفۀ خلوت انجام می‌شود. این مفاهیم در داده جریانی که داده‌ها به‌صورت یکجا در اختیار نیستند، مفهوم ردیابی برخط زیرفضا را پیدا می‌کنند؛ زیرا فرآیند یادگیری با به‌روزرسانی و ردیابی زیرفضا در زمان انجام می‌شود. در اینجا نیز در حضور نویز، هم زیرفضا و هم مؤلفۀ خلوت ردیابی می‌شوند و مسئلۀ ردیابی برخط و استوار زیرفضا شکل می‌گیرد.

    3- روش پیشنهادی

    3-1- تببین مسئله

    روش‌های مبتنی بر ردیابی برخط و استوار زیرفضا، داده را به دو بخش زیرفضای اصلی و مؤلفۀ خلوت، تخمین می‌زنند و با تحلیل بخش خلوت، به استخراج ناهنجاری در داده‌ها می‌پردازند. این روش‌ها برای مدل‌سازی داده‌های جریانی بسیار انعطاف‌پذیرند؛ زیرا ویژگی‌های مختلف مربوط به آنها به‌راحتی در مدل منعکس می‌شوند. یکی از مهم‌ترین ویژگی داده‌های جریانی، تغییر و پویایی آنها در گذر زمان است؛ بنابراین، یک مدل کارآمد باید در مقابل این تغییرات، تطبیق‌پذیر باشد. نوعی از این تغییرات مربوط به تغییرات ناگهانی یا افزایشی الگوهای اصلی پنهان در داده‌ها یا همان زیرفضای اصلی است. به‌تازگی در [21] الگوریتمی بر پایه مدل زیر ارائه شده است که تطبیق‌پذیری بسیار خوبی در مقابل این دسته از تغییرات دارد.

    (2)

     

     

    بر مبنای مدل فوق،  Ytبه‌عنوان ماتریس مجاورت گراف ورودی در هر گام زمانی به زیرفضای اصلی و تغییراتش به شکل  و ماتریس خلوت  تجزیه می‌شود. یادآوری می‌شود این تجزیه یک فرم توسعه‌یافته از تجزیه برخط CP است که ماتریس‌های  و  ماتریس‌های فاکتور غیر زمانی و b فاکتور زمان و R رتبه ماتریس داده ورودی است. با اعمال نرم فربنیوس و استفاده از مکانیسم کمترین مربعات نمایی وزندار مبتنی بر فاکتور فراموشی λ بر ماتریس‌های A و C، زیرفضای اصلی با رجوع به سابقۀ داده در طول زمان ردیابی می‌شود. همچنین، با اعمال نرم یک بر  و  به‌عنوان ماتریس‌های خلوت مربوطه به فاکتورهای A و C انحرافات الگوهای اصلی محاسبه می‌شوند. به این ترتیب، زیرفضای اصلی در یک روند تکاملی و با نگاه به سابقۀ داده‌ها به‌روز می‌‌شود؛ اما انحرافات، در لحظه و برخط به‌ازای هر گام زمانی محاسبه می‌شوند. ماتریس خلوت V هم در هر گام زمانی انحرافات سراسری را جمع آوری می‌کند که مبنای استخراج ناهنجاری است.

    در این رابطه، پارامتر μ و λ2 برای کنترل دقت تقریب ماتریس‌های مربوط به زیرفضا و پارامتر  λ1میزان خلوت‌بودن ماتریس V را کنترل می‌کنند. در مواقعی که نرخ خطا در سیستم کم تخمین زده می‌شود، μ مقدار کمتری خواهد داشت. λ نیز مقداری بین صفر و یک دارد. مقدار یک به معنی استفاده از همۀ سوابق داده‌ها و معادل مدل برون‌خط است؛ اما در مقادیر کمتر از یک به‌صورت نمایی از اهمیت و وزن داده‌های قدیمی برای محاسبۀ فاکتورهای جدید کاسته می‌شود.

    مدل فوق یک مسئلۀ بهینه‌سازی نامحدب است که تخمین فاکتور زمان با استفاده از تخمین‌گر کمترین مربعات، تخمین ماتریس خلوت V براساس عملگر آستانه‌گیری نُرم، تخمین A’ وC’ در قالب تخمینگر لاسو و تخمین فاکتورهای A و C با استفاده از کمترین مربعات بازگشتی به‌صورت متناوب انجام می‌شوند. محاسبات مربوطه به‌طور کامل در مقاله [21] آمده‌‌اند.

    با ارجاع به شکل (1) به‌عنوان اجزای پایۀ سیستم مبتنی بر رانش و انتخاب راهکار و مدل مرجع [21] برای حل مسئلۀ این پژوهش، چند نکته مهم درخور ذکر است: نخست اینکه این راهکار بین رانش و ناهنجاری تمایزی قائل نیست و رانش، مفهوم را به‌عنوان ناهنجاری شناسایی می‌کند؛ زیرا واحد تشخیص رانش مفهوم ندارد و خطای باقیماندۀ کل، مبنای تشخیص انحراف است که تمایزی بین تغییرات ناشی از رانش مفهوم و ناهنجاری قائل نمی‌شود. نکتۀ دوم به دلیل ناآگاهی از بروز رانش، در همۀ گام‌های زمانی، تطبیق با تغییرات یا همان یادگیری ماتریس‌های زیرفضا تکرار می‌شود. این در حالیست که محاسبۀ این ماتریس‌ها بسیار پُرهزینه است. بر اساس این، برای رفع موانع فوق، چارچوب پیشنهادی این مقاله با عنوان ردیاب برخط استوار تطبیق‌پذیر آگاهانه[13]، IAROST، شامل سه واحد یادگیری، تشخیص رانش مفهوم و تشخیص ناهنجاری تشریح می‌شود.

    3-2- تشخیص رانش مفهوم

    یکی از الزامات یادگیرندۀ برخط رانش - آگاه در یک محیط تغییرپذیر، وجود مکانیزم تشخیص رانش مفهوم به‌صورت صریح و مجزا از ناهنجاری است [8]. این مکانیزم اطلاعات مفیدی را در ارتباط با پویایی داده‌ها فراهم می‌کند. در این بخش، مکانیزم پیشنهادی تشریح می‌شود.

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

    با توجه به اینکه هر ستون از ماتریس‌های A’ وC’ به یک مؤلفه در داده اشاره دارد، اعمال نرم L2.1 به‌صورت  بر روی این ماتریس‌ها سنجۀ مناسبی برای اندازه‌گیری میزان تغییرات است؛ بنابراین، در هر گام زمانی، این نرم، محاسبه و سری زمانی حاصل از آن به‌منظور تشخیص قله[14]، پایش می‌شود. سری‌های زمانی به‌دست‌آمده به‌صورت برخط با الگوریتم smoothed z-score[22] تحلیل می‌شوند. این الگوریتم با ورود دادۀ جدید  در سری زمانی، میزان انحراف آن نقطه را نسبت به میانگین متحرک به طول m محاسبه می‌کند. در صورتی که z-score به‌دست‌آمده از مقدار حد آستانه بیشتر باشد، یک قله گزارش می‌شود. میانگین متحرک (s) و انحراف از معیار (σ) طبق روابط زیر محاسبه می‌شوند:

    (3)

     

    (4)

     

     

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

    (5)

     

     

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

    3-3- یادگیری و تطبیق‌پذیری

    براساس ویژگی‌های قلب یک سیستم یادگیری مبتنی بر رانش طبق شکل (1) و با استناد به رابطه (2)، حالت یادگیری به‌صورت برخط است.

    ویژگی دوم مربوط به تطبیق‌پذیری مدل است که نحوۀ سازگاری مدل در مواجهه با داده‌های جدید را مشخص می‌کند. همان‌طور که قبلاً گفته شد در رویکردهای یادگیری تحت رانش، دو استراتژی عمده تطبیق‌پذیری معرفی شده است، کورکورانه و آگاهانه. استراتژی کورکورانه در واکنش به رانش به‌صورت پیشگیرانه[15] و کند عمل می‌کند. علاوه بر این، به دلیل به‌روزرسانی منظم مدل در هر گام زمانی، بسیار هزینه‌بر و زمان‌بر است؛ در حالی که یک استراتژی آگاهانه، به‌صورت واکنشی[16] عمل می‌کند و در هر گام زمانی، وقوع رانش را بررسی و در صورت مثبت‌بودن، فرآیند تطبیق مدل با دادۀ جدید انجام می‌شود. در این حالت، مدل فقط در صورت نیاز به‌روز می‌شود؛ بنابراین، این استراتژی کارآمدتر است. یکی دیگر از مزایای یک استراتژی آگاهانه، ارائۀ اطلاعات دربارۀ پویایی فرآیند تولید داده است. این پژوهش، یک استراتژی آگاهانه برای تطبیق‌پذیری ردیاب برخط و استوار زیرفضا در مواجهه با رانش ارائه می‌کند.

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

    ویژگی سوم یک یادگیرنده در سیستم‌های مبتنی بر رانش این است که فرآیند یادگیری با استفاده از یک یادگیرندۀ واحد انجام می‌شود یا ترکیبی از چندین یادگیرنده. در این پژوهش، یک یادگیرندۀ واحد در نظر گرفته شده است که با گذشت زمان تکامل می‌یابد.

    3-4- تشخیص ناهنجاری

    با توجه به اینکه ماتریس V، بخش خلوت را نشان می‌دهد، اندازۀ بزرگی آن، سنجۀ خوبی برای تعیین زمان بروز ناهنجاری است. با استفاده از الگوریتم smoothed z-score، استفاده‌شده در شکل (2)، سری زمانی حاصله از نرم دو ماتریس V (سنجۀ اندازۀ بزرگی ماتریس به‌صورت ) پایش و با شناسایی یک قله، بروز ناهنجاری، اعلام و محرک لازم به واحد تشخیص ناهنجاری صادر می‌شود تا یال و گره ناهنجار تعیین شوند؛ بدین شکل که ضمن اعمال تابع z-score روی ماتریس V، درایه‌های با بیش از مقدار آستانه δ، یال ناهنجار اعلام می‌شوند. همچنین، به‌منظور تشخیص گرههای ناهنجار، نُرم دو هر ردیف از ماتریس، محاسبه و با اعمال تابع z-score  موارد بیش از حد آستانه δ اعلام می‌شوند. با این روال، به‌صورت برخط، در هر گام زمانی با کمترین هزینه، موارد ناهنجار شناسایی و اعلام می‌شوند. شکل (3) شبه کد این بخش را نشان می‌دهد.

     

    3-5- الگوریتم IAROST

    الگوریتم روش پیشنهادی به‌طور کامل در شکل (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

[1] [1] F. Khojasteh, M. Kahani, and B. Behkamal, “Concept drift detection in business process logs using deep learning,” Signal Data Process., Vol. 17, No. 4, pp. 33–48, 2021.
[2] K. S. Yaghoubi M, Sebti A, “Identifying Concept Drift in Business Processes by Analyzing Type of Surveys in Event History,” J. Inf. Commun. Technol., Vol. 12, No. 43, 1399.
[3] H. H. Kordi Ardestan F, Siyadati S, “An improved concept-based drift solution to update customer profiles in fraud detection systems,” in 8th Annual Conference on Electronic Banking and Payment Systems, 1397.
[4] J. Sun, D. Tao, and C. Faloutsos, “Beyond streams and graphs,” in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’06, 2006, p. 374.
[5] H. F. Tork, M. Oliveira, J. Gama, S. Malinowski, and R. Morla, “Event and anomaly detection using Tucker3 decomposition,” in CEUR Workshop Proceedings, 2012, Vol. 960, pp. 8–12.
[6] H. Fanaee-T and J. Gama, “Event detection from traffic tensors: A hybrid model,” Neurocomputing, Vol. 203, No. C, pp. 22–33, Aug. 2016.
[7] J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, and G. Zhang, “Learning under Concept Drift: A Review,” 2019.
[8] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, and A. Bouchachia, “A survey on concept drift adaptation,” ACM Comput. Surv., Vol. 46, No. 4, pp. 1–37, 2014.
[9] R. N. Gemaque, A. F. J. Costa, R. Giusti, and E. M. Santos, “An overview of unsupervised drift detection methods,” WIREs Data Min. Knowl. Discov., Jul. 2020.
[10] S. Saurav et al., “Online anomaly detection with concept drift adaptation using recurrent neural networks,” in Proceedings of the ACM India Joint International Conference on Data Science and Management of Data - CoDS-COMAD ’18, 2018, pp. 78–87.
[11] D. Zambon, C. Alippi, and L. Livi, “Concept Drift and Anomaly Detection in Graph Streams,” IEEE Trans. Neural Networks Learn. Syst., Vol. 29, No. 11, pp. 5592–5605, 2018.
[12] B. Hooi, K. Shin, S. Liu, and C. Faloutsos, “SMF: Drift-aware matrix factorization with seasonal patterns,” in SIAM International Conference on Data Mining, SDM 2019, 2019, pp. 621–629.
[13] H. Kasai, W. Kellerer, and M. Kleinsteuber, “Network Volume Anomaly Detection and Identification in Large-Scale Networks Based on Online Time-Structured Traffic Tensor Tracking,” IEEE Trans. Netw. Serv. Manag., Vol. 13, No. 3, pp. 636–650, 2016.
[14] M. Mardani and G. B. Giannakis, “Estimating Traffic and Anomaly Maps via Network Tomography,” IEEE/ACM Trans. Netw., Vol. 24, No. 3, pp. 1533–1547, 2016.
[15] M. Mardani, G. Mateos, and G. B. Giannakis, “Dynamic anomalography: Tracking network anomalies via sparsity and low rank,” IEEE J. Sel. Top. Signal Process., Vol. 7, No. 1, pp. 50–66, 2013.
[16] R. Pasricha, E. Gujral, and E. E. Papalexakis, “Identifying and alleviating concept drift in streaming tensor decomposition,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), Vol. 11052 LNAI, pp. 327–343, Apr. 2019.
[17] Y. Y. Lo, W. Liao, C. S. Chang, and Y. C. Lee, “Temporal Matrix Factorization for Tracking Concept Drift in Individual User Preferences,” IEEE Trans. Comput. Soc. Syst., Vol. 5, No. 1, pp. 156–168, Mar. 2018.
[18] G. I. Webb, R. Hyde, H. Cao, H. L. Nguyen, and F. Petitjean, “Characterizing concept drift,” Data Min. Knowl. Discov., Vol. 30, No. 4, pp. 964–994, Jul. 2016.
[19] M. Sayed-Mouchaweh, Learning from Data Streams in Dynamic Environments. Cham: Springer International Publishing, 2016.
[20] T. G. Kolda and B. W. Bader, “Tensor Decompositions and Applications,” SIAM Rev., Vol. 51, No. 3, pp. 455–500, Aug. 2009.
[21] M. Amoozegar, B. Minaei-Bidgoli, M. Rezghi, and H. Fanaee-T, “Extra-adaptive robust online subspace tracker for anomaly detection from streaming networks,” Eng. Appl. Artif. Intell., Vol. 94, p. 103741, Sep. 2020.
[22] J. P. van Brakel, “Smoothed z-score algorithm,” 2016. [Online]. Available: http://stackoverflow.com/questions/225 83391/peaksignal-detection-in-realtime-timeseries-data. [Accessed: 23- June2019]. [Accessed: 01-Jan-2019].
[23] H. Kasai, “Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations,” Neurocomputing, Vol. 347, pp. 177–190, 2019.
[24] A. Sobral, S. Javed, S. K. Jung, T. Bouwmans, and E. H. Zahzah, “Online Stochastic Tensor Decomposition for Background Subtraction in Multispectral Video Sequences,” in Proceedings of the IEEE International Conference on Computer Vision, 2015, Vol. 2015-Febru, pp. 946–953.
[25] M. Mardani, G. Mateos, and G. B. Giannakis, “Subspace learning and imputation for streaming big data matrices and tensors,” IEEE Trans. Signal Process., Vol. 63, No. 10, pp. 2663–2677, 2015.
[26] X. Ding, L. He, and L. Carin, “Bayesian robust principal component analysis,” IEEE Trans. Image Process., Vol. 20, No. 12, pp. 3419–3430, 2011.
[27] J. Y. Wei, J. F. Zhao, Y. Y. Zhao, and Z. C. Zhao, “Unsupervised anomaly detection for traffic surveillance based on background modeling,” 2018.
[28] L. Li, W. Huang, I. Y. H. Gu, and Q. Tian, “Statistical modeling of complex backgrounds for foreground object detection,” IEEE Trans. Image Process., Vol. 13, No. 11, pp. 1459–1472, 2004.
[29] C. Lin, Q. Zhu, S. Guo, Z. Jin, Y. R. Lin, and N. Cao, “Anomaly detection in spatiotemporal data via regularized non-negative tensor analysis,” Data Min. Knowl. Discov., pp. 1–18, Mar. 2018.
[30] “Enron Email Dataset.” [Online]. Available: https://www.cs.cmu.edu/~./enron/.
[31] “Trade (v4.0) — Correlates of War.” [Online]. Available: https://correlatesofwar.org/data-sets/bilateral-trade.
[32] J. Liao, J. Tang, W. Zeng, and X. Zhao, “Efficient and Accurate Traffic Flow Prediction via Incremental Tensor Completion,” pp. 2169–3536, 2018.
[33] A. Vandervalk, D. Snyder, and J. Hajek, “US DOT Roadway Transportation Data Business Plan (Phase 1),” 2013.