آنالیز افتراقی خطی

آنالیز تشخیصی خطی (به انگلیسی: Linear Discriminant Analysis، به طور مخفف LDA) و تشخیص خطی فیشر روش‌های آماری هستند که از جمله در یادگیری ماشین و بازشناخت الگو برای پیدا کردن ترکیب خطی خصوصیاتی که به بهترین صورت دو یا چند کلاس از اشیا را از هم جدا می‌کند، استفاده می‌شوند.

آنالیز تشخیصی خطی بسیار به تحلیل واریانس و تحلیل رگرسیونی نزدیک است؛ در هر سهٔ این روش‌های آماری متغیر وابسته به صورت یک ترکیب خطی از متغیرهای دیگر مدل‌سازی می‌شود.[1][2] با این حال دو روش آخر متغیر وابسته را از نوع فاصله‌ای در نظر می‌گیرند در حالی که آنالیز افتراقی خطی برای متغیرهای وابستهٔ اسمی یا رتبه‌ای به کار می‌رود.[3] از این رو آنالیز افتراقی خطی به رگرسیون لجستیک شباهت بیشتری دارد.

آنالیز تشخیصی خطی همچنین با تحلیل مؤلفه‌های اصلی و تحلیل عاملی هم شباهت دارد؛ هر دوی این روش‌های آماری برای ترکیب خطی متغیرها به شکلی که داده را به بهترین نحو توضیح بدهد به کار می‌روند[4] یک کاربرد عمدهٔ هر دوی این روش‌ها، کاستن تعداد بعدهای داده است. با این حال این روش‌ها تفاوت عمده‌ای با هم دارند: در آنالیز افتراقی خطی، تفاوت کلاس‌ها مدل‌سازی می‌شود در حالی که در تحلیل مؤلفه‌های اصلی تفاوت کلاس‌ها نادیده گرفته می‌شود.

LDA ارتباط نزدیکی با تحلیل واریانس و تحلیل رگرسیون دارد که سعی دارند یک متغیر مستقل را به عنوان ترکیبی خطی از ویژگی‌های دیگر بیان کنند. این متغیر مستقل در LDA به شکل برچسب یک کلاس است. همچنین LDA ارتباطی تناتنگ با تحلیل مؤلفه‌های اصلی PCA دارد. چرا که هر دو متد به دنبال ترکیبی خطی از متغیرهایی هستند که به بهترین نحو داده‌ها را توصیف می‌کنند. LDA همچنین سعی در مدلسازی تفاوت بین کلاس‌های مختلف داده‌ها دارد. از LDA زمانی استفاده می‌شود که اندازه‌های مشاهدات، مقادیر پیوسته باشند.[5][6]

LDA برای دو کلاس

مجموعه ای از مشاهدات را به نام${\displaystyle {\vec {x}}}$ برای هر نمونه از یک شی یا پدیده با کلاس شناخته شده y در نظر بگیرید. این مجموعه از نمونه‌ها مجموعه آموزش نامیده می‌شود. مسئله دسته‌بندی پیدا کردن یک پیش‌بینی‌کننده (predictor) برای هر کلاس از همان توزیع (نه لزوماً از مجموعه آموزش) داده شده از مجموعه مشاهده x است.[7]^:338. LDA با این فرض که تابع چگالی احتمال شرطی ${\displaystyle p({\vec {x}}|y=0)}$ و ${\displaystyle p({\vec {x}}|y=1)}$ هر دو، توزیع نرمال با پارامترهای میانگین و کواریانس ${\displaystyle ({\vec {u_{0}}},\Sigma _{0})}$ و ${\displaystyle ({\vec {u_{1}}},\Sigma _{1})}$هستند. حال با کمک راه حل بهینه بیز، پیش‌بینی می‌شود که نقاطی درستنمایی(likelihood) برای آنها کمتر از مقدار آستانه T باشد،از کلاس دوم هستند؛ یعنی:

 ${\displaystyle ({\vec {x}}-{\vec {\mu }}_{0})^{T}\Sigma _{0}^{-1}({\vec {x}}-{\vec {\mu }}_{0})+\ln |\Sigma _{0}|-({\vec {x}}-{\vec {\mu }}_{1})^{T}\Sigma _{1}^{-1}({\vec {x}}-{\vec {\mu }}_{1})-\ln |\Sigma _{1}|\ <\ T}$

