Description

مباحثی در علوم کامپیوتر استاد درس: دکتر اکبریتمرین دوم: تشخیص هرزنامه ها دانشگاه صنعتی امیرکبیر۴ آذر ۹۹۳۱ دانشکده ریاضی و علوم کامپیوتر

امروزه هرزنامه ها به یک مشکل بزرگ تبدیل شده اند. با رشد سریع کاربران اینترنت، ایمیل هایناخواسته نیز در حال افزایش است. مردم از آن ها برای کارهای غیرقانونی و غیراخلاقی، تقلب و کلاه برداریاستفاده می کنند؛ ارسال لینک های مخرب از طریق ایمیل های هرزه که می تواند به سیستم شما آسیب برساندو هم چنین می تواند در سیستم شما به راحتی جستجو کند. ایجاد یک حساب ایمیل جعلی برای اسپمرهابسیار آسان است، آن ها در ایمیل های خود نقش یک فرد واقعی را بازی می کنند. این اسپمرها افرادی رامورد هدف قرار می دهند که از این کلاه برداری ها آگاهی ندارند. بنابراین ،لازم است هرزنامه ها را شناساییکنید که به جلوگیری و یا حتی کاهش تبعات این ایمیل ها کمک کنید.
۱ شرح پروژه
در این پروژه با استفاده از تکنیک های یادگیری ماشین ،اسپم ها را شناسایی می کنید. شما باید ماژولی رابنویسید که طبقه بندی را با الگوریتمKNN اجرا کند. برای این، هر ایمیل را به عنوان برداری از تعدادکلمات نـمایش بدهید، که طول بردار هم اندازه واژگان است (برای هر داده ی آموزشی). طبیعی است کهبیش تر ورودی ها برابر با صفر شوند. به عنوان مثال، فرض کنید 0001=V ، و شاخص کلمهcheap ،25=i باشد. اگر ایمیلm هفت بار کلمه یcheap در آن ظاهر شود ،پس اندیس 52 در بردار نـمایش آن،برابر 7 است. برای طبقه بندی، شما باید برای هر ایمیل در مجموعه آزمون ،شباهتش هر یک از ایمیل هایمجموعه آموزش را با استفاده از معیار تشابه کسینوسی محاسبه کنید. سپس برای تعيين کلاس ایمیل ،k بالاترین ایمیل های مشابه را در نظر بگیرید. معیار تشابه کسینوسی به شرح زیر محاسبه می شود:
(۱)
که در آنxiA تعداد کلمه ی با اندیسi در ایمیلA است.
۱ .۱ محاسبه فاصله باtf-idf
در این بخش، شما باید فاصله کسینوسی را با فاصلهtf-idf جایگزین کنید. فرض کنیدn ایمیل در مجموعهآموزشی موجود باشد و آن ها را به شکلe1,e2,…,en نمایش دهیم. برای هر ایمیل جدید مانندˆe شاملدنباله کلماتw1,w2,…,wT میزان شباهت ˆe وei به شکل زیر تعریف می گردد:
Scoretf-idf (۲)
۱
در عبارت ۲ مقادیر (ˆtf(wi,e و (idf(wi به شکل زیر محاسبه می گردند:
tf(wi,eˆ) = log(count(wi,eˆ) + 1) (۳)
idf (۴)
در عبارت ۳ منظور از (ˆcount(wi,e تعداد رخداد کلمهwi در ایمیل ˆe است. همچنین، در عبارت ۴ منظوراز (df(wi تعداد ایمیل هایی است که حاوی کلمهwi هستند.
۲ .۱ پیکره
پیکره هرزنامه شریف شامل ۱۰۰۰ ایمیل است که ۵۰۰ مورد آن هرزنامه و ۵۰۰ مورد دیگر ایمیل عادیمی باشد. هر ایمیل در قالب یک فایلtxt ارائه شده است. در این فایل ممکن است علاوه بر متن ایمیل،اطلاعاتی جزئی در مورد فرستنده، گیرنده و تاریخ ارسال ایمیل نیز موجود باشد. کل پیکره در قالب ۴ پوشهزیر قابل دسترس است:
•hamtraining مجموعه ایمیل های عادی آموزشی ۳۰۰( نمونه)
•hamtesting مجموعه ایمیل های عادی آزمایشی ۲۰۰( نمونه)
•spamtraining مجموعه هرزنامه های آموزشی ۳۰۰( نمونه)
•spamtesting مجموعه هرزنامه های آزمایشی ۲۰۰( نمونه)برای دریافت این پیکره به لینک زیر مراجعه کنید:
https://github.com/omidrohanian/Spam-Filtering-For-Persian/tree/master/emails
۳ .۱ پیش پردازش
قبل از شروع فرآیند یادگیری، باید ابتدا مراحل زیر را روی هر فایلtxt اعمال کنید:
۱. حذف کاراکترهای غیر فارسی شامل حروف انگلیسی، اعداد و علائم خاص مانند نقطه، علامت سوالو علامت تعجب
۲. جداسازی کلمات (هر ایمیل به لیستی از کلمات تبدیل شود)
۳. حذف ایست واژه ها
۴. ریشه یابی کلمات (هر کلمه با ریشه خود جایگزین گردد)
نکته: برای این مراحل می توانید از ماژول هایی مانندHazm یاParsivar نیز کمک بگیرید. توجهداشته باشید همین مراحل باید روی داده های آزمایشی نیز قبل از ورود به مدل اعمال شوند.
۲
۴ .۱ محاسبه مهم ترین کلمات
پس از پیش پردازش داده ها، لطفا با استفاده از یکی از معیارهای 2χ و یاinformation gain مهم ترین کلماتیرا که در تشخیص نوع ایمیل نقش دارند مشخص کنید. برای این کار می توانید تعداد کلمات را معادل ۰۰۲یا ۵۰۰ در نظر بگیرید.
۱ .۴ .۱ تکرار آزمایش ها با مهم ترین کلمات (امتیازی)
پس از محاسبه مهم ترین کلمات، بقیه کلمات را از پیکره حذف کنید و آزمایش ها را تکرار نماييد. نتیجه رابا قسمت قبل مقایسه کنید.
۵ .۱ مقایسه با الگوریتمNaive Bayes (امتیازی)
پس از تبدیل ایمیل ها به لیستی از کلمات، فرض کنید یک ایمیل به شکل زیر در آمده است:
w1w2w3 …wn
که در آنwi ها هر کدام یک کلمه هستند. شما باید احتمال تعلق این ایمیل به مجموعه هرزنامه ها ومجموعه ایمیل های عادی را محاسبه کنید. به عبارت دیگر به دنبال مقادیر زیر هستیم:
P(spam|w1w2 …wn) (۵)
P(ham|w1w2 …wn) (۶)
مثلا اگر مقدار عبارت ۶ بزرگتر از عبارت ۵ باشد، ایمیل به مجموعه ایمیل های عادی تعلق دارد. توجه کنیدکه برای دریافت نمره مربوط به این قسمت، حتما باید کل الگوریتمNaive Bayes را خودتان پیاده سازی کنیدو استفاده از ماژول های آماده مجاز نیست. در صورت پیاده سازی این قسمت، باید نهایتا کارایی آن را باالگوریتمKNN از طریق معیارهای ارزیابی که در ادامه ذکر می گردند مقایسه کنید.
۶ .۱ معیارهای ارزیابی
برای این تمرین از شما انتظار می رود سیستمی را که پیاده سازی کرده اید، با استفاده از معیارهایPrecision ،Recall وF1-Score ارزیابی نماييد. همچنین ماتریس سردرگمی را نیز بدست آورده و گزارش نماييد.
۲ معیارهای تصحیح
پاسخ شما به این تمرین بر اساس موارد زیر ارزیابی می شود:
• پیاده سازیKNN توسط شما
• پیش پردازش و آماده سازی داده ها
• محاسبه فاصله کسینوسی و امتیاز بر حسبfdi-ft
۳
• پیاده سازی الگوریتمNaive Bayes و مقایسه خروجی دو مدل (امتیازی)
• محاسبه مهم ترین کلمات
• تکرار آزمایش ها با استفاده از مهم ترین کلمات (امتیازی)
• ارزیابی مدل ها
• گزارش شامل تحلیل شما از نحوه عملکرد سیستم
۳ نکاتی از تمرین قبل
در پروژه های ارسال تمرین قبل، اشکالات رایج و ساده ای وجود داشت که اشاره ی کوتاهی به آن ها می کنیم،تا در پروژه های بعدی عملکرد بهتری داشته باشیم): .
• برایخواناوتـمیزبودنکد،می توانیدازکامنت هایواضحویاقطعه هایمارک دان درنوت بوک هایتاناستفاده کنید.
• انـجام این نوع پروژه ها بدون تـحلیل خروجی و نتیجه های به دست آمده، لطفی ندارد. لطفا اینموارد را به گزارش هایتان اضافه کنید.
۴ نحوه ارسال پاسخ
لطفا از این تمرین یک نوت بوک اصلی داشته باشید که نشان دهنده مسیر اصلی اجرای کد شما باشد. اگرمی خواهید بخشی از کدهایتان را در فایل دیگری ذخیره کنید، می توانید با استفاده از دستورimport از آندر این نوت بوک بهره ببرید. از شما انتظار می رود موارد زیر را در قالب یک فایلzip ارسال نماييد:
• یک نوت بوک (فایل با پسوندipynb )
• یک فایلpdf که شامل گزارش شما است.
• هر گونه فایل دیگری با پسوندpy که از آن در نوت بوک استفاده کرده اید.
مهلت ارسال پاسخ: جمعه ۱۴ آذرماه ۹۹۳۱
مهلت ارسال با تاخیر ۱۰( درصد کسر نمره به ازای هر روز): دوشنبه ۱۷ آذرماه ۹۹۳۱ارتباط با ما
https://t.me/autsocialmedia :کانال تلگرام
ایمیل: یاسمن امی آرمان ملک زاده
malekzadeh@ieee.org yassi.ommi@gmail.com !موفق باشید
۴