25323

تشخيص ناهنجاري در گراف‌هاي پويا با استفاده از الگوريتم‌هاي تجزيه تانسور

دكتري

مهندسي كامپيوتر

95-1400

1400/05/02

دكتر بهروز مينايي

دكتر منصور رزقي-دكتر هادي فنايي

مهندسي كامپيوتر

تشخيص ناهنجاري در گراف‌هاي پويا كاربردهاي متفاوتي از جمله تجزيه و تحليل ترافيك در شبكه‌هاي حمل و نقل و تحليل بار در شبكه‌هاي هوشمند برق دارد. دسته مهمي از راهكارهاي تشخيص ناهنجاري در شبكه‌هاي پويا، بر پايه رديابي زيرفضاي برخط استوار و تجزيه تانسور بنا نهاده شده‌اند. البته روش‌هاي موجود از عدم استواري كافي در مقابل تغييرات ناگهاني زيرفضا رنج مي‌برند. به منظور حل اين مشكل، اين رساله يك ردياب زيرفضا و ناهنجاري برخط استوار مبتني بر تجزيه تانسور ارائه كرده است كه در برابر تغييرات ناگهاني زير فضا استوار است. تخمين دقيق‌تر زيرفضاي اصلي و متعاقب آن بخش خلوت، باعث تشخيص ناهنجاري با دقت بيشتري شده است. عملكرد راهكار پيشنهادي با مجموعه‌داده‌هاي با سطح مختلف تنكي ارزيابي شده است. كاهش ده درصدي خطاي پيش‌بيني و افزايش پانزده درصدي مقادير F-Measure برتري روش پيشنهادي را بر راهكارهاي موجود از دو جنبه توان يادگيري و تشخيص ناهنجاري نشان مي‌دهد. از منظري ديگر، تغيير ناگهاني زيرفضا به معني تغيير رفتار طبيعي و معادل نوعي از رانش مفهوم است كه بايد از ناهنجاري تفكيك شود. اين تمايز منجر به كاهش هشدار نادرست و در نتيجه بهبود كارايي تشخيص ناهنجاري مي‌شود. علاوه بر اين، در راهكار اول بروزرساني پيوسته يادگيرنده و تطبيق آن با تغييرات احتمالي در همه گام‌هاي زماني انجام مي‌شود كه بسيار پرهزينه است. بر اين اساس راهكار پيشنهادي دوم يك الگوريتم رديابي زيرفضاي استوار است كه قابليت تشخيص صريح رانش مفهوم و تفكيك آن از ناهنجاري را به طور همزمان و برخط دارد و علاوه بر آن تطبيق زيرفضا تنها در زمان وقوع رانش مفهوم انجام مي‌شود. ارزيابي روش پيشنهادي با مجموعه داده‌هاي واقعي انجام شد كه افزايش پانزده درصدي مقادير سنجه F-measure و كاهش بيست درصدي سنجه كشف مثبت كاذب، كارايي بهتر واحد تشخيص ناهنجاري را تاييد مي‌كنند. همچنين كاهش ده درصدي خطاي پيش‌بيني، توان بالاتر يادگيرنده را در همگرايي و تطبيق با تغييرات نشان مي‌دهد.

1400/07/10

Anomaly detection in dynamic graphs using algorithms for tensor decomposition

7/24/2022 12:00:00 AM

Anomaly detection in dynamic graph has many applications, for instance, traffic analysis in transportation networks and load analysis in smart electrify networks. One group of popular methods for anomaly detection from dynamic networks are tensor decomposition based robust online subspace trackers. However, these methods suffer from problem of insensitivity to drastic changes in the evolving subspace. In order to solve this problem, we propose a new robust online subspace and anomaly tracker based on tensor decomposition which is more adaptive and robust against sudden drastic changes in the subspace. More accurate estimation of low rank and sparse components by this tracker leads to more accurate anomaly detection. We evaluate the accuracy of our method with real-world dynamic network data sets with varying sparsity levels. Ten percent reduction for prediction error and fifteen percent increase F-Measure confirm that our method outperforms the state-of-the-art in terms of learning ability and anomaly detection. On the other hand, a sudden change in the subspace means a change in the natural behavior and is equivalent to a type of concept drift and must be distinguished from the anomaly. This discrimination reduces the false alarms and improves the performance of anomaly detection. In addition, the first solution continuously updates the learner to adapt with changes at all time steps, which is very costly. Accordingly, the second proposed method is a robust subspace tracking algorithm that explicitly detects concept drift and distinguishes it from anomaly simultaneously and online. Moreover, adaptation process is performed only when the concept drift occurs. Evaluation with real datasets demonstrates the promising performance of the proposed method for anomaly detection with fifteen percent increasing in F-measure and twenty percent decreasing in false-positive discovery, as well as convergence and adaptivity of the learning model by providing a lower prediction error.

تشخيص ناهنجاري , گراف‌هاي پويا , روش‌هاي تجزيه تانسور , الگوريتم‌هاي برخط استوار , رانش مفهوم

Anomaly detection , Dynamic graphs , Tensor decomposition methods , Online and incremental algorithms , concept drift