بدون هیچ فرض اضافه‌ای دسته بندی‌کننده حاصل به عنوان QDA (Quadratic discriminant analysis) شناخته می‌شود. LDA علاوه براین‌ها فرض ساده‌کننده همواریانسی(Homoscedasticity) (یعنی برابری کواریانس کلاسها، ) و کواریانس‌ها رتبه کامل هستند. در این مورد، اصطلاحات گوناگون باطل می‌شوند و معیار تصمیم آستانه ضرب نقطه ای زیر خواهد بود:

${\displaystyle {\vec {w}}\cdot {\vec {x}}>c}$

برای آستانه معین ثابتی به نام c، در حالی که:

${\displaystyle {\vec {w}}\propto \Sigma ^{-1}({\vec {\mu }}_{1}-{\vec {\mu }}_{0})}$

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

LDA استاندارد برای k کلاس

CDA آنالیز افتراقی استاندارد محورهای مختصاتی (K-1 مختصات استاندارد، K تعداد کلاس‌ها را نشان می‌دهد) را که به بهترین شکل دسته‌ها را از هم مجزا می¬کند پیدا می‌کند. این توابع خطی ناهمبسته هستند و k-1 فضا را از طریق ابر n بعدی از داده‌ها که به بهترین شکل k گروه را از هم مجزا می‌کند. برای جزئیات بیشتر LDA چند کلاسه را ببینید.

افتراق‌دهنده‌ی خطی فیشر

هرچند مقاله اصلی فیشر[1] رویکرد متفاوتی برای تعریف یک افتراق‌دهنده بکار می‌گیرد و بعضی فرضیات LDA مانند کلاسهای دارای توزیع نرمال یا کواریانس برابر کلاس را ندارد، واژه‌های افتراق خطی فیشر و LDA معمولاً به جای یکدیگر به کار می‌روند. دو کلاس از مشاهدات را با میانگین‌های و کواریانس‌های در نظر بگیرید. حالا ترکیب خطی دارای میانگین و واریانس برای هستند. افتراق‌دهنده فیشر بین این دو توزیع را به صورت نسبت واریانس بین دو کلاس به واریانس درون دو کلاس تعریف کرد:

${\displaystyle S={\frac {\sigma _{\text{between}}^{2}}{\sigma _{\text{within}}^{2}}}={\frac {({\vec {w}}\cdot {\vec {\mu }}_{y=1}-{\vec {w}}\cdot {\vec {\mu }}_{y=0})^{2}}{{\vec {w}}^{T}\Sigma _{y=1}{\vec {w}}+{\vec {w}}^{T}\Sigma _{y=0}{\vec {w}}}}={\frac {({\vec {w}}\cdot ({\vec {\mu }}_{y=1}-{\vec {\mu }}_{y=0}))^{2}}{{\vec {w}}^{T}(\Sigma _{y=0}+\Sigma _{y=1}){\vec {w}}}}}$

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

${\displaystyle {\vec {w}}\propto (\Sigma _{y=0}+\Sigma _{y=1})^{-1}({\vec {\mu }}_{y=1}-{\vec {\mu }}_{y=0})}$

وقتی که فرضیات LDA ارضا شد، معادله بالا معادل با LDA خواهد بود. حتماً به یاد داشته باشید که بردار بردار نرمال ابرصفحه جداکننده است. به عنوان یک مثال، در یک مسئله دوبعدی، خطی که دو گروه را به بهترین شکل تقسیم می‌کند عمودمنصف است. به‌طور کلی، نقاط داده‌ای که باید جدا شوند باید بر روی بردار ${\displaystyle {\vec {w}}}$ تصویر شوند. پس آستانه‌ای که به بهترین وجه داده را جداسازی می‌کند از تحلیل توزیع یک‌بعدی انتخاب می‌شود. قاعده‌ای کلی برای آستانه وجود ندارد. به هر حال، اگر تصاویر نقاط از هر دو کلاس تقریباً یک توزیع را نشان دهد، ابرصفحه وسط تصاویر دو مرکز یک انتخاب مناسب خواهد بود. در این مورد پارامتر c در شرط آستانه صریحاً به صورت زیر خواهد بود:

