هرزنامه که معمولا تبلیغاتی هستند، ویژگی‌های مشابهی دارند. مثلا آنهایی که محصولی را تبلیغ می‌کنند از قیمت آن حرف می‌زنند و یا می‌گویند که فرصت‌تان چقدر استثنایی است. حتی رنگارنگ بودن بخش‌های نوشته می‌تواند نشان از بی‌ارزش بودن آن باشد. از آنجایی که این نشانه‌های قطعی نیستند و ما هم در ایمیل‌هایی که برای هم می‌فرستیم ممکن است مثلا از قیمت حرف بزنیم، نمی‌توانیم با چند قانون ساده هرزنامه‌ها را جدا کنیم. این‌جور مواقع سعی می‌کنیم از روی مجموعه هرزنامه‌های موجود یاد بگیریم که هرزنامه‌ها چه ویژگی‌هایی دارند.
حال اگر این هرزنامه‌ها در قالب متن‌های کوتاه پیامکی و یا شبکه‌های اجتماعی پیام‌رسان باشند، تشخیص آن‌ها سخت‌تر هم می‌شود.

۱. مقدمه

امروزه نامه رسانی الکترونیکی به عنوان هنجاری برای ارتباط کارا و پرسرعت معرفی شده است. کاربران پست الکترونیک در گلوگاه کارایی گرفتار شدهاند و در جنگی نابرابر به مقابله ی کسانی رفته اند که دیدگاه متفاوتی از نامهرسانی الکترونیکی دارند و آن را به صورت ارسال حجم بالای نامه با اهداف اقتصادی، مخرب و سودجویانه میبینند. این رایانامهها به اصطلاح هرزنامه (اسپم) نامیده شده اند.
نامه های الکترونیکی بیهوده که تحت نام هرزنامه نیز معروفند قسمتی از کار و زندگی کاربران اینترنت بخصوص پست الکترونیکی را به خود اختصاص داده است. با توجه به تغییرات اعمال شده در هرزنامه ها که از طرف ارسال کنندگان آنها جهت مخفیماندن از شناساییشدن توسط برنامه های ضد هرزنامه صورت میپذیرد، طراحی یک راه حل ضد هرزنامهای که بتواند بطور مناسب خود را با تغییرات اعمال شده روی هرزنامه ها وفق دهد، مشکل است.
در سالهای اخیر تحقیقات بسیاری برای رفع این مسئله انجام گرفته است ولی هنوز نامه های الکترونیکی ناخواسته یکی از مشکلات جدی کاربران است.

۲. کارهای مرتبط

برای تشخیص ایمل های عادی از هرزنامه ها روش های بسیاری ابداع شده اند که در زیر به اختصار برخی از آنها را توضیح میدهم

۲.۱. روش های رفتار محور

در این دسته از روش ها بر اساس رفتار های ارسال کننده یا در یافت کننده نامه، آنها در لیست هایی قرار میگیرند و بر اساس این لیست ها درباره نامه های آنها تصمیم گیری می شود.

۲.۱.۱. لیست سیاه (Black List)

فهرست سیاه یکی از اولین روشهای ضد هرزنامه است. در این روش از یک فهرست که در آن دامنه ها، IP ها و نشانی های فرستنده های هرزنامه قرار دارد در سرور های انتقال رایانامه نگهداری می شود. به اینترتیب هرگاه دامنه یا آدرس IP فرستنده یک هرزنامه در لیست سیاه قرار داشته باشد، آن نامه به عنوان هرزنامه تلقی میشود. البته این روش کارایی بالایی ندارد، زیرا هرزنامه نویس ها از یک آدرس یا دامنه ثابت استفاده نمیکنند. [1]
از معایب این روش بالابودن نرخ منفی کاذب است.

۲.۱.۲. لیست سفید (White List)

این روش دقیقا برعکس روش قبل است، در این روش فهرستی از دامنه ها، IP ها و نشانی های فرستنده های نامه های پاک تهیه شده و هر نامه ای که از طرف آنها نباشد به عنوان هرزنامه تلقی میشود.
از معایب این روش بالابودن نرخ مثبت کاذب است. همچنین اگر هرزنامه نویس به اطلاعات فهرست سفید دسترسی پیدا کند،آن وقت این روش کاملاً ناکارا خواهد بود.[2]

