بخشی از مقاله
شناسایی هرزنامهها با استفاده از الگوریتم دستهبندي درخت تصمیم با یک رویکرد مبتنی برکاهش بُعد، تحلیل مولفههاي اساسی
چکیده
محبوبیت روزافزون و کم بودن هزینـه پسـتالکترونیکـی ایـن زمینـه را فـراهم کـرده اسـت تـا بسـیاري اقـدام بـه ارسـال نامـههـاي الکترونیکـی ناخواسته درحجـم انبـوه کننـد. ایـن نامـههـا بـه اصـطلاح هرزنامـه نامیـده مـیشـوند. هرزنامـههـا یکـی از بزرگتـرین مشـکلات کـاربران پسـت الکترونیکی هستند که سبب اتلاف وقت، کـاهش امنیـت و کـاهش کـارایی کـامپیوتر مـیشـوند. بـراي غلبـه بـر ایـن مشـکل روشـهاي مختلفـی ارائه شدهاست. در این مقاله یک روش براي شناسایی و دسـته بنـدي ایمیـلهـا بـه دو دسـته هرزنامـه یـا اسـپم و نامـه معتبـر بـا غیـر اسـپم بـر اســاس الگــوریتم درخــت تصــمیم ارائــه نمــودهایــمدر. روش پیشــنهادي از الگــوریتم کــاهش بُعــد، تحلیــل مولفــههــاي اساســی((PCAبــراي کــاهش بُعــد فضــاي ویژگــیهــا اســتفاده نمــودهایــم و همچنــین الگــوریتم ترکیبــی Baggingرا روي الگــوریتم درخــت تصــمیم اِعمــال
نمــودهایــم. روش پیشــنهادي روي مجموعــه داده اســتاندارد، Lingspam ارزیــابی شــده اســت. تــاکنون الگــوریتمهــاي زیــادي بــراي شناســایی هرزنامهها توسط الگـوریتمهـاي یـادگیري ماشـین در مقـالات ارائـه شـده کـه نتـایج حاصـل از ارزیـابی روش پیشـنهادي نشـان مـی دهـد کـه روش پیشنهادي باعث بالابردن معیارهاي دقت، صحت ،بازخوانی و کارایی دستهبندي هرزنامهها شده است.
کلمات کلیدي
پستالکترونیکی، هرزنامه ، یادگیري ماشین ، دستهبندي، کاهش بُعد ، درخت تصمیم ، الگوریتم ترکیبی.
-1 مقدمه
اینترنــت، امکــان اســتفاده از ســرویسهــا و خــدمات متعــدديرا در اختیــار کــاربران قرارمــیدهــد. ارســال و دریافــت نامــهالکترونیکــی یکــی از قــدیمیتــرین و در عــین حــال متــداولترین ســرویس ارائــه شده بـر روي اینترنـت اسـت. علیـرغم تمـامی مزایـا و پتانسـیلهـاي سـرویس فـوق، در چنـد سـال اخیـر و همزمـان بـا رشـد و گسـترش اســتفاده از اینترنــت، شــاهد مشــکلات و مســائل جــانبی در ایــن رابطه نیز میباشیم. توزیع نامههـاي آلـوده بـه ویـروسهـا و یـا کـرم-هـا، ارسـال و یـا دریافـت نامـههـاي الکترونیکـی ناخواسـته یـا همـان هرزنامـههـا، نمونـههـایی در ایـن زمینـه مـیباشـند. بـراي مقابلـه بـا هرزنامــههــا تــاکنون روش هــاي متعــددي ایجادشــده و ایــن رونــد بــا توجه به ابعاد گسترده آن، همچنان ادامه دارد. [1]
بهتــرین تکنولــوژي کــه در حــال حاضــر بــري توقــف هرزنامــه وجــود دارد، اســتفاده از نــرم افزارهــاي فیلترینــگ اســت. ایــن نــوع
برنامــههــا، وجــود کلیــد واژههــاي خاصــی را در خــط موضــوع نامــه و درون مــتن نامــه بررســی و در صــورت شناســایی، نامــهالکترونیکــی مـورد نظـر را حـذف مـینماینـد. بـراي امـلاء1کـردن یـک کلیـدواژه، روش هــاي متعــددي وجــود داشــته و در برخــی مــوارد ممکــن اســت فرآیند اسپل یـا امـلاي واژههـا نتـایج مطلـوبی را بـه دنبـال نداشـته و باعث حذف نادرسـت نامـههـایی گردنـد کـه تمایـل بـه دریافـت آنـان را داشته باشیم. [2]
در نتیجــه امــروزه از برنامــههــاي فیلترینــگ پیشــرفته، کــه بــر اســاس الگــوریتمهــاي یــادگیري ماشــین ایجــاد شــدهانــد و توســط مجموعـــه دادههـــاي اســـتاندارد آمـــوزش داده شـــدهانـــد جهـــت شناســـایی هرزنامـــهاســـتفاده مـــینماینـــد. [3]در ایـــن مقالـــه از الگــوریتمهــاي کــاهش بُعــد بــه همــراه الگــوریتمهــاي ترکیبــی دسـتهبنــدي یــادگیري ماشــین یــک مــدل جدیــد طراحــی نمــودهایــم کــه نســبت بــه فیلترهــاي پیشــین داراي دقــت، صــحت، بــازخوانی و کارایی بالاتري میباشد.
-2 الگوریتم درخت تصمیم2
درخت تصمیم یک روش دستهبندي با نظـارت در روشهـاي یـادگیري ماشین است. گرههاي درخت، ویژگیهـاي مسـئله هسـتند. در درخـت ایجادشده مهمترین ویژگی بهعنوان ریشه درخت قرار میگیـرد و بقیـه ویژگیها به ترتیب اهمیت در سطوح پایینتـر درخـت قـرار دارنـد ودر نهایت برگهاي درخت، نتیجه دستهبندي یا همان کلاسها را نمایش میدهند. [4]
براي ساختن درختهاي تصمیمگیري از یک استراتژي تقسـیم و غلبه استفاده میشود. در واقع یک مجموعه آموزش داریم که باید آن را تقسیم بندي کنیم. براي یک مجموعه آموزش M ، با اسـناد برچسـب-گذاري شده باید کلمه ti براي تقسیمبندي مجموعـه آمـوزش انتخـاب شود. سپس M بر اساس ترم ti انتخاب شده به دو زیر مجموعه تقسیم میشود. زیر مجموعه Mi+ شامل اسنادي است که شامل ti هسـتند و زیر مجموعه Mi- شامل اسنادي است که ترم ti در آنها نیست. همین فرآیند را براي Mi+ و Mi- تکرار میکنیم و اینکار را ادامه میدهیم تا زمانی که همه اسناد موجود در یک زیر مجموعه متعلق به یک کـلاس (مثلا همه متعلق به کلاس Lc باشند) که در این صـورت برچسـب آن نود برابر با کلاس متناظر با اسناد میشود و آن نود تبدیل به برگ می-گردد و دیگر آن را تقسیم نمیکنیم یا اینکه فرآیند را تـا زمـانی ادامـه میدهیم که دیگر ترمی براي تقسیمبندي زیر مجموعهها وجود نداشته باشد که در اینصورت برچسبی را روي آن میگذاریم که اکثریت اسـناد آن بخش، آن برچسب را دارند.
-3الگوریتم ترکیبی Bagging
استفاده از الگوریتمهاي ترکیبی باعث کاهش خطا مـیشـوند. در واقـع هنگامی که براي رسیدن به خروجی نهایی، خروجی حاصل از چنـدین دستهبند با یکدیگر ترکیب شوند، منجر بـه ایـن امـر خواهـد شـد کـه دستهبندها خطاي یکدیگر را بپوشانند. بطوریکه هر چه تعـداد دسـته-بندهاي ضعیف در روشهاي ترکیبی بیشـتر باشـد، خطـاي دﺳـﺘﻪﺑﻨـﺪ نهایی به میزان بیشتري کاهش مییابد. بدیهی است نکته منفی کـه در اینجا وجود دارد کندتر شدن فرآیند یادگیري الگوریتم ترکیبی خواهـد بود. [5]
Bagging یک الگوریتم ترکیبی یا تجمیعـی اسـت. در ایـن روش مجموعه داده اصلی با استفاده از روش نمونهبرداري بـا جایگـذاري، بـه تعدادي مجموعه داده تقسیمبندي میشود. [6]
اي پیدا کنیم که اولاً k ≤ pباشد و ثانیاً s محتویـاتی کـه در x وجـود دارد را بر اساس معیاري خاص دارا باشد. روشهاي خطی سعی میکنند هر یک از این k مؤلفه را از ترکیب خطی p مؤلفهي اولیه بدست آورند. 4PCA تصویر بیشترین واریانس را به دسـت مـی آورد. عملکـرد ایـن روش به این صورت است که ابتدا میانگین دادهها (بر روي هر بُعد)را از دادهها کم میکند و دادههاي جدید با مینگین صـفر تولیـد مـینمایـد. سپس ماتریس کوواریانس دادههاي جدید محاسبه می شود.
بردارهاي ویژه یکه ماتریس کوواریانس را می توان به عنوان بـردار ویژگی در نطر گرفت زیرا به نوعی پراکندگی دادهها را نشان مـیدهـد. دادههاي نهایی، با ضرب بردارهاي ویژگی در دادههاي با میانگین صـفر به دست می آیند.در حقیقـت، دادههـاي نهـایی از دَوَران دادههـاي بـا میانگین صفر به دست میآیند به صورتی که محورهاي مختصات آنهـا بردارهاي ویژه ماتریس کوواریانس شود. [7]
بــا دقــت در مقــادیر ویــژه مــاتریس کوواریــانس مــی تــوان ابعــاد فضـــاي ورودي را کـــاهش داد، بـــدون اینکـــه اطلاعـــات زیـــادي از دســت بــرود.PCA روشــی اســت بــراي شناســایی الگوهــا در داده-ها،همچنین نمایش دادههـا بـه شـکلی کـه شـباهتهـا و تفـاوتهـاي آنها پررنگتر شود.
الگوریتم PCA بهترین روش براي کاهش ابعاد داده به صـورت خطی میباشد. یعنی با حذف ضرایب کماهمیـت بدسـت آمـده از ایـن تبدیل، اطلاعات از دست رفته نسبت به روشهاي دیگر کمتـر اسـت. در این روش محورهاي مختصات جدیدي براي دادهها تعریف شده و داده-ها براساس این محورهاي مختصات جدید بیان میشوند. اولـین محـور باید در جهتی قرار گیرد که واریانس دادهها ماکسیمم شـود (یعنـی در جهتی که پراکندگی دادهها بیشتر است). دومین محور بایـد عمـود بـر محور اول به گونهاي قرار گیرد که واریانس دادهها ماکسیمم شـود. بـه همین ترتیب محورهاي بعدي عمود بر تمامی محورهاي قبلی به گونه-اي قرار میگیرند که دادههـا در آن جهـت داراي بیشـترین پراکنـدگی باشند . در شکل((1 این مطلب براي دادههاي دو بعدي نشان داده شـده است. [8]
شکل :(1)انتخاب محورهاي جدید براي دادههاي دو بعدي
5- مراحل روش پیشنهادي
1-5- استخراج کلمات
4کاهش- بُعد تحلیل مولفههاي اساسی3 مسئلهي کاهش ابعاد داده را بطور ریاضی میتوان بـه اینصـورت بیـان کرد: یک متغیر تصادفی -pبعديداریم توسط عملگرTokenize در محیط شبیهساز کلمـات مـتن را اسـتخراج میخواهیم متغیر -kبعدي را به گونه- مینماییم.
مانند کلمات با طول مشخص، حداقل 3 و حداکثر 20، با این عملگـر کلمات یک و دو حرفی که بی معنی هستند حذف میشوندواین باعـث کم شده تعداد کلمات و تعداد ویژگیها میشود.
5-2حذف کلمات زائد
حذف کلمات زائد و تکراري5، کلمات زائد کلمـاتی هسـتند کـه حـاوي اطلاعات چندانی نمیباشند، به علاوه در تمامی متون بـه تعـداد زیـاد وجود دارند و تاثیري در متمایز ساختن متن نسـبت بـه سـایر متـون ندارند، مانند حروف ربط و حروف اضافه از قبیل .is , are , and, the
5-3 ریشه یابی کلمات
ریشهیابی کلمات6، در ریشهیابی به جاي مشـتقات مختلـف یـک کلمـه، ریشه کلمه آورده میشودو بدین ترتیب تعـدادکلمات سـند تاحـدودي کاهش مییابد. مثلا باحذف پسوندهـاي کلمـات playing و played کلمه ریشه یعنی play به عنوان ویژگی اسـتخراج مـیشـود و مـابقی مشتقات آن حذف میشوند.
4- 5 تشخیص عبارت چند کلمهاي
اسـنادي از مجموعـه آموزشـی کـه کلمـه k در آن ( k (t در رابطــه (1) کــه N نماینــده تعــداد کــل اســناد و تعـداد حـداقل یـک بـار رخ داده، میباشـد. tf(tk,dj) نیـز نشـان دهنـده تعـداد
تکرارهــاي کلمــه kام در ســند jام اســت. بــه ایــن ترتیــب رخــدادبیشتر یـک کلمـه در صـورتی در افـزایش وزن آن مـؤثر اسـت کـه در همه متون دیگـر تکـرار نشـده باشـد . [10] بـا توجـه بـه اینکـه ایـن روش در کارهاي زیـادي مـورد اسـتفاده قـرار گرفتـه و کـارایی خـوب آن روي مجموعـه دادههـاي متفـاوتی بـه اثبـات رسـیده اسـت، در این مقاله نیز از این روش استفاده شده است. مراحــــل (5-1) و((5 -2و((5-3و((5-4و((5-5 را در ایــــن مقالــــه پیش پردازشهاي پایه گفته میشوند.
5-6 کاهشبُعد فضايبرداريدادهها توسطالگوریتم PCA
-7اِعمال5 الگوریتم ترکیبی Bagging روي درخت تصمیم
-6 پیاده سازي
تشخیص عبارت چنـد کلمـهاي (n-gram)، نحـوه تشـخیص عبـارات بستگی به انتخاب مقدار n دارد به ازاي n=1 یعنی عبارات یک کلمهاي به ازاي n=2 یعنی عبارات دو کلمهاي به ازاي n=3 یعنی عبـارات سـه کلمهاي وهمین طور بیشتر. براي پیادهسازي مُدل پیشنهادي از نرمافزار شبیهساز، Rapidminer در روش پیشــنهادي بــه ازاي n=2 و n=3 مــورد آزمــایش قــرار که یک نرمافزار متن باز به زبان جاوا میباشد استفاده شده است.
گرفتندولی نتایج به میزان قابل ملاحظـهاي تغییـر نیافتنـد. بـه خـاطر اینکه براي n=3 زمان بیشتري صرف میشد بنابراین n=2 را یعنی -7 آزمایشها
2-Gram را انتخاب نمودهام.
در این مقاله سه آزمایش انجام گرفته است که عبارتند از:
5-5 ایجاد بردار ویژگیها
اِعمال پیش پردازشهاي پایه روي دادهها سپس آزمایش شماره (1 براي ایجاد بـردار ویژگـیهـا از روش فرکـانس عبـارت، عکـس دسته بندي دادهها توسط درخت تصمیم.
فرکانس سند (TF-IDF) استفاده شده است. اِعمال پیش پردازشهاي پایه روي دادهها بعد آزمایش شماره (2
این روش براي حـل مشـکل فرکـانس سـند ارائـه شـده اسـت. اِعمال الگوریتم کاهش بُعد روي دادهها، سپس دسته بندي دادهها در ایــن روش دو فــاکتور در نظــر گرفتــه مــیشــود. یکــی فرکــانس توسط درخت تصمیم.
عبــارت در یــک ســند (tf) و دیگــري عکــس بســامد عبــارت در کــل آزمایش شماره 3اِعمال) پیش پردازشهاي پایه روي دادهها بعد اسناد .(idf) این روش بـر ایـن بـاور اسـت کـه عبـارتی کـه در تعـداد اِعمال الگوریتم کاهش بُعد روي دادهها، سپساِعمال الگوریتم ترکیبی زیـادي از اســناد باشـد بســیار عمـومی بــوده و مهـم نمــیباشـد و لــذا Bagging روي الگوریتم درخت تصمیم جهت دسته بندي دادهها.عکس فرکانس سند را در نظـر مـیگیـرد. در عـین حـال اگـر عبـارت در یک سند زیـاد تکـرار شـده باشـد، اهمیـت آن را نشـان مـیدهـد.
بنــابراین روش TF.IDF بــا ضــرب ایــن دو فــاکتور در یکــدیگر بــه یک معیار براي انتخـاب عبـارت مـیرسـد. ایـن روش جـزء روشهـاي خوب و ساده در انتخـاب ویژگـی بـه حسـاب مـیآیـد زیـرا بـه حجـم
