Astaraki

مقدمه ای بر داده کاوی خوشه بندی و طبقه بندی

مقدمه
امروزه با گسترش سیستم های پایگاهی و حجم بالای داده ها ی ذخیره شده در این سیستم ها ، نیاز به ابزاری است تا بتوان داده های ذخیره شده پردازش کرد و اطلاعات حاصل از این پردازش را در اختیار کاربران قرار داد .
با استفاده ار پرسش های ساده در SQL و ابزارهای گوناگون گزارش گیری معمولی ، می توان اطلاعاتی را در اختیار کاربران قرار داد تا بتوانند به نتیجه گیری در مورد داده ها و روابط منطقی میان آنها بپردازند اما وقتی که حجم داده ها بالا باشد ، کاربران هر چند زبر دست و با تجربه باشند نمی توانند الگوهای مفید را در میان حجم انبوه داده ها تشخیص دهند و یا اگر قادر به این کار هم با شند ، هزینه عملیات از نظر نیروی انسانی و مادی بسیار بالا است .
از سوی دیگر کاربران معمولا فرضیه ای را مطرح می کنند و سپس بر اساس گزارشات مشاهده شده به اثبات یا رد فرضیه می پردازند ، در حالی که امروزه نیاز به روشهایی است که اصطلاحا به کشف دانش بپردازند یعنی با کمترین دخالت کاربر و به صورت خودکار الگوها و رابطه های منطقی را بیان نمایند .
داده کاوی یکی از مهمترین این روشها است که به وسیله آن الگوهای مفید در داده ها با حداقل دخالت کاربران شناخته می شوند و اطلاعاتی را در اختیار کاربران و تحلیل گران قرار می دهند تا براساس آنها تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند .
در داده کاوی از بخشی از علم آمار به نام تحلیل اکتشافی داده ها استفاده می شود که در آن بر کشف اطلاعات نهفته و ناشناخته از درون حجم انبوه داده ها تاکید می شود . علاوه بر این داده کاوی با هوش مصنوعی و یادگیری ماشین نیز ارتباط تنگاتنگی دارد ، بنابراین می توان گفت در داده کاوی تئوریهای پایگاه داده ها ، هوش مصنوعی ، یادگیری ماشین و علم آمار را در هم می آمیزند تا زمینه کاربردی فراهم شود .
باید توجه داشت که اصطلاح داده کاوی زمانی به کار برده می شود که با حجم بزرگی از داده ها ، در حد مگا یا ترابایت ، مواجه باشیم . در تمامی منابع داده کاوی بر این مطلب تاکید شده است .
هر چه حجم داده ها بیشتر و روابط میان آنها پیچیده تر باشد دسترسی به اطلاعات نهفته در میان داده ها مشکلتر می شود و نقش داده کاوی به عنوان یکی از روشهای کشف دانش ، روشن تر می گردد .
مفاهیم پایه در داده کاوی
در داده کاوی معمولا به کشف الگوهای مفید از میان داده ها اشاره می شود . منظور از الگوی مفید ، مدلی در داده ها است که ارتباط میان یک زیر مجموعه از داده ها را توصیف می کند و معتبر ، ساده ، قابل فهم و جدید است .
تعریف داده کاوی
در متون آکادمیک تعاریف گوناگونی برای داده کاوی ارائه شده اند . در برخی از این تعاریف داده کاوی در حد ابزاری که کاربران را قادر به ارتباط مستقیم با حجم عظیم داده ها می سازد معرفی گردیده است و در برخی دیگر ، تعاریف دقیقتر که درآنها به کاوش در داده ها توجه می شود موجود است . برخی از این تعاریف عبارتند از :
· داده کاوی عبارت است از فرایند استخراج اطلاعات معتبر ، از پیش ناشناخته ، قابل فهم و قابل اعتماد از پایگاه داده های بزرگ و استفاده از آن در تصمیم گیری در فعالیت های تجاری مهم.
· اصطلاح داده کاوی به فرایند نیم خودکار تجزیه و تحلیل پایگاه داده های بزرگ به منظور یافتن الگوهای مفید اطلاق می شود
· داده کاوی یعنی جستجو در یک پایگاه داده ها برای یافتن الگوهایی میان داده ها .
· داده کاوی یعنی استخراج دانش کلان ، قابل استناد و جدید از پایگاه داده ها ی بزرگ .
· داده کاوی یعنی تجزیه و تحلیل مجموعه داده های قابل مشاهده برای یافتن روابط مطمئن بین داده ها .
همانگونه که در تعاریف گوناگون داده کاوی مشاهده می شود ، تقریبا در تمامی تعاریف به مفاهیمی چون استخراج دانش ، تحلیل و یافتن الگوی بین داده ها اشاره شده است
برخی از کاربردهای داده کاوی در محیطهای واقعی عبارتند از :
1. خرده فروشی : از کاربردهای کلاسیک داده کاوی است که می توان به موارد زیر اشاره کرد :
· تعیین الگوهای خرید مشتریان
· تجزیه و تحلیل سبد خرید بازار
· پیشگویی میزان خرید مشتریان از طریق پست(فروش الکترونیکی)
2. بانکداری :
· پیش بینی الگوهای کلاهبرداری از طریق کارتهای اعتباری
· تشخیص مشتریان ثابت
· تعیین میزان استفاده از کارتهای اعتباری بر اساس گروههای اجتماعی
3. بیمه :
· تجزیه و تحلیل دعاوی
· پیشگویی میزان خرید بیمه نامه های جدید توسط مشتریان
4. پزشکی :
· تعیین نوع رفتار با بیماران و پیشگویی میزان موفقیت اعمال جراحی
· تعیین میزان موفقیت روشهای درمانی در برخورد با بیماریهای سخت
مراحل فرایند کشف دانش از پایگاه داده ها
فرایند کشف دانش از پایگاه داده ها شامل پنج مرحله است که عبارتند از :
1. انبارش داده ها
2. انتخاب داده ها
3. تبدیل داده ها
4. کاوش در داده ها
5. تفسیر نتیجه
همانگونه که مشاهده می شود داده کاوی یکی از مراحل این فرایند است که به عنوان بخش چهارم آن نقش مهمی در کشف دانش از داده ها ایفا می کند .
انبارش داده ها
وجود اطلاعات صحیح و منسجم یکی از ملزوماتی است که در داده کاوی به آن نیازمندیم . اشتباه و عدم وجود اطلاعات صحیح باعث نتیجه گیری غلط و در نتیجه اخذ تصمیمات ناصحیح در سازمانها می گردد و منتج به نتایج خطرناکی خواهد گردید که نمونه های آن کم نیستند .
اکثر سازمانها دچار یک خلا اطلاعاتی هستند . در اینگونه سازمانها معمولا سیستم های اطلاعاتی در طول زمان و با معماری و مدیریت های گوناگون ساخته شده اند ، به طوری که سازمان اطلاعاتی یکپارچه و مشخصی مشاهده نمی گردد . علاوه بر این برای فرایند داده کاوی به اطلاعات خلاصه و مهم در زمینه تصمیم گیریهای حیاتی نیازمندیم .
هدف از فرایند انبارش داده ها فراهم کردن یک محیط یکپارچه جهت پردازش اطلاعات است . در این فرایند ، اطلاعات تحلیلی و موجز در دوره های مناسب زمانی سازماندهی و ذخیره می شود تا بتوان از آنها در فرایند های تصمیم گیری که از ملزومات آن داده کاوی است ، استفاده شود . به طور کلی تعریف زیر برای انبار داده ها ارائه می گردد :
انبار داده ها ، مجموعه ای است موضوعی ، مجتمع ، متغیر در زمان و پایداراز داده ها که به منظور پشتیبانی از فرایند مدیریت تصمیم گیری مورد استفاده قرار می گیرد .