۲.۱.۳. لیست خاکستری (Gray List)

ارسال کنندگان هرزنامه تلاش می کنند تا کمترین هزینه را برای ارسال هر نامه صرف کنند همچنین ارسال شدن همه نامه ها برایشان مهم نیست، از این رو اگر در ارسال نامه خطایی رخ بدهد، بجای این که آن را در صف ارسال مجدد قرار بدهند و پس از مدتی برای این کار تلاش کنند، از خطا صرف نظر کرده و نامه هایی که ارسال نشده اند را دور می اندازند
به این ترتیب اگر سرور دریافت کننده نامه به فرستنده اعلام کند که در حال حاظر امکان دریافت نامه را ندارد و سرور فرستنده باید بعدا مجددا تلاش کند ولی سرور فرستنده این کار را انجام ندهد، این احتمال وجود دارد که نامه از طرف یک هرزنامه نویس بوده است.
لذا این فهرست حاوی فرستندگانی است که پس از اعلام خطا، اقدام مجدد به منظور فرستادن آن انجام نداده اند و نامه هایی که برای ارسال مجدد آنها تلاش نشده است به عنوان هرزنامه تلقی میشوند[2].
از معایت این روش آن است که هر نامه پاک دوبار ارسال میشود و همچنین هرزنامه نویس ها میتوانند از اعمال سیاست عدم ارسال مجدد دست بردارند.

۲.۲. روش های هوشمند

در این روش ها از الگوریتم های هوش مصنوعی برای تشخصی هرزنامه بودن یک نامه استفاده میشود

۲.۲.۱. مبتنی بر قضیه Bayes

برای درک بهتر این روش باید مروری بر قضیه بیز در احتمالات داشت

P\left( { A }|{ B } \right) = \frac { P\left( { B }|{ A } \right) P\left( A \right) }{ P\left( A \right) }

این قضیه رابطه ای برای محاسبه احتمال وقوع A به شرط B از روی احتمال های وقوع A، B و B به شرط A بیان میکند
حال در مسئله تشخیص هرزنامه
اگر A را احتمال هرزنامه بودن یک ایمیل و B را محتوای ایمیل تعریف کنیم میتوانیم هرزنامه ها را بصورت زیر مشخص کرد:

P\left( { A }|{ B } \right) > P\left( { \overline { A } }|{ B } \right)

حال با استفاده از قضیه بیز میتوان آن را بصورت زیر نوشت:

P\left( A \right) P\left( { B }|{ A } \right) >P\left( { \overline { A } } \right) P\left( { { B }|\overline { A } } \right)

که به این معنی است که :
اگر احتمال این که این محتوا در یک هرزنامه وجود داشته باشد و این نامه هرزنامه باشد از احتمال این که این محتوا در یک نامه پاک وجود داشته باشد و این نامه پاک باشد بیشتر بشود، این نامه هرزنامه است.[3]

۲.۲.۲. براساس شبکه عصبی

