بخشی از مقاله
چکیده
تشخیص ناهنجاری در میان دادههای مورداستفاده یک امر مهم بوده و میتواند کاربردهای فراوانی در زمینههای امنیت، امور مالی، اجرای قانون داشته باشد. ازجمله دلایل ایجاد دادههای پرت میتوان به خطاهای انسانی، خطاهای سیستمی و ابزاری اشاره نمود.
در این مقاله با استفاده از روش برش گراف و با استفاده از دو الگوریتم کلونی مورچگان و مهاجرت پرندگان به شناسایی دادههای پرت اقدام گردید. دو الگوریتم ارائهشده در این مقاله، هرکدام رویکردهای جدیدی در زمینه تشخیص دادههای پرت ارائه داده و با استفاده از آنها، دامنههای بهتر و گستردهتری برای تشخیص دادهای پرت ارائه گردیده است.
-1 مقدمه
زمانی که بر روی مجموعه عظیمی از دادهها تجزیهوتحلیل انجام میدهیم، فهمیدن اینکه کدام داده مغایر با سایر دادهها میباشد، امری مهم و حیاتی است. شاخهای از دادهکاوی که در زمینه تشخیص اینگونه دادهها در مجموعهها کاربرد دارد را تشخیص ناهنجاری یا تشخیص پرت مینامند. تشخیص داده پرت میتواند رابطه مستقیمی با نوع کاربرد و زمینه مورداستفاده آن داشته باشد. در حالت کلی یک داده پرت دادهای است که تفاوت قابل ملاحظهای با بقیه اعضای نمونهای که در آن قرار دارد داشته باشد
شناسایی دادههای پرت کاربردهای فراوانی در علوم مختلف دارد که ازجمله این کاربردها میتوان به: تشخیص تقلب، آزمایشهای پزشکی، عیبیابی، آمارهای ورزشی، تشخیص خطاهای اندازهگیری و غیره، اشاره کرد.
تشخیص دادههای پرت ازآنجهت اهمیت دارد که میتواند با دسترسی به دادههای مخفی و ارائه راهکارهای سریع برای حل آن به پیشبینی و تشخیص مشکلات آتی کمک کرده و از وقوع آنها جلوگیری نماید. ازجمله مثالهایی که میتوان در این زمینه به آنها اشاره کرد، تشخیص پرتهای موجود در الگوریتمهای ترافیک شبکه که میتواند نشاندهنده هک شدن شبکههای کامپیوتری باشد و از طریق آن دادههای مهمی به بیرون درز کرده باشد اشاره نمود. همچنین میتوان به پرتهای موجود در عکسهای MRI که نشاندهنده وجود تومورهای بدخیم در افراد گوناگون باشد و پرتهای موجود در تراکنشهای انجامگرفته با کارتهای اعتباری که میتواند نشاندهنده سرقت مبالغ و یا سرقت هویت افراد باشد اشاره کرد.
ازجمله دلایل به وجود آمدن دادهای پرت میتوان به: خطاهای انسانی، خطاهای ابزاری، انحرافات طبیعی به وجود آمده در جوامع، دستکاری در قوانین یا تقلب، تغییرات در رفتارهای سیستم و یا خطا در آن اشاره کرد. بهطورمعمول خطاهای اشارهشده و پرتهای به وجود آمده توسط به وجود آورنده آن و یا افرادی که مسئول رفع آن هستند بهصورت عادی برطرف میگردند. تعدادی از دادههای پرت هم هستند که یا بهموقع شناسایی نشده و یا بهصورت عادی قابلشناسایی و تشخیص نیستند، بر همین اساس سه روش که بهطورمعمول برای تشخیص پرت استفاده میشود به شرح زیر میباشند.
-1 تشخیص دادههای پرت بدون داشتن دانش قبلی از دادههای موردمطالعه. این روشاساساً بدون نظارت بوده و چگونگی انجام آن اینگونه است که دادهای دورافتاده از سایر دادههایی که با استفاده از تحلیل بر روی توزیعهای آماری بهدستآمدهاند، بهعنوان داده پرت انتخاب میشوند . در این نوع تشخیص، فرض میگردد که دادهای پرت از دادههای عادی جدا بوده و به همین دلیل بهعنوان ناهنجاری انتخاب میگردند.
-2 تشخیص دادههای پرت با استفاده از دادههای معمولی و دادههای پرت. این روش شباهت بسیاری با کلاسبندی نظارتشده دارد و در آن دادهها از قبل علامتگذاری میشوند. کلاسبندی یک روش مناسب برای طبقهبندی دادهها میباشد و بهوسیله آن میتوان دادههای نرمال را از دادهای پرت تشخیص داد و هرکدام از آنها را در کلاسهای مجزایی دستهبندی کرد. این روش در کلاسبندی خطی کاربرد داشته و در آن میتوان به آموزش مدل و سپس کلاسبندی نمونههای جدید اقدام کرد به این صورت که اگر نمونه جدید در کلاس دادهای نرمال قرار گرفت بهعنوان داده معمولی انتخاب و در غیر این صورت بهعنوان داده پرت تشخیص داده میشود. در این روش الگوریتم کلاسبندی نیاز به یک پوشش کامل بر روی دادههای نرمال و غیر نرمال داشته تا کار دستهبندی را بهخوبی انجام دهد.
-3 تشخیص دادههای پرت فقط با استفاده از دادهای معمولی و در مواردی نادر، احتمال وجود دادهای پرت بهصورت خیلی کم در بین دادهها. این روش بهعنوان تشخیص نوگرایی شناخته میشود و به این صورت میباشد که تشخیص در آن بهصورت نیمه نظارت شده بوده و در آن دادههای نظارتشده بهعنوان کلاس نرمال در نظر گرفته میشوند و بر اساس آن الگوریتم آموزش دادهشده تا دادهای پرت را شناسایی نماید. این روش برای دادههای ایستا و پویا کاربرد داشته و همچنین باید دادهها در آن از قبل کلاسبندی شده باشند. این روش برخلاف روش دوم نیازی به دادهای غیر نرمال ندارد.
در این مقاله ابتدا با استفاده از برش گرافی و بهدست آوردن گرافهایی با حداقل طول اقدام، سپس با استفاده از الگوریتم کلونی مورچهها و با شناسایی کوتاهترین گرافهای ممکن به تشخیص دادههای پرت اقدام نموده همچنین در ادامه با بهکارگیری الگوریتم مهاجرت پرندگان بهعنوان جایگزینی برای الگوریتم کلونی مورچهها به شناسایی دادههای پرت اقدام گردید.
ادامه این مقاله از بخشهای زیر تشکیلشده است:
در بخش 2، مروری بر کارهای پیشین را خواهیم داشت .در بخش 3، مقدمهای بر روشهای ارائهشده بیان میگردد. در بخش 4، به ارائه روش پیشنهادی اقدام گردیده است .در بخش 5، ارزیابی از روش ارائهشده را خواهیم داشت و درنهایت در بخش 6 به ارائه نتیجهگیری و پیشنهادات خواهیم پرداخت.
-2 مروری بر کارهای مرتبط پیشین
پیشازاین نیز انواع متفاوتی از روشها جهت شناسایی دادههای پرت استفادهشده که در ادامه برخی از آنها بررسی میگردد.
Zengyou He و همکاران [4] بر روی الگوریتم CBLOF کارکرده و به طبقهبندی خوشههای بهدستآمده از الگوریتم، از بالا به پایین به ترتیب کوچک به بزرگ اقدام نمودند. سپس با استفاده از پرتهای پیداشده توسط الگوریتم به بررسی اهمیت طبقهبندیهای ایجادشده اقدام نمودند. نتایج بهدستآمده از این الگوریتم تا حد زیادی به خوشهبندی انجامشده متکی بود و بر همین اساس، دقت نتایج بهدستآمده پایین و برای کاربرانی که پیشزمینه کافی در این زمینه نداشتند نامناسب بود.
Yong Shi با کار بر روی الگوریتم SubCOID به تشخیص دادههای پرت با استفاده از تنوع مابین خوشهبندیهای ایجادشده پرداخت. این کار با استفاده از رابطه بین خوشهها و همچنین رابطه متقابل بین خوشهها و دادههای پرت بر اساس روش مینیمم درخت پوشا - MST - انجام گرفت. بااینحال جوابهای بهدستآمده از درخت مینیمم پوشا به دلیل وجود چندین راه متفاوت با وزنهای برابر، مناسب نبوده و دارای دقت کافی نمیباشد.
Zahra Hajihashemi و [6] Behrooz Minaei بر روی الگوریتم NC-ACO کارکرده و توانستد با استفاده از فرمول پیشنهادی خودشان در مقاله و محاسبه میزان فاصله اختلالات بهدستآمده توسط آن، به شناسایی خوشههای پرت اقدام نمایند. کار آنها به دلیل اینکه تنها بر روی کیفیت خوشهها تمرکز داشته و هدف آن تشخیص جمعی دادهای پرت با استفاده از خوشهبندی بود، خیلی دقیق نبوده و برای تشخیص دادههای پرت موثر نمیباشد.
Markus و همکاران [7] با ارائه روش LOF به پیدا کردن دادههای پرت با استفاده از K همسایه نزدیک و تراکم دادههای بر اساس آن و همچنین تجزیهوتحلیل تفاوت دادهها بر اساس آن پرداختند. Wen و همکاران [8] الگوریتم RNN را ارائه داده و بر اساس آن و با استفاده از روش معکوس K همسایه نزدیک، به شناسایی و بررسی دادههای پرت اقدام نمودند.
در بررسیهای Markus و همکاران و همچنین Win و همکارانصرفاً میزان تراکم دادهها مدنظر بوده و ویژگیهای اصلی دادههای پرت نادیده گرفتهشده است و بر همین اساس میزان دقت در آنها پایین میباشد. Knorr و [9] Tucakov پیدا کردن دادههای پرت بر مبنای فاصله را موردبررسی قراردادند. آنها فقط یک مفهوم ساده از تشخیص دادههای پرت را در نظر گرفتند بهگونهای که ابعاد مختلف دادههای کارشده، ازجمله حالتهای خاص مدل توزیع در کار آنان نادیده گرفته شد. همچنین از دیگر ایرادات کار آنان میتوان به عدم وجود ابزاری دقیق جهت رتبهبندی دادههای پرت اشاره کرد. بهعلاوه در طبقهبندی انجامشده، دادهها جهت تشخیص اینکه پرت هستند یا نه نشانهگذاری نشده بودند.
Ramaswamy و همکاران [10] به ارائه الگوریتمی مبتنی بر تقسیمبندی اقدام کردند. این الگوریتم دادهای ورودی را به زیرمجموعههایی مجزا از یکدیگر با استفاده از خوشهبندی تقسیمبندی مینماید، سپس به هرس کردن بخشهایی میپردازد که در آنها داده پرت تشخیص دادهشده است. این الگوریتم نسبت به روشی که در آن دادهها بر اساس فاصلهشان تا نقاط مشخصشدهای که توسط کاربر انتخاب میگردیدند، امتیازدهی میشدند کارایی بهتری داشت .
Zhang و همکاران [11] به ارائه روش LDOF اقدام کردند. این روش دادههای پرت را به نسبت فاصلهشان شناسایی مینماید بر این اساس که محاسبه پرت بودن دادها بر اساس پراکندگی آنان در دیتاست مشخص میگردد. روش LDOF از موقعیت نسبی یک داده نسبت به نزدیکترین همسایههایش استفاده کرده تا میزان انحراف را از محلی که در آن واقعشده است به دست آورد.
Kriegle و همکاران [12] روش را ارائه دادند که بر اساس آن به محاسبه واریانس زاویه بین دو بردار متفاوت از یک نقطه به نقطه دیگر در هر دستهبندی جهت شناسایی دادههای پرت اقدام میشد. Jiadong و همکاران [13] با ارائه روشی مبتنی بر گراف و همچنین با استفاده از الگوریتم کلونی مورچه برای تشخیص دادههای پرت اقدام نمودند. آنها با بهکارگیری الگوریتم کلونی مورچه اقدام به یافتن کوتاهترین گراف ممکن نمودند و این کار موجب نزدیک شدن دادههای مشابه به هم شده و تشخیص دادههای پرت با استفاده از آن راحتتر میگردد. این روش دارای دقت کمی بوده و تابع هزینهای با دقت پایینتری را ارائه مینماید.
