جنگل انزوا: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی

→ تفاوت قدیمی‌تر تفاوت جدیدتر ←

محتوای حذف‌شده محتوای افزوده‌شده

دیداریویکی‌متن

درخط

نسخهٔ ‏۲۰ ژوئن ۲۰۲۳، ساعت ۱۷:۵۶

جنگل اِنزِوا (به انگلیسی Isolation Forest) یک روش یادگیری نظارت نشده برای تشخیص داده‌های پَرت است.

یک جنگل انزوا مجموعه‌ای از درخت‌های انزوا (به انگلیسی Isolation Tree) است. هر درخت انزوا در واقع یک درخت دودویی می‌باشد.

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

شکل سمت چپ کاربردی از این الگوریتم را نشان میدهد. در ابن شکل فاصله ی زمانی بین فوران بر حسب زمان هر فوران برای آبفشان مخروطی Old Faithful ^[۱] نشان داده شده است. نواحی قرمز تیره امتیاز ناهنجاری بیشتری را نشان می دهند.

در درخت انزوا داده‌هایی که زودتر از بقیه جدا شوند نزدیک‌تر به ریشهٔ درخت می‌باشند و به این ترتیب احتمال پَرت بودن آن‌ها بیشتر می‌شود. میزان پرت بودن یک داده در یک درخت انزوا به صورت کلی برابر است با تعداد یال‌هایی که باید از ریشهٔ درخت تا گرهٔ برگ (Leaf Node) طی شود؛ بنابراین هرچه این مسیر کوتاه‌تر باشد احتمال پرت بودن داده بیشتر می‌شود. در نهایت جنگل انزوا برای تشخیص پرت بودن میانگین مسیرهای طی شده در هر درخت انزوا برای هر داده را محاسبه می‌کند.^[۲]

تاریخچه

این الگوریتم اولین بار در سال 2008 توسط فی تونی لیو و ژی هوا ژو توسعه داده شد.^[۳] در سال 2010 یک نسخه ی دیگری از این الگوریتم به نام سای فارست^[۴] توسعه داده شد تا مسئله ی مربوز به ناهنجاری های خوشه ای و ناهنجاری های موازی با پایه های متعامد فضا را حل کند.

الگوریتم

ساختن درخت انزوا

روند ساختن یک درخت ایزوله از روی یک مجموعهٔ دادهٔ $X=\lbrace x_{1},...,x_{n}\rbrace$ به‌طور خلاصه به ترتیب زیر است:^[۵]

اگر $\left\vert X\right\vert \leq 1$ $\left\vert X\right\vert \leq 1$ یا ارتفاع درخت به یک حد از پیش تعیین شدهٔ $l$ $l$ رسیده باشد:
1. ساختن یک گرهٔ برگ.
در غیر این صورت:
1. انتخاب تصادفی یک ویژگی $q$ (Feature) از میان تمامی ویژگی‌های موجود در مجوعهٔ دادهٔ $X$ .
2. انتخاب کمترین و بیشترین مقدار در ویژگی $q$ به نام‌های $min$ و $max$ .
3. انتخاب تصادفی یک مقدار $p$ بین $min$ و $max$ .
4. ساختن یک گرهٔ داخلی $X_{l}\subseteq X$ به عنوان فرزند چپ درخت به طوری که ویژگی $q$ تمامی عناصر مجموعهٔ $X_{l}$ کمتر از $p$ باشد و فراخوانی دوبارهٔ الگوریتم بر روی این مجموعه از داده‌ها.
5. ساختن یک گرهٔ داخلی $X_{r}\subseteq X$ به عنوان فرزند راست درخت به طوری که ویژگی $q$ تمامی عناصر مجموعهٔ $X_{r}$ بزرگتر یا مساوی $p$ باشد و فراخوانی دوبارهٔ الگوریتم بر روی این مجموعه از داده‌ها.

خصوصیات الگوریتم

این الگوریتم پیچیدگی زمانی از مرتبه ی خطی دارد و برای اجرا به حافظه ی کمی نیاز دارد. این موضوع این الگوریتم را برای اجرا روی دادگان حجیم مناسب می سازد.

شبه کد

ساختن جنگل انزوا

شبه کد

