فیلترینگ اسپم بیزی

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

جیسون رِنی اولین برنامه کامپیوتری|برنامه فیلترینگ ایمیل به نام iFile را که از روش طبقه بندی بیز استفاده می‌کرد را در سال ۱۹۹۶ نوشت. این برنامه با قرار دادن ایمیل‌ها در پوشه‌ها، آن‌ها را مرتب می‌کرد. اولین مقاله پژوهشی درباره فیلترینگ اسپم بیزی توسط سهامی (و دیگران) در سال ۱۹۹۸ انتشار یافت. روش‌های گوناگونی در این زمینه به صورت تحقیقاتی و همچنین نرم‌افزارهای تجاری پیاده سازی شده‌است. در سال ۲۰۰۲ میلادی، اصول فیلترینگ بیزی در مقاله‌ای که توسط پال گراهام نوشته شد، شرح داده شد و برای عموم قرار گرفت.

فیلترینگ اسپم بیزی به یک سازوکار معروف برای تشخیص ایمیل‌های اسپم در میان ایمیل‌های غیر اسپم (گاهی به این ایمیل‌ها ham یا bacn نیز می‌گویند) تبدیل شد. تعداد زیادی از سرویس گیرنده‌های ایمیل، فیلترینگ اسپم بیزی را پیاده سازی کرده‌اند. همچنین کاربرها می‌توانند به صورت جداگانه برنامه‌های فیلترینگ ایمیل را نصب کنند. از فیلترهای ایمیل طرف سرویس دهنده می‌توان DSPAM، SpamAssassin، SpamBayes، Bogofilter و ASSP را که از روش فیلترینگ اسپم بیزی استفاده می‌کنند را نام برد.

فرآیند

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

بعد ازیادگیری، احتمال کلمه‌های ایمیل (به وسیلهٔ توابع احتمال) برای مشخص کردن این که ایمیل در چه دسته‌ای قرار می‌گیرد استفاده می‌شود. هر کلمه در ایمیل به احتمال اسپم بودن ایمیل کمک می‌کند، بنابراین کلمات پر تکرار در ایمیل‌ها نقش مهمی در تشخیص اسپم بودن ایمیل دارند. به این کمک کردن احتمال posterior گویند که براساس قضیه بیز محاسبه می‌گردد. سپس برای تمام کلمات احتمال اسپم بودن ایمیل محاسبه می‌گردد و اگر کل احتمالات از مقدار آستانه (۹۵٪) بیشتر شد، فیلتر برچسب اسپم بودن به آن ایمیل می‌زند.

به مانند روش‌های دیگر فیلترینگ اسپم ایمیل با برچسب اسپم به صورت خودکار به پوشه "Junk" منتقل می‌شود و حتی بعد از مدتی پاک خواهد شد. برخی از نرم‌افزارها برای مدتی خاص ایمیل را در قرنطینه برای بازبینی به وسیله کاربر قرار می‌دهند.

یادگیری اولیه معمولاً دارای خطاهای بالایی است (مثبت کاذب و منفی کاذب) که کاربر ابتدا باید آن را برای نرم‌افزار تمیزسازی کند. بعد از مدتی نرم‌افزار به صورت پویا خودش را وفق می‌دهد و اسپم‌ها را با دقت بالایی تشخیص می‌دهد.

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

پایه ریاضی

فیلترهای ایمیل بیزی از مزایای قضیه بیز استفاده می‌کنند. قضیه بیز در چندین قسمت استفاده می‌شود:

• نخستین مرتبه، محاسبهٔ احتمال کلمه‌های موجود در پیام دریافت شده
• دومین مرتبه، محاسبهٔ احتمال اسپم بودن پیام براساس احتمال‌های بدست آمده از کلمه‌های پیام دریافتی
• سومین مرتبه، چگونگی برخورد با کلمه‌های کمیاب

محاسبه احتمال این که یک پیام شامل کلمات اسپم باشد

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

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

$\Pr(S|W) = \frac{\Pr(W|S) \cdot \Pr(S)}{\Pr(W|S) \cdot \Pr(S) + \Pr(W|H) \cdot \Pr(H)}$

و داریم:

• $Pr(S|W)\$: احتمال این که پیام اسپم و کلمه "Replica" در آن باشد
• $Pr(S)\$: احتمال اسپم بودن پیام‌ها
• $Pr(W|S)\$: احتمال این که کلمه "Replica" در پیام‌های اسپم ظاهر شود
• $Pr(H)\$: احتمال اسپم نبودن پیام‌ها (ham باشند)
• $P(W|H)\$: احتمال این که کلمه "Replica" در پیام‌های غیر اسپم (ham) ظاهر شود

احتمال اسپم بودن

آمار اخیر نشان می‌دهد که احتمال اسپم بودن پیامی که دریافت می‌کنید حداقل ۸۰ درصد است:

$\Pr(S) = 0.8 ; \Pr(H) = 0.2$