${\displaystyle c={\vec {w}}\cdot {\frac {1}{2}}({\vec {\mu }}_{y=0}+{\vec {\mu }}_{y=1})={\frac {1}{2}}{\vec {\mu }}_{y=1}^{t}\Sigma ^{-1}{\vec {\mu }}_{y=1}-{\frac {1}{2}}{\vec {\mu }}_{y=0}^{t}\Sigma ^{-1}{\vec {\mu }}_{y=0}}$

LDA چند کلاسه

وقتی که بیش از یک کلاس وجود داشته باشد، همان معادلات و روابطی که در تکنیک افتراقی فیشر بکار می‌روند را می‌توان برای پیدا کردن آن زیرفضایی بکار برد که بنظر می‌رسد می‌تواند تمام دامنهٔ تغییرپذیری داده‌ها در کلاس‌های گوناگون را نشان دهد. چنین تعمیمی به واسطهٔ کارهای C.R. Rao [8] بدست آمده است. فرض کنید هر کلاس از C کلاس یک میانگین${\displaystyle \mu _{i}}$ و یک کواریانس ${\displaystyle \sigma }$ دارد. پس تغییرپذیری بین کلاس‌ها ممکن است با استفاده از نمونه کواریانس میانگین‌های کلاس تعریف شود:

${\displaystyle \Sigma _{b}={\frac {1}{C}}\sum _{i=1}^{C}(\mu _{i}-\mu )(\mu _{i}-\mu )^{T}}$

در حالی که میانگین، میانگین، کلاس¬ها است. جداسازی کلاس در یک جهت در این مورد با عبارت زیر داده خواهد شد:

${\displaystyle S={\frac {{\vec {w}}^{T}\Sigma _{b}{\vec {w}}}{{\vec {w}}^{T}\Sigma {\vec {w}}}}}$

معنی اش این است که وقتی یک بردار ویژه از باشد جداسازی، معادل با مقدار ویژه متناظرش خواهد بود.

اگر ${\displaystyle \Sigma ^{-1}\Sigma _{b}}$ قطری باشد، تغییرپذیری بین ابعاد(features) در زیرفضای گسترش یافته با بردارهای ویژه متناظر با c-1 امین مقدار ویژه بزرگتر(به این علت که سلسله از c-1 در اکثر است). چنین بردارهای ویژه ای مانند PCA در ابتدا در کاهش ابعاد استفاده می¬شدند. بردارهای ویژه متناطر با مقادیر ویژه کوچکتر برای انتخاب داده‌های آموزش حساس تر است، و اغلب لازم است تا مرتب سازی توصیف شده در بخش بعد را به کار برد. اگر به جای کاهش ابعاد دسته‌بندی موردنیاز باشد، تعدادی تکنیک جایگزین وجود دارد. برای مثال، کلاس‌ها را می¬توان پارتیشن بندی کرد و آنالیز افتراقی فیشر استاندارد یا LDA را برای دسته‌بندی هر پارتیشتن به کار برد. یک مثال رایج از این رویکرد "یکی در برابر بقیه" است، وقتی که نقاط از یک کلاس در یک گروه قرار می¬گیرند، و هر چیز دیگر در دیگری، سپس LDA اعمال می‌شود. که این کار به C classifier منتج می¬شود، که نتایج آن ترکیب می‌شود. روش رایج دیگری دسته‌بندی جفتی است، جایی که یک دسته بند جدید برای هر جفت از کلاس‌ها ایجاد می‌شود (در مجموع C-1 دسته بندی‌کننده داده می‌شود)، با ترکیب دسته‌بندی کننده‌های منفرد برای تولید یک دسته بندی‌کننده نهایی.

کاربرد عملی

در عمل، میانگین کلاس‌ها و کواریانس‌ها معلوم نیست. هرچند می‌توان آن‌ها را از مجموعه آموزش تخمین زد. برآورد بیشترین درستنمایی (maximum likelihood estimate) یا برآورد پسین حداکثر( maximum a posteriori) را می‌توان به جای مقدار دقیق در معادلات بالا به کار برد. اگرچه برآورد کواریانس بعضی مواقع بهینه در نظر گرفته شده‌است، به این معنی نیست که افتراق بدست آمده با جایگزینی این مقادیر همیشه بهینه باشد، حتی اگر فرض توزیع نرمال کلاس‌ها درست باشد. پیچیدگی دیگر در اعمال LDA و افتراق‌دهندهٔ فیشر به داده‌های واقعی وقتی که تعداد مشاهدات هر نمونه از تعداد نمونه‌ها کمتر باشد روی می¬دهد.[4] در این مورد، برآورد کواریانس full rank نیست، پس نمی‌تواند معکوس شود. روش‌های گوناگونی برای حل این مشکل وجود دارد. یک روش استفاده از شبه معکوس به جای ماتریس معکوس معمولی در فرمول بالاست. به هر حال، پایداری بهتر عددی با پرتو اندازی(پروجکشن) مسئله بر زیرفضای گسترش یافته با ممکن است بدست آید.[9] راهبرد دیگر برای حل مشکل اندازه نمونه استفاده از یک برآوردگر انقباضی (Shrinkage estimator) از ماتریس کواریانس است، به بیان ریاضی:

