مقاله کاھش ابعاد داده در داده کاوی

بخشی از مقاله

چکیده

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

-1 مقدمه

1-1 دادهکاوي

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

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

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

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

.2-1 کاهش ابعاد داده

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

علت اول افزایش تعداد مشاهدات و علت دوم که از اهمیت بالاتري برخوردار است افزایش تعداد متغیرهاي مربوط به یک مشاهده است .[3] درمجموع این مقاله با بیان تعاریفی روشن و جامع از کاهش ابعاد داده، دادهکاوي و همچنین کاربردهاي آنها، خواننده را در درك بهتر این مفاهیم یاري میکند؛ و باعث ایجاد نگرشی متفاوت در ذهن مخاطب نسبت به مطالب ذکر شده میگردد.

-2 تقلیل یا فروکاهی ابعاد

بسترهاي داده اي که داراي ابعاد زیادي هستند علیرغم فرصتهایی که به وجود می آورند، چالشهاي محاسباتی زیادي را ایجاد می کنند.

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

تقلیل یا فروکاهی ابعاد، به فرآیند کاستن و کم کردن از تعداد ابعاد و متغیرهاي موردنیاز براي نمایش و بررسی مسائل مطروحه در ریاضیات، آمار، فیزیک، مهندسی و بسیاري از شاخههاي علوم محاسباتی و پیچیدهي نوین اطلاق میشود

در ادبیات تحلیلهاي چند متغیرياساساً به روشهایی که براي کاهش ابعاد استفاده میشود، روشهاي محوري یا روش هاي هندسی نیز گفته میشود .[5] روشهاي کاهش ابعاد داده به دودسته تقسیم می شوند:

روشهاي مبتنی بر استخراج ویژگی

روشهاي مبتنی بر انتخاب ویژگی

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

1-2 روشهاي مبتنی بر استخراج ویژگی

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

1-1-2 تبدیل فوریه گسسته - DTF -

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

2-1-2 تبدیل موجک گسسته - DWT -

تبدیل DWT براي اولین بار توسط شخصی به نام Alfred Haar به وجود آمد. تاکنون نسخه هاي مختلفی براي DWT ارائهشده است،
مانند  Haar  Wavelet،  Newland  Transform  و .Undecimated Wavelet Transform این تبدیل نیز همانند تبدیل فوریه بسیار پرکاربرد است و در بسیاري از زمینه هاي علوم و مهندسی موردتوجه قرارگرفته است. تبدیل Haar Wavelet به دلیل سادگی در پیادهسازي و سرعت اجراي بالا، از محبوبیت بیشتري نسبت به سایر نسخه¬هاي DWT برخوردار است.

3-1-2 استخراج ویژگی در پردازش تصویر

براي اینکه از روي الگوهاي یک تصویر هویت و یا خالق آن تصویر مشخص شود باید یکسري مشخصات عام و یا خاص از دل تصویر بیرون کشیده شود که به این کار استخراج ویژگی گفته میشود. بهعنوانمثال در تشخیص امضاء بهوسیله پردازش تصویر یک سري ویژگیها - مانند شیبخطها - از تصویر اسکن شدهي امضاء بیرون کشیده میشود که بهوسیله آن میتوان صاحب امضاء را تشخیص داد

4-1-2 استخراج ویژگی در پردازش گفتار

در تجزیهوتحلیل سیگنال گفتار ویژگیهاي مختلفی استفاده میشود که انتخاب ویژگی موردنظر بسته به کاربرد صورت میگیرد، چراکه شرایط مناسب کاربرد هر یک با دیگري متفاوت است.

2-2 روشهاي مبتنی بر انتخاب ویژگی

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

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