گرچه اکثر نرم‌افزارهای تشخیص اسپم بیزی فرض می‌کنند هیچ دلیلی وجود ندارد که احتمال اسپم بودن پیام‌های دریافتی بیشتر از اسپم نبودن آن‌ها باشد و آن‌ها احتمال این دو را برابر در نظر می‌گیرند.

$\Pr(S) = 0.5 ; \Pr(H) = 0.5$

فیلترهایی که از این فرضیه استفاده می‌کنند گفته می‌شود که بیز نیست، یعنی آن‌ها هیچ تبعیضی بین ایمیل‌های دریافتی نمی‌گذارند. این فرضیه فرمول را ساده تر می‌کند:

$\Pr(S|W) = \frac{\Pr(W|S)}{\Pr(W|S) + \Pr(W|H)}$

این کمیت به نام میزان اسپمگی (spamicity یا spaminess) شناخته می‌شود و می‌توانیم برای کلمه "Replica" آن را محاسبه کنیم. عدد $Pr(W|S)\$ در این فرمول تعداد تکرار کلمه "Replica" در پیام‌های اسپم در مرحله یادگیری است. به طور مشابه عدد $Pr(W|H)\$ تعداد تکرار کلمه "Replica" در پیام‌های غیر اسپم (ham) در مرحله یادگیری است. برای بدست آوردن تقریبی خوب، باید در مرحله یادگیری تعداد پیام‌های اسپم و غیر اسپم به طور قابل توجهی زیاد باشد. همچنین با توجه به تغییر فرمول بیز، باید در مرحله یادگیری تعداد پیام‌های اسپم و غیر اسپم نیز با هم برابر باشند. تشخیص این که پیام اسپم است یا نه با در نظر گرفتن یک کلمه "Replica" کاری بسیار اشتباه است، به همین دلیل است که نرم‌افزارهای فیلترینگ اسپم بیز سعی می‌کنند که براساس چندین کلمه اسپم بودن یا نبودن را تشخیص دهند.

ترکیب احتمال‌های مستقل بدست آمده از کلمه‌های یک پیام

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

$p = \frac{p1 \cdot p2 \cdot \ldots \cdot pN}{p1 \cdot p2 \cdot \ldots \cdot pN + (1 - p1) \cdot (1 - p2) \cdot \ldots \cdot (1 - pN)}$

و داریم:

• $p$ احتمال این که پیام دریافتی اسپم باشد
• $p1$ احتمال این که کلمه اول در پیام دریافتی اسپم باشد. $p(S|W1)\$ (به عنوان مثال کلمه "Replica")
• $p2$ احتمال این که کلمه دوم در پیام دریافتی اسپم باشد. $p(S|W2)\$ (به عنوان مثال کلمه "Watches")
• و الی کلمه N -۱
• $pN$ احتمال این که کلمه Nاُم در پیام دریافتی اسپم باشد. $p(S|WN)\$ (به عنوان مثال کلمه "home")

با فرضیات بالا، نرم‌افزاری که به این طریق نوشته شود naive Bayes classifier نامند. برای تشخیص اسپم بودن پیام، نتیجه $p$ با مقدار آستانه مقایسه می‌شود. اگر مقدار $p$ کمتر از مقدار آستانه بود، پیام اسپم نیست (که به آن ham گفته می‌شود) در غیر این صورت پیام اسپم است.

چگونگی رفتار با کلمات کمیاب

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

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

با در نطر گرفتن قضیه بیز، متغیر تصادفی با توزیع بتا، دو دسته ایمیل‌های غیر اسپم (ham) و اسپم برای یک کلمه (مثل "Replica") است. تعدادی از نرم‌افزارها از احتمال صحیح قضیه بیز استفاده می‌کنند:

$Pr'(S|W) = \frac{s \cdot Pr(S) + n \cdot Pr(S|W)}{s + n }$

و داریم:

• $Pr'(S|W)\$ احتمال صحیح این که کلمه داده شده در پیام‌های اسپم ظاهر شود
• $s\$ یک ضریب، که ما براساس پیش زمینه‌ای که در دریافت پیام‌های اسپم داریم، مشخص می‌شود
• $Pr(S)\$ احتمال این که تمام پیام‌های دریافتی اسپم باشند
• $n\$ تعداد تکرار کلمه در مرحله یادگیری
• $Pr(S|W)\$ مقدار اسپمگی (spamicity) این کلمه

این احتمال صحیح به جای مقدار اسپمگی (spamicity) در فرمول ترکیب احتمال‌های مستقل استفاده می‌شود.

مجددا برای جلوگیری از مشکوک بودن بیش از اندازه به ایمیل‌های دریافتی $Pr(S)\$ می‌تواند برابر ۰.۵ در نظر گرفته شود. عدد $3$ مقدار خوبی برای $s$ می‌باشد، که نشان دهنده این است که حداقل ۳ پیام در مرحله یادگیری شامل کلمه جاری است. این برای افزایش اطمینان نرم‌افزار است.

این فرمول می‌تواند گسترش پیدا کند و $n$ برابر با صفر در نظر گرفته شود (یعنی اسپمگی (spamicity) تعریف نشده‌است)، بنابراین فرمول به صورت $Pr(S)\$ می‌شود.

