طبقه‌بندی خطی

در زمینه یادگیری ماشینی، هدف دسته‌بندی آماری استفاده از ویژگی‌های یک شی برای شناسایی رده (یا گروه) آن است. یک دسته‌بندی‌کننده خطی یا طبقه‌بندی‌کننده خطی (به انگلیسی: Linear classification) با اتخاذ یک تصمیم طبقه‌بندی بر اساس مقدار ترکیب خطی ویژگی‌ها به این هدف دست می‌یابد. ویژگی‌های یک شی نیز به عنوان مقادیر ویژگی شناخته می‌شوند و معمولاً در یک بردار به نام بردار ویژگی به ماشین ارائه می‌شوند. چنین طبقه‌بندی‌کننده‌هایی برای مسائل کاربردی مانند طبقه‌بندی اسناد، و به‌طور کلی برای مسائلی با تعداد زیادی از متغیرها (ویژگی‌ها) به خوبی کار می‌کنند. در مقایسه با دسته‌بندی کننده‌های غیرخطی، این دسته‌بندی کننده‌ها با صرف زمان کمتری برای آموزش و صرف زمان کمتر در پیش‌بینی، عملکرد مشابهی دارند.

تعریف

در این حالت، نقاط تو پر و تو خالی را می‌توان با تعداد زیادی طبقه بندی کننده خطی به درستی طبقه بندی کرد. H1 (آبی) و H2 (قرمز) آنها را به درستی طبقه بندی می‌کنند. H2 را «بهتر» در نظر می‌گیریم، به این معنا که از هر دو گروه دورتر است. H3 (سبز) نقاط را به درستی طبقه بندی نمی‌کند.

اگر بردار ویژگی ورودی طبقه بندی کننده یک بردار حقیقی ${\vec {x}}$ باشد، خروجی به شکل زیر خواهد بود

$y=f({\vec {w}}\cdot {\vec {x}})=f\left(\sum _{j}w_{j}x_{j}\right),$

که ${\vec {w}}$ بردار حقیقی وزن‌ها و f تابعی است که حاصلضرب نقطه ای دو بردار را به خروجی مورد نظر تبدیل می‌کند. بردار وزن ${\vec {w}}$ از مجموعه ای از نمونه‌های آموزشی با برچسب بدست می‌آید. در بیشتر موارد f یک تابع است که همه مقادیر ${\vec {w}}\cdot {\vec {x}}$ را با یک آستانه معین به کلاس اول و تمام مقادیر دیگر را به کلاس دوم تخصیص می‌دهد. به عنوان مثال،

$f(\mathbf {x} )={\begin{cases}1&{\text{if }}\ \mathbf {w} ^{T}\cdot \mathbf {x} >\theta ,\\0&{\text{otherwise}}\end{cases}}$

$\mathbf {w} ^{T}$ ترانهادهٔ $\mathbf {w}$ و $\theta$ یک آستانه اسکالر است. یک تابع پیچیده‌تر می‌تواند تابعی باشد که احتمال تعلق یک آیتم به طبقهٔ خاص را بدهد.

برای یک مسئله طبقه‌بندی دو کلاسه (باینری)، یک طبقه‌بندی‌کننده خطی را می‌توان به‌عنوان تقسیم کنندهٔ یک فضای ورودی با ابعاد بالا با یک ابرصفحه تصور کرد: بطوریکه تمام نقاط یک طرف ابر صفحه به‌عنوان "طبقه ۱" و بقیهٔ نقاط به عنوان "طبقه ۲" دسته بندی می‌شوند.

طبقه‌بندی‌کننده خطی اغلب در موقعیت‌هایی که سرعت طبقه‌بندی با اهمیت است استفاده می‌شود، زیرا در بیشتر اوقات سریع‌ترین طبقه‌بندی‌کننده است، به‌ویژه زمانی که ${\vec {x}}$ اسپارس (دارای صفرهای زیاد) است. همچنین، طبقه‌بندی‌کننده‌های خطی معمولاً زمانی که بردار ویژگی دارای ابعاد زیاد است، بسیار خوب عمل می‌کند. مانند طبقه بندی اسناد، که در آن هر عنصر در ${\vec {x}}$ معمولاً تعداد تکرار یک کلمه در سند است (به ماتریس سند مراجعه کنید). در چنین مواردی، طبقه بندی کننده باید به خوبی آموزش ببیند شود.

مدل‌های مولد (generative) در مقابل مدل‌های تمیز دهنده (discriminative)

دو روش کلی برای تعیین پارامترهای (${\vec {w}}$) یک طبقه بندی کننده خطی وجود دارد. که آن‌ها را به دو دستهٔ مدل‌های مولد یا تمیز دهنده تقسیم می‌کند. اولین دسته با استفاده از روش‌های توزیع احتمال مانند استفاده از توابع چگالی مشروط $P({\vec {x}}|{\rm {class}})$ پارامترهای مدل را تعیین می‌کند. از این دسته طبقه بندی کننده‌ها می‌توان به موارد زیر اشاره نمود:

• آنالیز افتراقی خطی (LDA) - مدل‌های چگالی شرطی گاوسی
• طبقه بندی کننده ساده بیز با مدل‌های رویداد برنولی چند جمله ای یا چند متغیره.

دسته دوم از طبقه‌بندی کننده‌ها مدل‌های تمیز دهنده هستند که شما سعی نمی‌کنید که مدل احتملاتی که این مشاهدات را تولید کرده را تخمین بزنید بلکه تنها دنبال یک تابع هستید که بتواند تمایز کلاسها را برای شما مشخص کند. مثال‌های برای این دسته از طبقه‌بندی کننده‌ها به شرح زیر هستند:

• رگرسیون لجستیک
• پرسپترون - الگوریتمی که تلاش می‌کند تمام خطاهای موجود در مجموعه آموزشی را برطرف کند
• تجزیه و تحلیل تشخیصی خطی فیشر - الگوریتمی (متفاوت با "LDA") که نسبت پراکندگی بین طبقاتی به پراکندگی درون کلاسی را بدون هیچ فرض دیگری به حداکثر می‌رساند. این در اصل یک روش کاهش ابعاد برای طبقه بندی باینری است.
• ماشین بردار پشتیبان - الگوریتمی که حاشیه بین ابر صفحه تصمیم و عناصر مجموعه آموزشی را به حداکثر می‌رساند.

جستارهای وابسته

• پس انتشار
• رگرسیون خطی
• پرسپترون
• طبقه بندی درجه دوم
• ماشین‌های بردار پشتیبانی می‌کند
• Winnow (الگوریتم)

خواندن بیشتر

1. Y. Yang, X. Liu، "آزمایش مجدد طبقه بندی متن"، Proc. کنفرانس ACM SIGIR, pp. 42-49، (1999). کاغذ @citeseer
2. R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms", MIT Press، (۲۰۰۱).شابک ‎۰−۲۶۲−۰۸۳۰۶-Xشابک 0-262-08306-X