شبکه های عصبی در کل مجموعه ای از چندین “تابع ساده ریاضی” هستند که در نهایت تابعی پیچیده را تشکیل می دهند. خروجی هر کدام از این توابع می تواند ورودی تابعی دیگر باشد. در نهایت با استفاده از خروجی ها باید بتوان دسته بندی نمونه را مشخص نمود.
خود شبکه های عصبی به دو دسته تقسیم می شوند. روشی که بیشتر در تشخیص هرزنامه به کار می رود روش Perceptron است.
در این روش هر تابع ساده ما به شکل یک ترکیب خطی از ورودی هاست. خروجی عددی حقیقی است. قرار داد می شود که خروجی مثبت به معنی عادی بودن ایمیل و اعداد منفی بیانگر اسپم بودن آن می باشند. ضرایب این ترکیب خطی در ابتدا مقادیری دلخواه تعیین می شوند. حال باید یکی از نمونه هایی به تابع داده شود که حدس تابع در مورد هزنامه بودن یا نبودن آن اشتباه است. در این صورت تمام ضرایب ترکیب خطی یاد شده بر پایه این ورودی و با استفاده از رابطه ای مشخص اصلاح می گردند. این عمل چندین بار تکرار می شود. وضعیتی حاصل شد که تمام نمونه ها درست دسته بندی شده بودند، کار متوقف می گردد.[4]
در صورتی که رابطه بین ورودی های مسئله خطی نباشد، ضرایب واگرا خواهند شد و الگوریتم به نتیجه نمی رسد.شبکه های عصبی نیاز به زمان و نمونه های زیاد برای تکمیل فرآیند یادگیری دارند. همچنین لزومی ندارد که رابطه بین ورودی ها واقعا خطی باشد و ممکن است روش کلا به نتیجه نرسد. در عوض پیاده سازی آن ها کار مشکلی نیست و نتیجه ی حاصله در صورت وجود عموما خوب و مطلوب است.

۲.۲.۳. بر اساس SVM

ماشین بردار پشتیبانی (Support Vector Machine) خود نوعی از شبکه های عصبی است.
در این روش تابعی خطی پیدا می شود که با گرفتن ورودی ها، هرزنامه بودن را مشخص کند. تفاوت اینجاست که در این روش تابع خطی را به یک معادله تبدیل شده و با استفاده از آن تلاش می شود “خط مرز” بین نمونه های عادی و اسپم یافت شود. در این صورت برای تشخیص وضعیت هر ایمیل جدید، کافیست بررسی شود که این ایمیل کدام طرف خط مذکور است (با توجه به n بعدی بودن فضا، خط یاد شده در اصل خود یک فضای n-1 بعدی با معادله ی مشخصه ی خاص خود است).[5]
پیاده سازی این روش اندکی مشکل است اما حاصل عموما بهتر از روش بالا می باشد.

۲.۲.۴. با استفاده از الگوریتم K-NN

الگوریتم K Nearest Neighbor یا به اختصار KNN یک گروه شامل K رکورد از مجموعه رکورد‌های آموزشی که نزدیک‌ترین رکورد‌ها به رکورد آزمایشی باشند را انتخاب کرده و بر اساس برتری رده یا برچسب مربوط به آن‌ها در مورد دسته رکورد آزمایشی مزبور تصمیم‌گیری می‌نماید. به عبارت ساده‌تر این روش رده‌ای را انتخاب می‎‌کند که در همسایگی انتخاب شده بیشترین تعداد رکورد منتسب به آن دسته باشند. بنابراین رده‌ای که از همه رده‌ها بیشتر در بین K نزدیک‌ترین همسایه مشاهده شود، به عنوان رده رکورد جدید در نظر گرفته می‌شود.[6]

۳. آزمایش‌ها

۳.۱. مجموعه داده (Data Set)

در این پروژه از مجموعه داده هرزنامه پیامکی که توسط دانشگاه کالیفرنیا در ارواین ارائه شده استفاده شد.
این دیتاست شامل ۵۵۷۴ پیام است که کوتاه ترین آنها ۲ کاراکتر و طولانی ترینشان ۹۱۰ کاراکتر طول دارد. پراکندگی طول پیام ها در تصویر زیر مشخص است:

همچنین در این دیتاست ۴۸۷۲ نامه پاک وجود دارد که شامل ۴۵۱۸ پیام متحصر به فرد است و طولانی ترین آنها ۹۱۰ و کوتاه ترین آنها ۲ کاراکتر طول دارند.
از میان ۷۴۷ هرزنامه، ۶۵۳ پیام یکتا وجود دارد و بیشترین طول آنها ۲۲۳ و کمترین آنها ۱۳ کاراکتر است، پراکندگی طول پیام ها برحسب نوع نامه در تصویر زیر قابل مشاهده است:

۳.۲. پیاده‌سازی

