اسپم و فیلترکردن عمومی آن با استفاده از روش Naïve Bayesian
رئوس مطالب
مروری بر پدیده اسپم
روشهای مبتنی بر یادگیری برای فیلترکردن اسپم ها
روش Naïve Bayesian برای فیلترکردن اسپم
معیارهای ارزیابی
بررسی نتایج
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
2
Spam/junk/bulk Emails
پیغامهایی در Inbox شما هستند که شما آن ها را نخواسته و زمانی را برای بیرون انداختن آنها صرف می کنید.
در مقابل آن : نامه های الکترونیکی معتبر یا ham
75-80% از حجم نامه های الکترونیکی را اسپم ها (spam) تشکیل می دهند
باعث ایجاد ترافیک شده و فضای حافظه و قدرت محاسباتی را از بین می برد
باعث ضرر اقتصادی
هزینه ای بالغ بر 50 میلیون دلار بر اقتصاد امریکا در سال 2005 وارد ساخته
با توجه به شخص و سازمان گیرنده ایمیل، اسپم ها تعریف می گردند
ایمیل های در حوزه هنر برای شخصی که علاقه ای به هنر ندارد اسپم تلقی می شود
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
3
ایمیل های اسپم
Subject: AWARD CONFIRMATION
We wish to congratulate you over your email success in our computer BALLOTING SWEEPSTAKE held on 16th Nov, 2007. This is a millennium scientific computer game in which email addresses were used. It is a promotional program aimed at encouraging internet users; therefore you do not need to buy ticket to enter for it.
“ You have won!!!!“, you are almost winner of $…
“Your order”, your item$ have to be $hipped
“Lose your weight”, no subscription required
“Assistance required”, an amount of million 25 US$
“Download it”, free celebrity wallpapers download
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
4
نمونه هایی از ایمیل های اسپم
بیشتر به منظور اهداف اقتصادی است
تبلیغ برای یک کالای خاص، سرویس خاص و یا یک ایده خاص
فریب کاربران برای استفاده از اطلاعات محرمانه آنها phishing
انتقال یک نرم افزار خرابکار به کامیپوتر کاربر (مثلاً ویروس)
ایجاد یک خرابی به صورت موقتی در Mail-Server
ایجاد ترافیک
پخش مطالب غیراخلاقی
اسپم ها دائما در حال تغییر محتوا و شکل هستند، برای اینکه توسط آنتی اسپم ها شناسایی نشوند.
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
5
برخی از اهداف ایمیل های اسپم
روشهای اقتصادی
دریافت وجه برای ارسال ایمیل : مانند پروتکل Zmail
روشهای قانون گذاری مانند قانون US-CAN SPAM
امن سازی بسترانتقال ایمیل
تغییر پروتکلهای انتقال ایمیل (مثل SMTP) و ارانه پروتکل های جایگزین مانند SenderId
کنترل ایمیل های خروجی در برابر کنترل ایمیل های ورودی
فیلترینگ ایمیل ها
اسپم و فیلترکردن عمومی آن با استفاده از روش Naïve Bayesian
6
تکنیک های مبارزه با اسپم ها و کنترل آنها
1- فیلترینگ براساس یکسری قاعده از پیش تعریف شده:
if $SENDER$ contains “schacht” $ACTION$=$INBOX$ [HAM]
if $SUBJECT$ contains “Win” $ACTION$=$DELETE$ [SPAM]
if $BODY$ contains “%%Money%%” $ACTION$=$DELETE$ [SPAM]
مشکلات: قوانین ثابت، وابستگی به زبان، چه تعداد قانون؟، چه کسی باید قوانین را تعریف
کند
2- فیلترینگ براساس لیست سیاه و سفید (Black list-white list)
3- فیلترینگ مبتنی بر یادگیری (آماری) و با استفاده از ویژگیهای پیغامها
در یادگیری ماشینی برای عمل دسته بندی (Classification) از نمونه داده هایی (ایمیل هایی) که از قبل فراهم شده است(داده آموزش یا training) و هر یک دسته(کلاس،برچسب) مشخص دارد، استفاده کرده و دسته(کلاس) یک نمونه جدید(تست) را تعیین می کنیم.
بردار پارامترها( ویژگی ها) θ حاصل آموزش دسته بند با استفاده از یک مجموعه داده است که قبلاً جمع آوری شده است
نیز تابع آموزش (Training) می باشد
تست داده جدید: m’ یک ایمیل جدید است و دسته آن را می خواهیم (spam or ham?)
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
7
فیلترینگ مبتنی بر یادگیری (آماری) و با استفاده از ویژگیهای پیغامها
مجموعه داده آموزش (training Data): M
دو نوع کلاس(برچسب) : اسپم و ایمیل معتبر (ham)
یادگیری Offilne
داده های آموزش با کلاس(برچسب) مشخص، قبلا جمع آوری شده است و ما در طی دسته بندی از همین داده های ثابت استفاده می کنیم
<email type=“HAM_email”>Soha! sorry cannot reach at 18:00</email>
<email type=“spam”>hi, have you thought online credit?</email>
….
یادگیری Online
کاربر طبقه بندی هایِ غلط دسته بند را تصحیح می کند و برچسب صحیح را معین می کند؛ به این ترتیب حجم داده آموزش به تدریج افزوده می شود و دانش دسته بند افزایش می یابد
مثال: در سرویس ایمیل Yahoo! می توان بر روی “spam” و یا “not spam” کلیک کرد و بدین ترتیب Yahoo! از کاربر Feedback می گیرد
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
8
متدهای یادگیری
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
9
یادگیری Online: Yahoo Mail
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
10
شمای کلی مدل
test
training
انتخاب ویژگی Feature Selection
(x2)
classify
Evaluate
Ham?
Spam?
ویژگیهای به صورت لغت (Tokenization)
ویژگی های وابسته به دامنه
ویژگیها ی به صورت عبارات دست ساخته
استخراج ویژگی ها
Feature Extraction
دسته بند(Classifier)
test
مراحل:
داده های آموزش شامل ایمیل های برچسب خورده
دو کلاس مشخص: Spam و Ham
استخراج ویژگی ها
توکن بندی متن تشخیص کلمات حذف Stopwords(مثل if,and اگر، به، با،…) ریشه یابی کلمات (Stemming) حذف علامات نقطه گذاری مثل ؛ ، …. ویژگیهای به صورت لغت
عبارات دست ساخته که متمایز کننده می باشند مثل$$Money$$
ویژگی های مشخصه دامنه مثل To، From، تاریخ ارسال پیام، اندازه پیام، …
انتخاب ویژگی های برتر : Feature Selection
دسته بندی ایمیل به عنوان اسپم و یا ایمیل معتبر
دسته با احتمال بیشتر = برچسب کلاس
ارزیابی نتایج (Precision/Recall)
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
11
مراحل مدل
این ویژگی ها نشانه هایی برای دسته بندی یک پیغام به اسپم و یا ایمیل معتبر است
ویژگی های یک ایمیل
کلمات (توکن ها)
free, win, online, weight, fortune, offer ،…
عبارات
“Free”, “only$”, “order now!”،…
کاراکترهای خاص
$pecial, grea8, 4u،…
سرآیند ایمیل (وابسته به دامنه)
نام فرستنده، آدرس ایمیل فرستنده و گیرنده، نام دامنه (مثل .edu، .ir، .com)، آدرس های IP
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
12
ویژگی(مشخصه) های یک پیام الکترونیکی
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
13
ماتریس بردار ویژگی ها (با مقادیر باینری)
ویژگی ها
کلمات و عبارات همان ویژگی ها هستند، اگر در آن سند/ایمیل موجود باشند ، مقدارشان برابر 1 بوده
و اگر در آن سند/ایمیل موجود نباشند مقدارشان برابر صفر خواهد بود
برای ما کلماتی ارزش دارد که بتوانیم با استفاده از آنها دسته ها (اسپم و ایمیل معتبر) را تشخیص دهیم
در جدول بالا ویژگی X2 خاصیت تمایز در تشخیص دسته ایجاد کرده است و وبنابراین یک ویژگی ایده آل است.
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
14
انتخاب ویژگی ها (Feature Selection)
ویژگی
ایمیل
تا حد زیادی کیفیت classification به انتخاب ویژگی ها وابسته است
الگوریتم های خوبی چون PIL و MST براساس MI ارائه شده است
انتخاب و یژگی ها با الگوریتم های ژنتیک و یا hill climbing
روش خی-2 و IG بهترین روشهایی هتند که کلمات پرمعنا را به ما می دهند.
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
15
انتخاب ویژگی ها (ادامه)
Naïve Bayesian
K- نزدیک ترین همسایه (k-NN)
SVM (Support Vector Machine)
توسط یک ابرصفحه کلاسها از هم جدا می شوند: برای وقتی که تنها دو کلاس داریم
فرکانس کلمه – فرکانس معکوس سند (TF-IDF)
Term Frequency- Inverse Document Frequency
درخت های تصمیم گیری
C4.5
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
16
برخی از الگوریتم های مبتنی بر یادگیری برای دسته بندی ایمیل ها
احتمال شرطی : P(B | A) = P(A|B) * P(B) / P(A)
X={x1, x2, x3, x4…xn} بردار ویژگی ها می باشد
مجموعه ویژگی ها: X={“online”, “credit”, “now!!!”…”Zinc”}
C={c1, c2, c3, c4…ck} مجموعه کلاسها
در اینجا دو کلاس داریم: C={“SPAM”, “LEGITIMATE”}.
ساده ترین روش برای محاسبه فرمول احتمال بیزین این است که فرض کنیم که هر ویژگی Xi بصورت شرطی مستقل از سایر ویژگی هاست
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
17
فیلتر کردن اسپم با استفاده از دسته بند Naïve Bayesian
فرض استقلال:
n= تعداد ویژگی ها
هر کلاس (اسپم و یا ایمیل معتبر) که این مقدار احتمالی به ازای آن بزرگتر باشد، برچسب آن ایمیل خواهد بود.
برای مقایسه مقدار کلاس اسپم با کلاس «ایمیل معتبر» نیازی به محاسبه مخرج کسر فوق نیست چراکه این مقدار برای هر کلاس یکسان است
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
18
فیلتر کردن اسپم با استفاده از دسته بند Naïve Bayesian(ادامه)
False Psitive شامل ایمیل هایی می شود که به اشتباه جزو اسپم ها دسته بندی می گردند. :
False Negative هم شامل ایمیل هایی می شود که به اشتباه جزو ایمیل های معتبر دسته بندی می شوند.:
!!! طبقه بندی اشتباه یک ایمیلِ معتبر به عنوان اسپم نسبت به طبقه بندی اشتباه یک اسپم به عنوان ایمیلِ درست، هزینه بدِ بیشتری در بردارد!
اگر هزینه λ بار بدتر از هزینه باشد، آنگاه زمانی یک ایمیل را جزو اسپم ها طبقه بندی می کنیم که
با فرض داریم که t برابر است با . در اینجا t برابر 0/999 گرفته شده است.
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
19
طبقه بندی به عنوان اسپم
از feature selection برای کاهش ابعاد ویژگی/داده استفاده شده است
بعضی اوقات می توان از feature transforming هم استفاده کرد
LSI & SVD
یک انبوه داده(corpus)از ایمیلهای واقعی : شامل 1578 ایمیل بیهوده و 211 ایمیل معتبر 1538 داده برای آموزش فیلتر و 251 عدد برای تست
ویژگیهای گرفته شده از توکن های متن
توکن های نادر (با رخداد کمتر از 3 در کل corpus) حذف شدند
35 ویژگی عبارتی اضافه شدند
20 ویژگی غیر متنی و وابسته به دامنه اضافه شدند
تعداد کاراکترهای غیر الفبایی در عنوان ایمیل به عنوان ویژگی مفیدی شناسایی شد
500 ویژگی برتر با استفاده از Mutual Information انتخاب شد
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
20
آزمایش
Spam Precision: درصدی از ایمیلهای طبقه بندی شده به عنوان اسپم که در واقع اسپم هستند.
Spam Recall: درصدی از کل ایمیل های اسپم واقعی که توسط دسته بند به عنوان اسپم طبقه بندی شده اند.
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
21
معیارهای ارزیابی
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
22
نتایج
یک نمودار Precision/Recall ایده آل
نمودار Recall / Precision برای اسپم ها با 3 مجموعه متفاوت از ویژگیها
نتایج دسته بندی (Classification) با استفاده از مجموعه ویژگی های متفاوت
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
23
نتایج (ادامه)
نقاط قوت
متد Bayesian کل پیغام را در نظر می گیرد. این متد علاوه بر اینکه کلمات کلیدی که معرف و مرتبط با اسپم هستند را شناسایی می کند، بلکه کلمات معرف ایمیل های معتبر را نیز شناسایی می کند. در متد Bayesian کلمات در کنارهم تاثیر یکدیگر را (در نتیجه نهایی فیلتر اسپم) متعادل می کنند؛ به بیانی دیگر فیلتر Bayesian بر روی کلمات کلیدی تکیه نمی کند به طوریکه به خاطر یک کلمه خاص، یک پیغام را جزو اسپم ها طبقه بندی کند، بلکه تمامی کلمات و تمامی ویژگی های پیغام را در نظر می گیرد.
یک فیلتر Bayesian با یادگیری مستمر از اسپم های جدید و ایمیل های معتبرِ جدید، به طور ثابت خود را با آخرین تغییرات وفق می دهد. فیلتر Bayesian دائماً در حال تحول است و خود را با تکنیک های جدید اسپم هماهنگ می سازد.
هنگامی که فرستادگان اسپم برای فریب دادن راهکارِ «بررسی کلمات کلیدی» به جای “Free” از “F-r-e-e” استفاده کردند، بلافاصله پس از افزودن “F-r-e-e” به پایگاه داده کلمات کلیدی، راهکارشان خنثی شد
روش Bayesian روشی است که قابل اِعمال به هر زبانی می باشد. فیلتر اسپم Bayesian کاملاً قابل انطباق با هر زبان و نوشتاری می باشد
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
24
نقاط قوت وضعف دسته بند Naïve Bayesian
تکنیک فیلتر Bayesian حساس به کاربر و داده های اوست. فیلتر از ایمیل های کاربر (و یا شرکت) یاد می گیرد که در مورد کاربر، بیشتر چه مطالبی به عنوان ایمیل رد و بدل می گردد.
به عنوان مثال اگر شرکت (یا فرد) یک شرکت دلال اتومبیل باشد، آنگاه کلمه “mortgage” به عنوان نشانه ای برای یک اسپم تلقی می گردد، در حالی که اگر شرکت (یا فرد) یک شرکتی باشد که طرف قراردادش سازمان وام دهنده مسکن باشند آنگاه چنین کلمه ای در ایمیل نشان دهنده وجود یک اسپم نمی باشد.
یک فیلتر Bayesian نسبت به فیلترهای مبتنی بر لیست کلمات کلیدی، کمتر فریب می خورد.
نقطه ضعف: فرض استقلال بین ویژگی ها
می توان از روشهای جایگزین (البته با محاسبات بیشتر) مانند Belief Network استفاده کرد
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
25
نقاط قوت وضعف(ادامه)
روش Bayesian برای فیلتر کردن اتوماتیک اسپم ها کارا می باشد
افزودن ویژگیهای غیردامنه ای و غیرمتنی و عبارتهای دست-ساخته باعث بهبود کارائی فیلترینگ می گردد.
فیلتراسپم Naïve Bayesian می تواند برای دسته بندی های متفاوتی از ایمیلها مورد استفاده قرار گیرد
مثل دسته بندی ایمیلهای معتبر به «ایمیلهای دوستان» و «ایمیلهای کاری»
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
26
جمع بندی
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
27
مراجع
[1] Sahami, M., Dumais, S., Heckerman,D and Horvitz,E. A bayesian approach to filtering junk e-mail. In Learning for Text Categorization: Papers from the 1998 Workshop.AAAI Technical Report WS-98-05, 1998.
[2] Blanzieri,E., Bryl,A. A survey of learning-based techniques of Email Spam Filtering. Technical report # DIT-06-056.University of Torino, Italy.2008.
[3] http://www.gfi.com/whitepapers/why-bayesian-filtering.pdf. “Why Bayesian filtering is the most effective anti-spam technology”, White Paper by GFI Software., 2008.
[4] Cohen, W., Learning rules that classify email. In Proceedings of the 1996 AAAI Spring Symposium on Machine Learning in Information Access, MLIA ’96. AAAI Press, 1996.
[5] Yang, Y., Pederson, J.O., A Coparative Study on feature selection in text categorization. In Proceedings of International Conference on Machine Learning (ICML), Pages 412-420. Morgan Kaufman Publishers, 1997
اسپم و فیلترکردن آن با استفاده از روش Naïve Bayesian
28
با تشکر از توجه شما