محاسبهٔ امتیاز پرت بودن (Anomaly score)

شبه کد

خصوصیات جنگل انزوا

زیرنمونه برداری (Sub-sampling): این الگوریتم نیازی به آن ندارد که همهٔ داده‌های مربوط به مرحلهٔ آموزش (Training) را در اختیار داشته باشد. به همین دلیل تنها یک زیرنمونه از داده‌ها برای آموزش الگوریتم کفایت می‌کند. این در حالی است که اکثر الگوریتم‌ها هرچه داده‌های بیشتری را دراختیار داشته باشند بهتر عمل می‌کنند. به این ترتیب می‌توان گفت که یکی از ویژگی‌های مثبت این الگوریتم زیرنمونه برداری و قابلیت کار کردن با داده‌های کم می‌باشد.^[۶]

تاریخچه

منابع

↑ «Old Faithful».
↑ Tan, Swee Chuan; Ting, Kai Ming; Liu, Fei Tony (2011). "Fast anomaly detection for streaming data". Proceedings of the Twenty-Second international joint conference on Artificial Intelligence. 2. AAAI Press. pp. 1511–1516. doi:10.5591/978-1-57735-516-8/IJCAI11-254. ISBN 978-1-57735-514-4.
↑ Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (2008-12). "Isolation Forest". 2008 Eighth IEEE International Conference on Data Mining. IEEE. doi:10.1109/icdm.2008.17. {{cite journal}}: Check date values in: |date= (help)
↑ Liu, F.T., Ting, K.M., Zhou, ZH. (2010). On Detecting Clustered Anomalies Using SCiForest. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2010. Lecture Notes in Computer Science(), vol 6322. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15883-4_18. پارامتر |عنوان= یا |title= ناموجود یا خالی (کمک); پیوند خارجی در |ژورنال= وجود دارد (کمک)
↑ Shaffer, Clifford A. (2011). Data structures & algorithm analysis in Java (3rd Dover ed.). Mineola, NY: Dover Publications. ISBN 978-0-486-48581-2. OCLC 721884651.
↑ Hariri, Sahand; Carrasco Kind, Matias; Brunner, Robert J. (2019). "Extended Isolation Forest". IEEE Transactions on Knowledge and Data Engineering: 1. arXiv:1811.02141. doi:10.1109/TKDE.2019.2947676. S2CID 53236735.

[1] «Old Faithful».

[2] Tan, Swee Chuan; Ting, Kai Ming; Liu, Fei Tony (2011). "Fast anomaly detection for streaming data". Proceedings of the Twenty-Second international joint conference on Artificial Intelligence. 2. AAAI Press. pp. 1511–1516. doi:10.5591/978-1-57735-516-8/IJCAI11-254. ISBN 978-1-57735-514-4.

[3] Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (2008-12). "Isolation Forest". 2008 Eighth IEEE International Conference on Data Mining. IEEE. doi:10.1109/icdm.2008.17. {{cite journal}}: Check date values in: |date= (help)

[4] Liu, F.T., Ting, K.M., Zhou, ZH. (2010). On Detecting Clustered Anomalies Using SCiForest. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2010. Lecture Notes in Computer Science(), vol 6322. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15883-4_18. پارامتر |عنوان= یا |title= ناموجود یا خالی (کمک); پیوند خارجی در |ژورنال= وجود دارد (کمک)

[5] Shaffer, Clifford A. (2011). Data structures & algorithm analysis in Java (3rd Dover ed.). Mineola, NY: Dover Publications. ISBN 978-0-486-48581-2. OCLC 721884651.

[6] Hariri, Sahand; Carrasco Kind, Matias; Brunner, Robert J. (2019). "Extended Isolation Forest". IEEE Transactions on Knowledge and Data Engineering: 1. arXiv:1811.02141. doi:10.1109/TKDE.2019.2947676. S2CID 53236735.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