حذف نکردن این ویژگی ها مشکلی ازلحاظ اطلاعاتی ایجاد نمی کند ولی بار محاسباتی را براي کاربرد موردنظر بالا می برد؛ و علاوه بر این باعث می شود که اطلاعات غیرمفید زیادي را به همراه داده هاي مفید ذخیره کنیم. در این بخش روشهاي مختلف را بر اساس نوع و ترتیب تولید زیرمجموعه ویژگیهاي کاندید و همچنین نحوه ارزیابی این زیرمجموعه ها دستهبندي می کنیم. سپس تعدادي از روشهاي معرفیشده در هر دسته را معرفی و بر اساس اهمیت تا جایی که مقدور باشد، آنها را تشریح می کنیم. لازم به ذکر است که به دلیل اینکه مبحث انتخاب ویژگی به مبحث طبقهبندي بسیار نزدیک است، بعضی از مسائلی که در اینجا مطرح می شود مربوط به مبحث طبقهبندي
 است. توضیحات ارائهشده در حد آشنایی است. شما می توانید براي کسب اطلاعات بیشتر به منابع معرفیشده مراجعه نمایید.

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

براي اینکه بتوانیم تقسیمبندي درستی از روشهاي مختلف انتخاب ویژگی داشته باشیم، به این صورت عمل می کنیم که فرآیند انتخاب ویژگی در تمامی روشها را به این بخش ها تقسیم می کنیم:

.1تابع تولیدکننده : این تابع زیرمجموعه هاي کاندید را براي روش موردنظر پیدا می کند.

.2تابع ارزیابی : زیرمجموعه موردنظر را بر اساس روش دادهشده، ارزیابی و یک عدد به عنوان میزان خوبی روش بازمیگرداند . روشهاي مختلف سعی دریافتن زیرمجموعه اي دارند که این مقدار را بهینه کند. .3شرط خاتمه: براي تصمیم گیري در مورد زمان توقف الگوریتم.

.4تابع تعیین اعتبار : تصمیم می گیرد که آیا زیرمجموعه انتخابشده معتبر است یا خیر؟

.2جستجوي مکاشفه اي .3جستجوي تصادفی

2-2-2 تابع ارزیابی

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

توابع ارزیابی را می توان به طرق مختلفی دستهبندي کرد. در اینجا ما دستهبندي اي که توسط Dash و Liu ارائهشده است را بیان می کنیم. آنها این معیارها را به پنج دست تقسیم کرده اند:

.1معیارهاي مبتنی بر فاصله .2معیارهاي مبتنی بر اطلاعات .3معیارهاي مبتنی بر وابستگی .4معیارهاي مبتنی بر سازگاري

.5معیارهاي مبتنی بر خطاي طبقهبندي کننده

شکل 1 فرآیند انتخاب ویژگی .[9]

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

1-2-2 توابع تولیدکننده

اگر تعداد کل ویژگی ها برابر N باشد، تعداد کل زیرمجموعه هاي ممکن برابر N 2 می شود. این تعداد براي N هاي متوسط هم خیلی زیاد است . بر اساس نحوه جستجو در میان این تعداد زیرمجموعه، روشهاي مختلف انتخاب ویژگی را می توان به سه دسته زیر تقسیم بندي نمود:

.1جستجوي کامل

3-2دستهبندي و تشریح الگوریتمهاي مختلف انتخاب ویژگی

در این قسمت بر اساس تابع ارزیابی و تابع تولیدکننده، روشهاي مختلف انتخاب ویژگی را به چند دسته تقسیمبندي می کنیم و سپس تعدادي از روشها را شرح داده و الگوریتم کار را بهصورت شبه کد، ذکر می کنیم.

قبل از اینکه بحث را ادامه دهیم، لازم است که متغیرهاي بهکاررفته در شبه کدها را معرفی کنیم. این متغیرها و شرح آنها بهصورت زیر است:

•    متغیر :D مجموعه آموزشی
•    متغیر :S مجموعه ویژگی اصلی - شامل تمام ویژگی ها -
•    متغیر :N تعداد ویژگی ها
•    متغیر :T زیرمجموعه ویژگی انتخابشده
•    متغیر :M تعداد ویژگیهاي انتخابشده یا تعداد ویژگی هایی که لازم است انتخاب شوند [10]،.[11]

1-3-2 تابع ارزیابی مبتنی بر فاصله - تابع تولیدکننده مکاشفهاي

مهم ترین روش در این گروه Relief است. در اینجا ما ابتدا این روش را بهعنوان نماینده این گروه شرح می دهیم، سپس یک مرور مختصري بر سایر روشها خواهیم داشت.