بخشی از مقاله
چکیده
اخیراً تجزیه نامنف ماتریس بعنوان ی از پرکاربردترین روش ها در زمینه داده کاوی معرف شده است. اهمیت این روش را م توان در تسهیل تفسیر داده های نامنف و با بعد بالا بیان کرد. در این نوشتار ضمن معرف ی از مهم ترین وریتم های این روش به نام ANLS، به کاربردی از آن در مسئله کلاس بندی ارقام م پردازیم.
واژهdهای کلیدی: .تجزیه نامنف ماتریس ، کاهش رتبه ماتریس ، مجموعه فعال و کمترین مربعات با قید نامنف
مقدمه
با توجه به رشد روز افزون داده ها و اینکه در بسیاری از موارد اطلاعات واقع در این داده ها دارای ابهام هستند، اساس مشترک رهیافت های مختلف در تحلیل داده ها، پیدا کردن نمایش مفید و مناسب از داده هاست. نمایش که علاوه بر آش ارسازی ساختار پنهان در داده ها، منجر به کاهش ب عد آنها نیز م شود. در دنیای واقع ، بسیاری از داده ها از جمله مقدار غلظت مواد، شدت نور و ... دارای مقادیر نامنف هستند.بنابراین برای ابزارهای تحلیل چنین داده هایی باید همواره شرط نامنف بودن برقرار باشد تا معنای فیزی داده ها حفظ شود.
ابزارهای کلاسی نظیر P CA١ برقراری شرط نامنف بودن داده ها را تضمین نمی کنند. بنابراین استفاده از ابزار قویتری چون تجزیه نامنف ماتریس برای رفع این محدودیت بیان می شود. تعریف برای ماتریس داده نامنف A ∈ Rm,n و عدد طبیع مفروض k ∈ min{m, n}، NMF عوامل ماتریس نامنف و H ∈ Rk,n را طوری پیدا م کند که تقریب ماتریس با رتبه پائین تر بفرم A ≈ W H برای ماتریس داده نامنف تولید شود. بطور معمول در کل ترین حالت، این معادله تقریبی بصورت ی مسئله بهینه سازی بفرم زیر فرمولبندی می شود.
از جمله اقدامات مختلف که برای NMF در مقالات گوناگون پیشنهاد شده می توان به ارائه ال وریتم تکراری بهنگام ضربی توسط Lee و Seung، روش تصویر گرادیان توسط Lin و ال وریتم کمترین مربعات متناوب توسط Berryو هم اران وی اشاره کرد. اخیراً، آثار مختلف افراد بر بهبود هم رایی ال وریتم های مذکور متمرکز شده اند. در این نوشتار به معرف ی از جدیدترین این آثار م پردازیم. ال وریتم که در ادامه بدان خواهیم پرداخت، توسط Kim و P ark با تکیه بر روش مجموعه فعال در سال ٢٠٠٨ معرف گردید.
از روش های پیشنهادی، استفاده از روش مجموعه فعال است. روش مجموعه فعال را می توان برای حل مسائل کمترین مربعات از برد که عامل سمت راست این مسائل ی بردار باشد. اما با وجود حضور بردارهای aj و atj در مسائل که در سمت راست علامت تساوی روابط و قرار دارند، ب ار بردن مستقیم روش مجموعه فعال برای حل تک تک این مسائل موجب کندی اجرای ال وریتم م شود. خوشبختانه برای رفع این مش ل، ال وریتم سریع ترکیبی کمترین مربعات موجود است که روش مجموعه فعال را بطور غیر مستقیم اما همزمان برای همه ستون های ماتریس A و ماتریس At ب ار م برد و بدین ترتیب موجب افزایش سرعت محاسبات م گردد. با توجه به اینکه ال وریتم کمترین مربعات با قید نامنف جزء روشهای کاهش مختصات بلوک است، هم رایی این ال وریتم به نقطه ایستا تضمین شده است .
کلاس بندی ارقام
از مسائل مطرح در تشخیص ارقام م توب۵، کلاس بندی ارقام۶ نامعلوم است. در کلاس بندی ارقام، رقم نامعلوم با استفاده ازمجموعه ای متش ل از ارقام معلوم - آموزش - به کلاس مربوط به خود اختصاص داده م شود. برای نیل به این هدف، از روش NMF و ال وریتم ANLS استفاده کردیم. پای اه داده هدی شامل تصاویری از ارقام فارس ٠ تا ٩ و مجموعه های آموزش و آزمایش بترتیب با ٠٠٠٠۶ و ٢٠٠٠٠ رقم م باشد که ما در مسئله کلاس بندی ارقام به روش NMF، برای مجموعه آموزش از ١٠٠٠ نمونه و برای مجموعه آزمایش جهت تخصیص مورد نظر از ٢٠٠ نمونه - ٢٠ نمونه از تصویر هر رقم - انتخاب کردیم.
ما تصویر هر ی از ارقام را در قالب ی بردار ۶۵٢ ب عدی در نظر گرفتیم. پس از ایجاد ده ماتریس آموزش متناظر با ده کلاس متش از ارقام هم نوع آموزش و نیز بردار d ∈ R256 برای نمایش رقم نامعلوم، بدست آوردن مانده مسئله εi = min ∥Aix − d∥22 را برای تعیین کلاس مربوط به رقم d مد نظر قرار دادیم. با اعمال NMF روی Aiها و فراخوان ستون های Wi که پایه ای برای فضای ستون Ai است، مسئله کمترین مربعات مذکور بصورت εi = min ∥Wiy − d∥22 که در آن y = Hix، تغییر م کند.
حال با پیدا کردن کمترین مقدار مانده εi، م توان رقم d را به کلاس iام اختصاص داد. در کاربردهای مختلف به روش NMF و بطور خاص در مسئله کلاس بندی ارقام، انتخاب مقدار k بسیار مهم است. زیرا دقت بازسازی تصویر هر رقم به تعداد k بردار پایه ای بستگ دارد. در جدول ١ نتایج حاصل از کلاس بندی ارقام فارس با استفاده از روش NMF بازای مقدار k = 10 آورده شده است. در بررس صورت گرفته، میزان موفقیت در تشخیص درست ارقام ، ٩٣ درصد برآورد شد.
نتیجه گیری
تجزیه نامنف ماتریس با ارائه نمایش خط از داده های نامنف ، روش مفید برای تقریب ماتریس نامنف م باشد. جای زین مناسبی برای روشهای کلاسی است. روشهای کلاسی آماری از جمله P CA با وجود کاهش رتبه و ارائه نمایش خط از داده های نامنف ، بدلیل داشتن ویژگ تعامد در خود، تضمین در عدم حضور متغیرهای منف ندارند. این فقدان، تفسیر داده ها را دچار نقصان می کند. اما
با توجه به برقراری قیدهای نامنف می تواند نمایش مبتن بر اجزاء را در تش یل کلیت داده بخوبی معنا بخشد. در روش باید توجه شود که انتخاب مقدار k طوری انجام گیرد که از ی طرف کاهش رتبه ماتریس و از طرف دی ر دقت مورد نظر حاصل گردد. این انتخاب در کاربردها مشخص م شود. اما در هر حال تعیین مقدار مناسب برای پارامتر k، همچنان تحت مطالعه است.