کد پیاده‌سازی در GitHub قابل مشاهده است.
در این مرحله، با کمک کتابخانه scikit learn مدل های تشخیص هرزنامه را توسط سه الگوریتم Naive Bayes و SVM و KNN پیاده کردم
فرایند کلی آموزش دادن الگوریتم ها به این صورت است:
ابتدا مجموعه داده را به ۲ بخش با نسبت ۱ به ۴ تقسیم می‌شود، از بخش بزرگ تر برای یاد دادن به ماشین و از بخش کوچک تر برای تست کردن آن استفاده می‌شود.
سپس باید داده ها را برای کامپیوتر قابل فهم کرد، به این منظور با استفاده از الگوریتم TF-IDF هر جمله را به برداری از اعداد تبدیل می کنیم

۳.۲.۱. مدل BOW

نام این مدل خلاصه عبارت Bag Of Word است و یک روش ساده سازی نمایش اطلاعات متن است و هدف آن تبدیل متن به یک آرایه (وکتور) از اعداد است.
در این روش تعداد تکرار هر موجودیت در متن به جای خود آن موجودیت در آرایه ذخیره میشود. موجودیت های ما میتوانند کلمات، عبارات یا حتی کاراکتر ها و ... باشند.[7]

۳.۲.۲. الگوریتم TF-IDF

نام این الگوریتم که خلاصه عبارت Term Frequency–Inverse Document Frequency است
در این شیوه به لغات یک وزن بر اساس فراوانی آن در متن داده می‌شود. در واقع این سیستم وزن دهی نشان می‌دهد چقدر یک کلمه برای یک متن مهم است. وزن کلمه با افزایش تعداد تکرار آن در متن افزایش می‌یابد، اما توسط تعداد کلمات در متن کنترل می‌شود، چرا که می‌دانیم در صورت زیاد بودن طول متن، بعضی از کلمات (مثلا حروف اضافه یا ضمیر ها) به طول طبیعی بیشتر از دیگران تکرار خواهند شد، اگرچه چندان اهمیتی در معنی ندارند.
به منظور استفاده از این الگوریتم ما مراحل زیر را انحام میدهیم:[8]

تعداد تکرار هر کلمه را در هر پیام می شماریم. (TF) که این مورد در مسئله ما با روش BOW انجام می شود.
عدد بدست آمده را بر تعداد کل تکرار های آن کلمه در دیتاست تقسیم می کنیم. (IDF)

سپس با استفاده از Grid Search Cross Validation که در کتابخانه scikit learn وجود دارد بهترین گزینش پارامتر های الگوریتم پیدا میشوند

۳.۲.۳. خروجی اولیه الگوریتم ها

قبل از بیان خروجی های ابتدا چند تعریف را ارائه می کنم:[9]

Precision : دقت سیستم در میان دادهای پیش بینی شده
Recall : نسبت تعداد داده های پیش بینی شده، به تعداد کل داده های مورد انتظار برای پیش بینی
f1-score : [10]
F1=2 \times \frac { precision \times recall }{ precision + recall }

Naive Bayes

پس از اجرا این الگوریتم خروجی های زیر بدست آمد:

	precision	recall	f1-score	support
ham	0.97	1.00	0.98	4827
spam	1.00	0.77	0.87	747
avg / total	0.97	0.97	0.97	5574

همان طور که در تصویر زیر قابل مشاهده است الگوریتم ۲۳٪ (۱۷۰ نامه) از مواردی که هرزنامه بوده اند را به عنوان نامه پاک شناسایی کرده همچنین هیچ از نامه های پاک را به عنوان هرزنامه تشخیص نداده است.

Support Vector Machine

پس از اجرا این الگوریتم خروجی های زیر بدست آمد:

	precision	recall	f1-score	support
ham	0.87	1.00	0.93	4827
spam	0.00	0.00	0.00	747
avg / total	0.75	0.87	0.80	5574

همان طور که مشاهده می کنید، این اگوریتم بدون بهینه سازی قادر به تشخیص هرزنامه ها نیست

K Nearest Neighbor

پس از اجرا این الگوریتم خروجی های زیر بدست آمد:

	precision	recall	f1-score	support
ham	0.87	1.00	0.93	4827
spam	0.00	0.00	0.00	747
avg / total	0.75	0.87	0.80	5574