راه‌های اکتشافی دیگر

کلمات بی طرف مانند "the"، "a"، "some" یا "is" در زبان انگلیسی یا مشابه این کلمات در زبان‌های دیگر را می‌توان نادیده گرفت. در حالت کلی، برخی از فیلترهای فیلترینگ بیزی تمام کلماتی که مقدار اسپمگی آن‌ها نزدیک به ۰٫۵ باشند را نادیده می‌گیرند که این تصمیم خوبی است. در این الگوریتم کلماتی که اسپمگی آن‌ها در اطراف ۰٫۰ (که مشخص کننده پیام‌های درست و غیر اسپم هستند) یا ۱٫۰ (که مشخص کننده پیام‌های درست و اسپم هستند) باشند، در نظر گرفته می‌شوند. به عنوان مثال یک روش می‌تواند ۱۰ کلمه‌ای را نگه دارد که قدر مطلق $| 0.5 - pI |$ از همه بیشتر باشد.

برخی از نرم‌افزارها کلماتی را نگه می‌دارند که چندین دفعه در مرحله یادگیری در پیام‌های مختلف ظاهر شده باشند.

برخی دیگر از نرم‌افزارها از الگوها (دنباله‌ای از کلمات) به جای کلمات زبان طبیعی استفاده می‌کنند. برای مثال، با یک پنجره لغزان چهار کلمه‌ای، این نرم‌افزارها اسپمگی را برای «Viagra is good for» به جای کلمات "Viagra" ،"is" ،"good" و "for" محاسبه می‌کنند. این روش حساسیت به متن را افزایش می‌دهد و اختلال بیزی را برای پایگاه داده‌های بزرگ کمتر می‌کند.

روش‌های ترکیبی

به دلیل بالا بودن خطاها در ابتدای استفاده از روش بیزی برای فیلترینگ اسپم، راه‌هایی برای ترکیب احتمال‌ها وجود دارد. این روش‌ها با فرضیاتی که از آمار و اطلاعات ورودی محاسبه می‌شود فرق دارد. این فرضیات به طور اساسی با فرمول‌هایی که با ترکیب احتمال‌ها بدست آوردیم فرق دارند. برای مثال با فرض احتمال‌های مستقل و با استفاده از توزیع کی دو با درجهٔ آزادی $2 \cdot N$ می‌توان فرمول زیر را داشت:

$p = C^{-1}(-2 \cdot \ln(p1 \cdot p2 \cdot \ldots \cdot pN), 2 \cdot N)$

وقتی که $C^{-1}$ تابع توزیع معکوس کی دو باشد. احتمال‌های مستقل می‌توانند با روش فرق گذاری مارکوین نیز ترکیب شوند.

بحث

مزیت‌ها

مزیت فیلترینگ اسپم بیزی، یادگیری برای هر کاربر می‌باشد.

اسپم‌هایی که یک کاربر دریافت می‌کند معمولاً براساس فعالیت‌های کاربر در اینترنت می‌باشد. برای مثال، یک کاربر در یک خبرنامه ثبت نام می‌کند و کاربر ایمیل‌های آن خبرنامه را به عنوان اسپم می‌شناسد. این خبرنامه اینترنتی معمولاً دارای کلمات مشترک است، که می‌تواند اسم خبرنامه یا آدرس ایمیل خبرنامه باشد. یک فیلتر اسپم بیزی در نهایت یک احتمال بالایی براساس الگوهای خاص کاربر در نظر می‌گیرد.

رفتار متفاوتی با ایمیل‌های غیر اسپم و قانونی ای که کاربر دریافت می‌کند خواهد داشت. برای مثال در یک شرکت، گاهی اسم شرکت، نام کارمندان و یا نام مشتری‌ها در پیام‌ها ذکر می‌شود. فیلتر یک احتمال پایینی برای این دسته از اسامی تعیین می‌کند.

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

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

اشکال‌ها

فیلترینگ اسپم بیزی مستعد زهر بیزی است، روشی که اسپمرها برای کاهش کارایی فیلترینگ‌های اسپمی که، وابسته به فیلترینگ بیزی است، به کار می‌برند. فرستادن ایمیل‌های انبوه قانونی که معمولاً متن آن از روزنامه‌ها و منابع ادبی جمع آوری می‌شود یک نمونه زهر بیزی است که اسپمرها انجام می‌دهند. تاکتیک‌های اسپمرها شامل، قرار دادن کلمات تصادفی بی ضرر که معمولاً ربطی به اسپم ندارد، نیز می‌باشد که بدین وسیله امتیاز اسپم‌ها را نزد فیلترینگ‌های بیزی کاهش می‌دهند تا از فیلترینگ‌های اسپم بیزی فرار کنند.

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

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

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

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

منابع

Wikipedia contributors, "Bayesian spam filtering," Wikipedia, The Free Encyclopedia, (accessed November 17, 2009).

پیوند به بیرون

• Guide to Bayesian spam filters: part 1, part 2.
• Detailed explanation of Paul Graham's formulas by Tim Peters
• Gary Robinson's spam blog