بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مروري برارزيابي ماشين بردارپشتيبان درتشخيص و طبقه بندي ايميل هاي اسپم
چکيده
يکي از ارتباطات اقتصادي سريع ايميل است ،افزايش کارابران ايميل باعث افزايش هرزنامه ها در سال هاي اخير شده است .هرزنامه نويس ها هميشه سعي مي کنند راه هايي براي فرار از فيلترهاي موجود بيابند بنابراين فيلترهاي جديد براي تشخيص هرزنامه ها نياز به توسعه دارند بيشتر اين فيلترها از ترکيبي از چندين روش مانند فهرست هاي سياه يا سفيد، استفاده از واژه هاي کليدي، فيلترهايي بر پايه قانون ،روشهاي يادگيري ماشين و غيره براي شناسايي دقيقتر هرزنامه ها بهره ميبرند.در اين مقاله به بررسي معيارهاي ارزيابي مانند دقت وصحت ونرخ خطا وکارايي ماشين بردارپشتيبان ماشين براي تشخيص وفيلترينگ هرزنامه ها مي پردازيم .
کليد واژه : يادگيري ماشين ,هرزنامه , ماشين بردار پشتيبان , داده کاوي, فيلترينگ اسپم
١ - مقدمه
تحت تاثير شبکه جهاني اينترنت زمان و فاصله ارتباطات به وسيله نامه الکترونيکي کاهش يافته است ، به همين دليل کاربران اغلب براي برقراري ارتباط با ديگران و ارسال با دريافت اطلاعات از ايميل استفاده مي کنند. .با توجه به تحقيقات اخير،٦٠ درصد از تمام ترافيک وپهناي باند , مربوط به ايميل هاي هرزنامه است .در اين راه مقدار بزرگي از پهناي باند به هدر مي رود ودر سيستم فرستادن ايميل سرريز رخ مي دهد. در واقع فيلتر هرزنامه ها ، يک برنامه کامپيوتري است که توانايي دسته بندي نامههاي الکترونيکي را دارا مي باشد ،اين برنامه با احتمال زيادي بايد قادر به تشخيص هرزنامه ها باشد.بيشتر اين فيلترها از ترکيبي از چندين روش مانند فهرست سياه ، و سفيد استفاده از واژه - هاي کليدي، فيلترهايي بر پايه قانون و غيره براي شناسايي دقيقتر هرزنامه ها بهره ميبرند. اين روشها خود ميتوانند به تنهايي فيلتري موثر باشند، ولي در کاربردهاي تجاري از ترکيب اين روشها استفاده ميشود. برخي از اين روشها به صورت دستي توسط کاربر تعيين ميشوند، از اين نوع فيلترها ميتوان به فيلترهاي استفاده شده در پست
الکترونيکي ياهو اشاره کرد. ولي اين روش ها يک ايراد عمده دارند و آن ثابت بودن قوانين مورد استفاده در اين فيلترها است ، که بايد تحت نظر کاربر تعيين شوند . مشکل ديگر اين روشها اين است که هرزنامه نويسان با ترفند هاي مختلفي ميتوانند اين فيلترها را فريب دهند. علاوه بر اين روشها، روش ديگري که محبوبيت بسياري پيدا کرده است ، شناسايي هرزنامهها بر اساس محتواي آنها است . که در اين چند سال اخير جدا کردن نامههاي معتبر و هرزنامه ها بر اساس محتوا پيشرفت چشمگيري داشته است ، در واقع جدا کردن نامههاي معتبر و هرزنامهها بر اساس محتوا را مي توان نوعي دسته بندي متن به حساب آورد چرا که بدنه اغلب نامهها به صورت متني است که با ورود هرزنامه ، دسته آن بايد تعيين شود. طبقه بندي ماشين بردار پشتيبان يا SVM، جز دسته بندي الگوريتم هاي تشخيص الگو است .از الگوريتم SVM، در هر جايي که نياز به تشخيص الگو يا دسته بندي در کلاس هاي خاص باشد مي توان استفاده کرد. آموزش نسبتا ساده است و براي داده هاي با ابعاد بالا تقريبا خوب جواب مي دهد. زمان اجراي آن نسبت به ساير طبقه بندي ها ازجمله Decision Tree,ve Bayesian, C٤٥Naiو...کم تراست , زيرا در مرحله Data Training از بردارهاي پشتيبان از ميان داده هاي پايگاه داده استفاده مي کند.
در اين مقاله به بررسي معيارهاي اندازه گيري ماشين بردار پشتيبان درفيلترينگ هرزنامه ها مي پردازيم .چهارچوب اين مقاله به اين صورت است که دربخش ٢به بيان مساله ايميل هرزنامه مي پردازيم . دربخش ٣ به معرفي ماشين بردارپشتيبان وروش هاي ترکيبي ومقايسه آنها مي پردازيم . دربخش ٤ انواع ديتاست هاي نمونه موجود و نرم افزارهاي ساخته شده براي مقابله با هرزنامه وليست معيار هاي اندازه گيري هرزنامه ها رامعرفي مي کنيم و بخش ٥ درباره نتيجه گيري وکارآينده است .
٢ - مساله ايميل هرزنامه
هرزنامه ايميل در سال ١٩٩٠ وقتي که وارد اينترنت شد تبديل به يک معضل شد و روز به روز افزايش يافت به صورتي که امروزه با يک تخمين محافظه کارانه ٨٠ تا ٨٥ درصد ايميل ها را در برمي گيردو در بعضي از منابع از ٩٥درصد بالاتر مي رود.هر روز ساعت هاي زيادي براي خواندن و مرتب کردن اين ايميل ها مصرف مي شود،که از لحاظ اقتصادي داراي اهميت است .از جمله مسائل ديگري که مرتبط با هرزنامه است ،از لحاظ تکنيکي است .اغلب هرزنامه ها مي توانند خطرناک باشند،شامل ويروس ،اسب تروا يا نرم افزار هاي خطرناک ديگري باشند و منجر به خرابي در رايانه ها و شبکه ها شوند. هرزنامه ها ابزار اصلي براي انجام حملات فشينگ شده اند حملاتي که هنگام شناسايي و تعيين هويت فرد در يک بانک يا سازمان ديگري،داده هاي بانکي او را دزديده و منجر به فريب آن ها مي شوند.تحت تاثير هرزنامه ها،مديران ايميل ها و شبکه ها براي گسترش سيستم ها براي نبرد با هرزنامه ها،مجبور هستند که تلاش کرده و زمان بگذارند.و به عنوان آخرين مساله ،دريافت پيغام هاي ناخواسته ،نوعي تجاوز به حريم محسوب مي شود و اغلب کاربران را مجبور مي کندکه موارد ناخواسته از جمله مسائل دور از اخلاق را ببينند.
٣. ارزيابي تشخيص و طبقه بندي هرزنامه بااستفاده از ماشين بردار پشتيبان
٣-١ معرفي ماشين بردار پشتيبان SVM
SVM دسته بندي کننده اي است که جزو شاخه Kernel Methods دريادگيري ماشين محسوب ميشود . SVM در سال ١٩٩٢ توسط Vapnik معرفي شده و بر پايه statistical learning theory بنا گرديده است . شهرت SVM بخاطر موفقيت آن در تشخيص حروف دست نويس است که با شبکه هاي عصبي بدقت تنظيم شده برابري ميکند: ١.١(% خطا) هدف اين دسته الگوريتم ها تشخيص و متمايز کردن الگوهاي پيچيده در داده هاست ( از طريق کلاسترينگ ، دسته بندي، رنکينگ ، پاکسازي و غيره ) .درSVM با فرض اينکه دسته ها بصورت خطي جداپذير باشند، ابرصفحه
هایی با حداکثر حاشیه را بدست می اورد که دسته ها را جدا کنند . در مسایلی که داده ها بصورت خطي جداپذير نباشند داده ها به فضاي با ابعاد بيشتر نگاشت پيدا ميکنند تا بتوان آنها را در اين فضاي جديد بصورت خطي جدا نمود. اگر دو دسته وجود داشته باشند که بصورت خطي از هم جداپذير باشند، بهترين جدا کننده اين دو دسته چيست ؟ الگوريتم هاي مختلفي از جمله پرسپترون ميتوانند اين جداسازي را انجام دهند. ايده SVM براي جدا سازي دسته ها اين است که : دو صفحه مرزي بسازيد : دو صفحه مرزي موازي با صفحه دسته بندي رسم کرده و آندو را آنقدر از هم دور ميکنيم که به داده ها برخورد کنند. صفحه دسته بندي که بيشترين فاصله را از صفحات مرزي داشته باشد، بهترين جدا کننده خواهد بود.
نزديکترين داده هاي آموزشي به ابر صفحه هاي جدا کننده بردار پشتيبان ناميده ميشوند . در صورت استفاده مناسب از SVM اين الگوريتم قدرت تعميم خوبي خواهد داشت , زيراعليرغم داشتن ابعاد زياد از overfitting پرهيز ميکند.
اين خاصيت ناشي از optimization اين الگوريتم است که در فشرده سازي اطلاعات استفاده مي شود در واقع بجاي داده هاي آموزشي از بردارهاي پشتيبان استفاده ميکند. براي حل مساله ما تعدادي نمونه هاي آموزشي داريم
که هرکدام عضوي از کلاس هاي y هستند و
تابع تصميم گيري در SVM خطي به صورت زير تعريف مي شود:
ابر صفحه جداکننده به صورت زيرتعريف مي شود:
ميخواهيم مقادير W, b رابگونه اي پيدا کنيم که نمونه هاي آموزشي را بدقت دسته بندي کند , با اين فرض که داده ها بصورت خطي جدا پذير باشند و حاشيه را حداکثر نمايد براي اين منظور مااز رابطه هاي زير استفاده مي کنيم :
دراين رابطه مقادير ياضريب دوگانه و b رابااستفاده از معادلات QP حل مي کنيم . مقادير جديدx درمرحله تست را دررابطه زير قرارمي دهيم :
براساس نوع داده ها و دامنه مساله توابع کرنل متفاوتي وجوددارد:
بنابراين معادلات حل مساله بااستفاده از تابع کرنل مشخص به صورت زير است :
در واقع الگوريتم SVM، جز الگوريتم هاي تشخيص الگودسته بندي مي شود.از الگوريتم SVM، در هر جايي که نياز به تشخيص الگو يا دسته بندي در کلاس هاي خاص باشد مي توان استفاده کرد. آموزش نسبتا ساده است برخلاف شبکه هاي عصبي در ماکزيمم هاي گير نمي افتد. براي داده هاي با ابعاد بالا تقريبا خوب جواب مي دهد. مصالحه بين پيچيدگي دسته بندي کننده و ميزان خطا به طور واضح کنترل مي شود. به انتخاب يک تابع کرنل خوب براي اجرا نياز دارد. زمان اجراي آن نسبت به ساير طبقه بندي ها ازجمله Decision Tree,ve Bayesian, C45Nai و...کم تراست , زيرا در مرحله Data Training از بردارهاي پشتيبان از ميان داده هاي پايگاه داده استفاده مي کند.
الگوريتم زير الگوريتم طبقه بندي SVM درشناسايي ايميل هاي اسپم است :
٣-٢ ارزيابي ومرور تشخيص و طبقه بندي هرزنامه براساس ماشين بردارپشتيبان
وپنيک طبقه بندي SVM را در سال ١٩٩٩ معرفي کرد و در همان سال مقاله اي درزمينه دسته بندي ايميل ها ي اسپم براساس طبقه بندي SVM ارائه داد.در اين مقاله سرعت ودقت ومعيارهاي اندازه گيري SVM با سايرطبقه بندي هاي ديگر ازجمل Ripper, Rocchio, and Boosting Decision trees مقايسه مي شود, در اين مقاله از TF-ID براي انتخاب ويژگي ها هم به صورت باينري وهم به صورت کيسه کلمات وحذف STOP Word هااستفاده کرده است ونشان مي دهد که سرعت اين الگوريتم به خاطر استفاده از بردارهاي پشتيبان در مرحله آموزش بسيار بالاتر از سايرطبقه بندي هاي ديگر است و دقت آن با الگوريتم Boosting بسيار نزديک است (١٠).
Woitaszek از طبقه بندي SVM به صورت خطي و يک ديکشنري خطي براي مدل کردن داده هاي آموزشي استفاده کرده است . آنها طبقه بندي پيشنهادي را برروي Microsoft Outlook XP اضافه کردند و توانستند با استنتاج خود برروي
Outlook ايمل هاي کاربران را گروه بندي کنند(١١).
Matsumoto نتايج آزمايش خود رابرروي دوروش طبقه بندي SVM و نيوبيزين پياده کردند آنها از TFو TF-IDF براي استخراج واژه ها استفاده کردند . نتايج آنها نشان داد که نيوبيزين کارايي بالاتري به نسبت SVM برروي مجموعه داده ها دارند(١٢).
Huai-bin Wang الگوريتم ترکيبي جديدي براي استخراج ويژگي هاي ايميل براساس الگوريتم ژنتيک و طبقه بندي SVM
به نام GA-SVM ارائه دادند , سپس اين روش را با SVM مقايسه کردند که الگوريتم پيشنهادي دقت بيشتري نسبت به
SVM دارند (١٣).
Scheffer چارچوبي براي يادگيري يک طبقه بندي با استفاده از پيام هاي عمومي در دسترس (برچسب دار) و پيام هاي کاربران بدون (برچسبدار) ارائه داده اند .در اين حالت که ايميل هاي N کاربر مشترک استفاده مي شود، طبقه بندي براي يک کاربر جديد با يادگيري SVM خطي ، که در آن هزينه ازدست دادن طبقه بندي پيام بر اساس برآورد اصلاح - طرفين واژه هاي هر پيام به دست مي آيد. نتايج آزمايش با استفاده از نمايش دودويي، برروي مجموعه داده Enron corpus که ايميل هاي اسپم را از منابع مختلف دولتي و خصوصي به دست آمده است .دراين تحقيق فرمول پيشنهادي ريسک (AUC _ ١) تا ٤٠درصد کاهش مي دهد، در مقايسه با کاربر از يک طبقه بندي واحد براي همه کاربران تاييد شد(١٤).
Kanaris از کاراکترهاي n - گرم استفاده کردند، هنگامي که Nاز قبل مشخص شده و يک متغير براي آموزش در SVMخطي است ، که در تحقيق خود از بازيابي اطلاعات براي انتخاب ويژگي ها و از نمايش باينري وفرکانس واژه ها TFاستفاده کردند .آزمايش برروي مجموعه داده هاي LingSpamو SpamAssassin ومدل هاي ٣-و٤- و٥- گرام و fold-١٠ cros-validation انجام شده است .مدل N - گرم برتراز روش ديگر است و نتايج نمايش براساس کلمات ، با متغير Nدر سناريو cost-sensitiveاست (١٥).
روش جديدي براي فيلترکردن اسپم براساس Online SVM مطرح شد که قابليت تطبيق با هر مجموعه آموزشي جديد وافزايشي وهرسيستمي دارد. در اين روش يک شرايط سازگاري براي پارامتر C ,(يکي ازمسايل اصلي در طبقه بندي SVM, انتخاب مقدار C براي به دست آوردن حداکثر فاصله ها بين دسته هاست ), معرفي مي کند و اين روش را با SVM مقايسه مي کند ودقت روش فوق ٠.١ از طبقه بندي SVM بيشتر است (١٦).
در تز دکتراي آنتون بريل يک پيشرفتي برروي طبقه بندي SVM براي شناسايي اسپم با محلي کردن داده ها انجام داده است . دراين تز دو الگوريتم پيشنهاد داده است يکي SVM Nearest Neighbor Classifre که از ترکيب و ادغام SVM و K Nearest Neighbor استفاده کرده است و ديگري HP-SVM-NN که الگوريتم قبلي را بادرجه احتمال بالا است و هر دو روش را با طبقه بندي SVM مقايسه کرده است ونشان داده است که الگوريتم هاي پيشنهادي دقت وسرعت بالايي نسبت به SVM دارند(١٧) .
Ye يک مدل متمايزي براساس SVM و تئوري D-S ارائه داد. آنها از SVM براي طبقه بندي و مرتب کردن ايميل ها براساس ويژگي هاي محتوي هدر وبدنه و از تئوري D-S براي تشخيص اسپم استفاده کردند که دقت خوبي را ارائه دادند(١٨).
Yu and Xu ٤ الگوريتم ماشين يادگيري را باهم مقايسه کردند NB, NN,SVM, RVM نتايج آزمايش نشان داد که طبقه بنديNN برسايز مجموعه آزمايش بسيار حساس است وبه صورت تنها نامناسب براي رد کردن ايميل اسپم است .RVM ,SVM عملکرد خيلي بهتراز NB داشتند و RVM زمان تست بالاتري نسبت به SVM داشت (١٩).
Sun از دو الگوريتم LS-SVM ,LPP براي فيلترينگ اسپم استفاده کردند , از الگوريتم LPP براي استخراج ويژگي هاازايميل واز الگوريتم LS-SVM براي طبقه بندي و تشخيص ايميل اسپم از غيراسپم استفاده کردند. نتايج نشان داد که کار آنها عملکرد بهتري در مقايسه با طبقه بندي هاي ديگر دارد(٢٠).
Qinqing Ren چهارچوبي براي انتخاب ويژگي هاي فيلترکردن ايميل هاي اسپم با استفاده از طبقه بندي SVM ارائه داده است .در اين روش اطلاعات از ايميل به صورت ويژگي ها با استفاده از فرمول فرکانس ويژگي ها ( TF-IDF) وافزايش وزن کلماتي که در هدر ايميل وجود دارد استخراج مي شوند(٢١).
Liu Yuguo تابع کرنل ترتيبي براي طبقه بندي SVM بانام DPWSK پيشنهاد دادند که اين تابع کرنل براساس معيارهاي وابستگي ساخته شده است وتوانايي تشخيص کلمات خالص ازميان دانش موجود و قابليت محاسبه معيار شباهت معنايي در متن راداردونسبت به طبقه بندي SVM دقت بالايي دارد(٢٢).
يک الگوريتم ترکيبي پيشگو براي تشخيص صحفات با استفاده از منطق فازي و الگوريتم ژنتيک و طبقه بندي SVM ارائه شده است . اين الگوريتم با استفاده از قوانين فازي و الگوريتم ژنتيک مي تواند خطاهارا در صحفات تشخيص دهد وبراساس طبقه بندي SVM آنها را طبقه کند در مقايسه با خود طبقه بندي SVM دقت وکارايي بالاتري دارد(٢٣).
خلاصه مطالب اين بخش :
جدول ١- مروري براستفاده ماشين بردار پشتيبان در ايميل هاي هرزنامه