انتخاب داده ها
انبار داده ها شامل انواع مختلف و گوناگونی از داده ها است که همه آنها در داده کاوی مورد نیاز نیستند . برای فرایند داده کاوی باید داده ها ی مورد نیاز انتخاب شوند . به عنوان مثال در یک پایگاه داده های مربوط به سیستم فروشگاهی ، اطلاعاتی در مورد خرید مشتریان ، خصوصیات آماری آنها ، تامین کنندگان ، خرید ، حسابداری و ... وجود دارند . برای تعیین نحوه چیدن قفسه ها تنها به داده ها یی در مورد خرید مشتریان و خصوصیات آماری آنها نیاز است . حتی در مواردی نیاز به کاوش در تمام محتویات پایگاه نیست بلکه ممکن است به منظور کاهش هزینه عملیات ، نمونه هایی از عناصر انتخاب و کاوش شوند .
تبدیل داده ها
هنگامی که داده های مورد نیاز انتخاب شدند و داده ها ی مورد کاوش مشخص گردیدند ، معملا به تبدیلات خاصی روی داده ها نیاز است . نوع تبدیل به عملیات و تکنیک داده کاوی مورد استفاده بستگی دارد : تبدیلاتی ساده همچون تبدیل نوع داده ای به نوع دیگر تا تبدیلات پیچیده تر همچون تعریف صفات جدید با انجام عملیاتهای ریاضی و منطقی روی صفات موجود .
کاوش در داده ها
داده های تبدیل شده با استفاده از تکنیکها و عملیاتهای داده کاوی مورد کاوش قرار می گیرند تا الگوهای مورد نظر کشف شوند .
تفسیر نتیجه
اطلاعات استخراج شده با توجه به هدف کاربر تجزیه و تحلیل و بهترین نتایج معین می گردند . هدف از این مرحله تنها ارائه نتیجه (بصورت منطقی و یا نموداری) نیست ، بلکه پالایش اطلاعات ارایه شده به کاربر نیز از اهداف مهم این مرحله است .
داده کاوی منحصر به گردآوری و مدریت داده‌ها نبوده و تجزیه و تحلیل اطلاعات و پیش بنی را نیز شامل می‌شود برنامه‌های کاربردی که با برسی فایل‌های متن یا چند رسانه‌ای به کاوش داده‌های پردازنده پارامترهای گوناگونی را در نظر می‌گیرد که عبارت انداز:
رابطه (Association): الگوهایی که بر اساس آن یک رویداد به دیگری مربوط می‌شود مثلا خرید قلم به خرید کاغذ.
ترتیب (Sequence): الگویی که به تجزیه و تحلیل توالی رویدادها پرداخته و مشخص می‌کند کدام رویداد رویدادهای دیگری را در پی دارد مثلا تولد یک نوزاد و خرید پوشک.
طبقه بندی(Classification): شناسایی الگوهای جدید مثلا همزمانی خرید چسب و پوشه
خوشه بندی(Closeting): کشف و مستند سازسی مجموعه‌ای از حقایق ناشناخته مثلا موقعیت جغرافیایی خرید محصولی با مارک خاص
پیش بینی(Forecasting):کشف الگوهایی که بر اساس آنها پیش بینی قابل قبولی از رویدادهای آتی ارایه می‌شود، مثلا رابطه عضویت در یک باشگاه ورزشی با شرکت ذر کلاسهای ورزشی.
خوشه بندی
قابلیت خوشه بندی وظیفه تقسیم یك گروه ناهمجنس را در چندین زیر گروه بر عهده دارد. این فرایند یك تفاوت اساسی با طبقه بندی دارد. زیرا در این مدل هیچ گونه الگوی آموزشی نداریم. خوشه بندی به طور خودكار ویژگی های متمایز كننده زیر گروه ها را تعریف می كند و زیر گرو هها را سازماندهی می نماید. و به عنوان نوعی قابلیت داده كاوی غیر مستقیم مطرح است.
این ابزارها پایگاه داده را بر اساس ویژگی های داده ها به چندین بخش تقسیم می كنند و گروه هایی ازركوردها را به وجود می آورند كه نمایانگر یا صاحب صفت خاصی هستند. الگوهای به دست آمده در ذاتپایگاه داده نهادینه هستند و نشانگر بعضی اطلاعات غیر منتظره و در عین حال ارزشمند شركتی باشند.
مثالی از كاربردهای خوشه بندی در تقسیم بندی افرادی است كه به پرسش نامه ای پاسخ داده اند. از این كار می توان در تقسیم بندی مشتریانی كه به پرسش نامه ها پاسخ داده اند در گروه هایی كه اعضای آن بیشترین شباهت را با یكدیگر و بیشترین تفاوت را با اعضای سایر گروه ها دارند، استفاده كرد. بعد از بخش بندی جمعیتی با استفاده از قابلیت خوشه بندی می توان بر روی خوشه های مشخص شده تحلیل هم پیوندی انجام داد تا خریدهای به هم مرتبط یك گروه جمعیتی خاص شناخته شوند.
كاربرد خوشه بندی برای تعیین بهترین گروه های جامعه شناختی برای اهداف خاص بازاریابی است.
اغلب از خوشه بندی به عنوان اولین گام فراین دهای داده كاوی یاد می شود كه قبل از سایر فرایند ها برای شناسایی گروهی از ركوردهای مرتبط با هم كه بعدًا بتوانند نقطه آغاز تحلیلها باشند بر روی ركوردها اعمال می شود.
هدف از خوشه بندی این است که داده های موجود را به چند گروه تقسیم کنند و در این تقسیم بندی داده های گروه های مختلف باید حداکثر تفاوت ممکن را به هم داشته باشند و داده های موجود در یک گروه باید بسیار به هم شبیه باشند .
برخلاف کلاس بندی (که در ادامه خواهیم دید) در خوشه بندی ، گروه ها از قبل مشخص نمی باشند و همچنین معلوم نیست که بر حسب کدام خصوصیات گروه بندی صورت می گیرد. درنتیجه پس از انجام خوشه بندی باید یک فرد خبره خوشه های ایجاد شده را تفسیر کند و در بعضی مواقع لازم است که پس از بررسی خوشه ها بعضی از پارامترهایی که در خوشه بندی در نظر گرفته شده اند ولی بی ربط بوده یا اهمیت چندانی ندارند حذف شده و جریان خوشه بندی از اول صورت گیرد
پس از اینکه داده ها به چند گروه منطقی و توجیه پذیر تقسیم شدند از این تقسیم بندی می توان برای کسب اطلاعات در مورد داده ها یا تقسیم داده ها جدید استفاده کنیم.از مهمترین الگوریتم هایی که برای خوشه بندی استفاده می شوند می توان Kohnen و الگوریتم K-means را نام برد
طبقه بندی
طبقه بندی در واقع ارزشیابی ویژگیهای مجموعه ای از داد ه ها و سپس اختصاص دادن آ نها به مجموعه ای از گرو ههای از پیش تعریف شده است. این متداولترین قابلیت داده كاوی می باشد. داده كاوی را می توان با استفاده از داده های تاریخی برای تولید یك مدل یا نمایی از یك گروه بر اساس ویژگی های داده ها به كار برد. سپس می توان از این مدل تعریف شده برای طبقه بندی مجموعه داده های جدید استفاده كرد. همچنین می توان با تعیین نمایی كه با آن سازگار است برای پیش بینی های آتی ازآنبهرهگرفت.
برای مثال، برای طبقه بندی تخلفات و كلاهبرداری ها در صنعت و اعتبارات، با استفاده از قابلیت طبقه بندی داده كاوی، سیستم با استفاده از مجموعه ای از پیش تعریف شده از داده ها، تعلیم می بیند. مجموعه داد ه های مورد استفاده در این نمونه باید هم شامل مجموعه هایی از داد ه های معتبر باشند و هم شامل مجموعه هایی از داد ه های جعلی. از آن جا كه این داده ها از پیش تعریف شده هستند، سیستم پارامترهایی را می یابد كه می توان از آ نها برای تشخیص طبقه بندی های متمایز استفاده كرد. بعد از تعیین پارامترها سیستم از آ نها برای طبقه بندی های بعدی بهره خواهد گرفت.
در واقع سیستم هایی كه بر اساس طبقه بندی داده كاوی می كنند، دو مجموعه ورودی دارند: یك مجموعه آموزشی كه در آن داده هایی كه به طور پیش فرض در دسته های مختلفی قرار دارند، همراه با ساختار دسته بندی خود وارد سیستم می شوند و سیستم بر اساس آ نها به خود آموزش می دهد یا به عبارتی پارامترهای دسته بندی را برای خود مهیا می كند. دسته دیگر از ورودی هایی هستند كه پس از مرحله آموزش وبرای تعیین دستهوارد سیستم می شوند.
تكنیك های داده كاوی كه برای دسته بندی به كار می آیند عمومًا شامل تكنیك های شبكه عصبی و درخت تصمیم گیری هستند.
یكی از متغیرهای مهم در قابلیت دسته بندی برآورد یا امتیاز دهی است. هر جا طبقه بندی یك پاسخ دو تایی مثل بله و خیر ارائه كند، برآورد یك درجه بندی مثل پایین بالا و یا متوسط ارائه می كند. در اصل برآورد، چندین نما درامتداد مجموعه ای از داده ها فراهم می آورد كه نشان دهنده درجه تعلق یك نما به یك مجموعه است.
كاربرد قابلیت طبقه بندی در بازاریابی هدف، تصویب اعتبار و بررسی تقلب، است.
مسائل طبقه بندی به شناسایی خصوصیاتی منجر می شوند كه مشخص می نمایند هر مورد به كدام گروه تعلق دارد.این الگو هم می تواند برای فهم داده موجود و هم برای پیش بینی اینکه هر نمونه جدید چگونه کار می کند استفاده شود. برای مثال شما ممکن است بخواهید پیش بینی کنید که آیا اشخاص برای پاسخگویی به درخواست یک میل مستقیم که ممکن است به یک دستگاه تلفن با مسافت زیاد آسیب برساند می توانند گروه بندی شوند یا برای یک عمل جراحی باید گروه بندی شوند.
داده کاوی مدلهای طبقه بندی را بوسیله امتحان کردن داده طبقه بندی شده(موارد) و نهایتا یافتن یک الگوی پیش گو ایجاد می کند. این موارد موجود می تواند از یك پایگاه داده تاریخی ناشی شود مانند اطلاعات افرادی كه تحت معالجه دارویی خاصی هستند و یا به سمت یك خدمت با مسافت دور جذب شده اند.یا اینكه از تجربه هایی كه طی آن یك نمونه از تمام پایگاه داده در جهان واقعی تست شده باشد و نتایج آن برای ایجاد یك گروه بند استفاده شده باشند منتج شود. برای مثال یك نمونه از لیستی از پیامها به عنوان پیشنهاد فرستاده خواهد شد و نتایج پیام رسانی برای ساخت یك مدل طبقه بندی جهت بكار گرفته شدن در تمام پایگاه داده استفاده خواهد شد.
روش‌های خوشه‌بندی
روش‌های خوشه‌بندی را می‌توان از چندین جنبه تقسیم‌بندی کرد:
1- خوشه‌بندی انحصاری (Exclusive or Hard Clustering) و خوشه‌بندی با هم‌پوشی (Overlapping or Soft Clustering)
در روش خوشه‌بندی انحصاری پس از خوشه‌بندی هر داده دقیقأ به یک خوشه تعلق می‌گیرد مانند روش خوشه‌بندی K-Means. ولی در خوشه‌بندی با همپوشی پس از خوشه‌بندی به هر داده یک درجه تعلق بازاء هر خوشه نسبت داده می‌شود. به عبارتی یک داده می‌تواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونه‌ای از آن خوشه‌بندی فازی است.
2- خوشه‌بندی سلسله مراتبی (Hierarchical) و خوشه‌بندی مسطح(Flat)
در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی نسبت داده می‌شود. مانند روش Single Link. ولی در خوشه‌بندی مسطح تمامی خوشه‌های نهایی دارای یک میزان عمومیت هستند مانند K-Means. به ساختار سلسله مراتبی حاصل از روشهای خوشه‌بندی سلسله مراتبی دندوگرام (Dendogram) گفته می‌شود.
با توجه با اینکه روش‌های خوشه‌بندی سلسله مراتبی اطلاعات بیشتر و دقیق‌تری تولید می‌کنند برای تحلیل داده‌های با جزئیات پیشنهاد می‌شوند ولی از طرفی چون پیچیدگی محاسباتی بالایی دارند برای مجموعه داده‌های بزرگ روش‌های خوشه‌بندی مسطح پیشنهاد می‌شوند.
خوشه‌بندی در مقابل طبقه‌‌بندی
در طبقه‌بندی هر داده به یک طبقه (کلاس) از پیشین مشخص شده تخصیص می‌یابد ولی در خوشه‌بندی هیچ اطلاعی از کلاسهای موجود درون داده‌ها وجود ندارد و به عبارتی خود خوشه‌ها نیز از داده‌ها استخراج می‌شوند.
روشهای خوشه‌بندی سلسله مراتبی
همان گونه که بیان شد، در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی، معمولا به صورت درختی نسبت داده می‌شود. به ا ین درخت سلسله مراتبی دندوگرام (dendogram) می‌گویند. روش کار تکنیکهای خوشه‌بندی سلسله‌مراتبی معمولا بر اساس الگوریتمهای حریصانه (Greedy Algorithms) و بهینگی مرحله‌ای (stepwise-optimal) است. روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها معمولا به دو دستة زیر تقسیم می‌شوند:
بالا به پایین (Top-Down) یا تقسیم کننده (Divisive): در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هایی شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند.
پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative): در این روش ابتدا هر داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر با یکدیگر ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندیسلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود. که در بخشهای بعد به تشریح هر یک پرداخته خواهد شد.
نمونه‌ای از روش خوشه‌بندی سلسله مراتبی و تفاوت بین روشهای بالا به پایین و پایین
به بالا در شکل زیر مشاهده می‌شود.


تفاوت بین روشهای بالا به پایین با روشهای پایین به بالا

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!