${\displaystyle C_{\text{new}}=(1-\lambda )C+\lambda I\,}$

${\displaystyle I}$ ماتریس همانی است، و ${\displaystyle \lambda }$ پارامتر منظم‌کننده (regularization parameter) یا شدت انقباض است. این کار، مبنای آنالیز افتراقی منظم‌سازی شده یا آنالیز افتراقی انقباضی را فراهم می‌کند. همچنین در بسیاری از موارد عملی افتراق خطی مفید نیست. LDA و افتراق‌دهندهٔ فیشر با استفاده از ترفند کرنل Kernel method قابل تعمیم به دسته¬بندی غیرخطی هستند. در اینجا مشاهدات اصلی به صورت مؤثر به یک فضای غیرخطی بالاتر نگاشت می¬شوند. دسته¬بندی خطی در این فضای غیرخطی معادل دسته¬بندی غیرخطی در فضای اصلی است. مثال بسیار رایج روش کرنل افتراقی فیشر kernel Fisher discriminant است. LDA قابل تعمیم به آنالیز افتراقی چند دسته‌ایی نیز است، وقتی که c یک متغیر رتبه¬ای با N حالت ممکن به جای دو حالت باشد. به‌طور مشابه، اگر چگالی¬های شرطی کلاس با یک کواریانس مشترک نرمال باشد، آماره بسنده برای مقادیری از N تصویر (پروجکشن) است، که زیرفضایی است که با N میانگین گسترش یافته‌است، با affine projected که به وسیله ماتریس کواریانس معکوس. این پروجکشن‌ها در حل یک مسئله مقدار ویژه تعمیم یافته یافت می¬شوند، جایی که صورت ماتریس کواریانسی است که با درنظرگرفتن میانگین‌ها به عنوان نمونه‌ها تشکیل شده‌است، و مخرج ماتریس کواریانس مشترک است.

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

• لوجیت
• پرسپترون
• تحلیل مولفه‌های اصلی

منابع

1. Fisher, R. A. (1936). "The Use of Multiple Measurements in Taxonomic Problems". Annals of Eugenics. 7 (2): 179–188. doi:10.1111/j.1469-1809.1936.tb02137.x. hdl:2440/15227.
2. McLachlan, G. J. (2004). Discriminant Analysis and Statistical Pattern Recognition. Wiley Interscience. ISBN 0-471-69115-1. MR 1190469.
3. Analyzing Quantitative Data: An Introduction for Social Researchers, Debra Wetcher-Hendricks, p.288
4. Martinez, A. M.; Kak, A. C. (2001). [/~aleix/pami01.pdf "PCA versus LDA"] Check |url= value (help) (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 23 (=2): 228–233. doi:10.1109/34.908974.
5. Abdi, H. (2007) "Discriminant correspondence analysis." In: N.J. Salkind (Ed.): Encyclopedia of Measurement and Statistic. Thousand Oaks (CA): Sage. pp. 270–275.
6. Perriere, G.; & Thioulouse, J. (2003). "Use of Correspondence Discriminant Analysis to predict the subcellular location of bacterial proteins", Computer Methods and Programs in Biomedicine, 70, 99–105.
7. Venables, W. N.; Ripley, B. D. (2002). Modern Applied Statistics with S (4th ed.). Springer Verlag. ISBN 0-387-95457-0.
8. Rao, R. C. (1948). [/stable/2983775 "The utilization of multiple measurements in problems of biological classification"] Check |url= value (help). Journal of the Royal Statistical Society, Series B. 10 (2): 159–203.
9. Yu, H.; Yang, J. (2001). "A direct LDA algorithm for high-dimensional data — with application to face recognition", Pattern Recognition, 34 (10), 2067–2069