@@ خط ۱: / خط ۱: @@
+[[پرونده:Normalized Anomaly Scores of Isolation Forest.png|حاشیه|بندانگشتی|امتیاز های نرمال شده روی دادگان دیتاست "Old Faithful" در نتیجه ی اجرای الگوریتم جنگل انزوا]]
 [[پرونده:Isolation Tree.jpg|بندانگشتی|300x300پیکسل|نمونه‌ای از یک درخت انزوا. در این درخت گره‌ی مشخص شده با رنگ قرمز تنها دو یال با ریشه‌ی درخت فاصله دارد. در صورتی که مسیر مشخص شده با رنگ آبی پنج یال با ریشه‌ی درخت فاصله دارد. بنابراین می‌توان گفت که گره‌ی قرمز در مقایسه با سایر گره‌های درخت پَرت‌تر است.]]
 '''جنگل اِنزِوا''' (به انگلیسی Isolation Forest) یک روش یادگیری نظارت نشده برای تشخیص [[داده پرت|داده‌های پَرت]] است.
@@ خط ۵: / خط ۶: @@
 به طور خلاصه این الگوریتم فضای دادگان را به کمک خطوطی موازی پایه های متعامد فضا جداسازی می کند و به دادگانی که در قسمت های مختلف این فضا قرار گرفته اند امتیازی برای میزان غیر طبیعی بودن اختصاص می دهد. نحوه ی تخصیص این امتیاز نیز بدین صورت است که دادگانی که به خطوط جداساز کمتری برای قرار گیری در یک خوشه ی جداگانه نیاز دارند امتیاز بیشتری دریافت می کنند.
+شکل سمت چپ کاربردی از این الگوریتم را نشان میدهد. در ابن شکل فاصله ی زمانی بین فوران بر حسب زمان هر فوران برای آبفشان مخروطی Old Faithful <ref>{{یادکرد وب|نشانی=https://en.wikipedia.org/wiki/Old_Faithful|عنوان=Old Faithful}}</ref> نشان داده شده است. نواحی قرمز تیره امتیاز ناهنجاری بیشتری را نشان می دهند.
 در درخت انزوا داده‌هایی که زودتر از بقیه جدا شوند نزدیک‌تر به ریشهٔ درخت می‌باشند و به این ترتیب احتمال پَرت بودن آن‌ها بیشتر می‌شود. میزان پرت بودن یک داده در یک درخت انزوا به صورت کلی برابر است با تعداد یال‌هایی که باید از ریشهٔ درخت تا گرهٔ برگ (Leaf Node) طی شود؛ بنابراین هرچه این مسیر کوتاه‌تر باشد احتمال پرت بودن داده بیشتر می‌شود. در نهایت جنگل انزوا برای تشخیص پرت بودن میانگین مسیرهای طی شده در هر درخت انزوا برای هر داده را محاسبه می‌کند.<ref>{{یادکرد کتاب|عنوان=Tan, Swee Chuan; Ting, Kai Ming; Liu, Fei Tony (2011). "Fast anomaly detection for streaming data". Proceedings of the Twenty-Second international joint conference on Artificial Intelligence. 2. AAAI Press. pp. 1511–1516. doi:10.5591/978-1-57735-516-8/IJCAI11-254. ISBN 978-1-57735-514-4.}}</ref>
 == تاریخچه ==
+این الگوریتم اولین بار در سال 2008 توسط فی تونی لیو و ژی هوا ژو توسعه داده شد.<ref>{{Cite journal|last=Liu|first=Fei Tony|last2=Ting|first2=Kai Ming|last3=Zhou|first3=Zhi-Hua|date=2008-12|title=Isolation Forest|url=http://dx.doi.org/10.1109/icdm.2008.17|journal=2008 Eighth IEEE International Conference on Data Mining|publisher=IEEE|doi=10.1109/icdm.2008.17}}</ref> در سال 2010 یک نسخه ی دیگری از این الگوریتم به نام سای فارست<ref>{{یادکرد ژورنال|ژورنال=Liu, F.T., Ting, K.M., Zhou, ZH. (2010). On Detecting Clustered Anomalies Using SCiForest. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2010. Lecture Notes in Computer Science(), vol 6322. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15883-4_18}}</ref> توسعه داده شد تا مسئله ی مربوز به ناهنجاری های خوشه ای و ناهنجاری های موازی با پایه های متعامد فضا را حل کند.
-این الگوریتم اولین بار در سال 2008 توسط فی تونی لیو و ژی هوا ژو توسعه داده شد.
 == الگوریتم ==