همان طور که مشاهده می کنید، این اگوریتم بدون بهینه سازی قادر به تشخیص هرزنامه ها نیست

۳.۲.۴. خروجی الگوریتم های بهبود یافته

Naive Bayes

با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافته و نتایج تغییر کرد:

params = {
    'tfidf__use_idf': (True, False),
    'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word')
}

	precision	recall	f1-score	support
ham	0.97	1.00	0.99	4827
spam	1.00	0.81	0.89	747
avg / total	0.98	0.97	0.97	5574

همان طور که مشاهده می‌کنید، پس از بهینه سازی این الگوریتم،۴٪ از False Positive های این الگوریتم کاهش پیدا کرد و تعداد آخطا ها به ۱۴۲ نامه رسید

درصد تشخیص الگوریتم بیزین پس از بهینه سازی

Support Vector Machine

با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافت:

params = {
        'tfidf__use_idf': (True, False),
        'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word', 'char'),
        'classifier__n_neighbors': numpy.arange(start=1, stop=100),
        'classifier__weights': ['uniform', 'distance']
    }

با اعمال این پارمتر ها سخت گیری الگوریتم بشدت زیاد شد و منجر به ایجاد ۲ مورد False Negative شد ولی تنها در تشخیص ۱۰مورد از هرزنامه ها شکست خورد:

درصد تشخیص الگوریتم SVM پس از بهینه سازی

	precision	recall	f1-score	support
ham	1.00	1.00	1.00	4827
spam	1.00	0.99	0.99	747
avg / total	1.00	1.00	1.00	5574

K Nearest Neighbor

با تعیین پارامتر های زیر برای Grid Search، خروجی الگوریتم بهبود یافت:

 params = {
        'tfidf__use_idf': (True, False),
        'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word', 'char'),
        'classifier__n_neighbors': numpy.arange(start=1, stop=100),
        'classifier__weights': ['uniform', 'distance']
    }

با اعمال این پارامتر ها دقت الگوریتم بطور چشم گیری افزایش پیدا می کند، شایان ذکر است ای با این پارامتر ها ۷ مورد False Negative و ۲۶ مورد False Positive ایجاد شده است

	precision	recall	f1-score	support
ham	0.99	1.00	1.00	4827
spam	0.99	0.97	0.98	747
avg / total	0.99	0.99	0.99	5574

درصد تشخیص الگوریتم KNN پس از بهینه سازی

۳.۳. تحلیل اولیه

در خروجی این الگوریتم ها نکته قابل توجهی وجود دارد، با این که الگوریتم های SVM و KNN درصد خطا نسبتا پایینی دارند، اما هر ۳ الگوریتم در تشخیص جملات زیر دچار خطا شدند:

برچسب درست	متن پیام
spam	Monthly password for wap. mobsi.com is 391784. Use your wap phone not PC
spam	Guess who am I?This is the first time I created a web page WWW.ASJESUS.COM read all I wrote. I'm waiting for your opinions. I want to be your friend 1/1
spam	Hello darling how are you today? I would love to have a chat, why dont you tel...

۳.۴. بهبود نتایج

برای حل مشکل با تغییر پارامتر های الگوریتم ها، به نتیجه جالبی دست پیدا کردم.
اگر آنالازیر char را از فهرست آنالیزر های bow الگوریتم KNN حذف کنم دقت آن کمی کاهش پیدا می‌کند ولی وقتی در کنار الگوریتم های دیگر قرار بگیرد منجر به کاهش خطا کل سیستم می‌شود.
در این حالت تنها ۱ عبارت توسط هیچ الگوریتمی به درستی برچسب نخورد:

برچسب درست	متن پیام
spam	Hi its LUCY Hubby at meetins all day Fri & I will B alone at hotel U fancy cumin over? Pls leave msg 2day 09099726395 Lucy x Calls£1/minMobsmoreLKPOBOX177HP51FL

K Nearest Neighbor

با حدف آنالازیر char پارامتر های آن به صورت زیر ٔر آمد:

 params = {
        'tfidf__use_idf': (True, False),
        'bow__analyzer': (splitToLemmas_NoStopWord, splitToLemmas, splitToTokens, 'word'),
        'classifier__n_neighbors': numpy.arange(start=1, stop=100),
        'classifier__weights': ['uniform', 'distance']
    }

با اعمال این پارامتر ها ۱ مورد False Negative و ۳۱ مورد False Positive وجود دارد

	precision	recall	f1-score	support
ham	0.99	1.00	1.00	4827
spam	1.00	0.96	0.98	747
avg / total	0.99	0.99	0.99	5574

۴. کارهای آینده

الگوریتم های بسیاری مانند شبکه عصبی و ... جود دارند که میتوان از آنها برای تشخیص هرزنامه استفاده کرد.
همچنین پارمتر های الگوریتم های استفاده شده در این مقاله بسیار متنوع تر از آنچه بررسی شده‌اند است و می‌توان روی بررسی و انتخاب دقیق آن ها تمرکز کرد.
همچنین می‌توان روی بهبود توابع مورد استفاده در مدل BOW کار کرد و یا از مدل های دیگری استفاده کرد

۵. مراجع

[1] Oro, David, et al. "Benchmarking IP blacklists for financial botnet detection." Information Assurance and Security (IAS), 2010 Sixth International Conference on. IEEE, 2010.
[2] Chiou, Pin-Ren, Po-Ching Lin, and Chun-Ta Li. "Blocking spam sessions with greylisting and block listing based on client behavior." Advanced Communication Technology (ICACT), 2013 15th International Conference on. IEEE, 2013
[3] Sahami, Mehran, et al. "A Bayesian approach to filtering junk e-mail." Learning for Text Categorization: Papers from the 1998 workshop. Vol. 62. 1998.
[4] Kufandirimbwa, Owen, and Richard Gotora. "Spam Detection using Artificial Neural Networks (Perceptron Learning Rule)." Online Journal of Physical and Environmental Science Research 1.2 (2012): 22-29.
[5] Support Vector Machine
[6] K Nearest Neighbor Classifier
[7] Bag Of Words model
[8] TF-IDF
[9] Precision & Recall
[10] F1-score
[7] Metsis, Vangelis, Ion Androutsopoulos, and Georgios Paliouras. "Spam filtering with naive bayes-which naive bayes?." CEAS. Vol. 17. 2006.

۶. پیوندهای مفید

تایید شده

با عرض سلام و خسته نباشید. به نظر من در این فاز در کل خوب عمل کردید و با یک تغییر ساده نتایج را بهبود دادید که خوب است، شاید اگر وقت داشتید می شد روش های دیگری را هم امتحان کنید و نمونه های خروجی درست و غلط را برای مخاطب قرار دهید. کارهای آینده هم کوتاه بود ولی محتوای مناسبی داشت موفق باشید.

سلام توضیحات کامل و خوب بود. اگر الگوریتم‌ها کامل تر توضیح داده می‌شد و نقاط قوت و ضعف هرکدام بیان می‌شد بهتر بود.

سلام ، خسته نباشید توضیحاتتون خیلی خوب بود فقط به نظر من اگر الگوریتم‌ها را یکم بیشتر توضیح می‌دادید بهتر هم می‌شد.
با تشکر

سلام خسته نباشید،
اگر مقدمه کمی بیشتر بود بهتر بود ولی در کل همه ی قسمت ها خیلی خوب بود مخصوصا قسمت شرح کار های مرتبط که کامل و قابل فهم بود و نمودار ها نیز به خوبی مقایسه ها را نشان می دهند.

از نظر نگارشی بسیار با سلیقه انجام شده و گزارش بسیار زیبا در آب در امده.
از نظر محتوا شرح مساله رو به خوبی انجام دادین و همین روند رو کار‌های مرتبط و داده ادامه دادین که بسیار جامع و گویا بود.
در قسمت نتایج بهتر بود کمی بیشتر معیار ارزیابی‌تان را توضیح می‌دادین و ضمن اینکه برای بهبود برنامه می‌توانستین روش‌های بیشتری را امتحان کنید.