خوشه بندی و دسته بندی در داده کاوی

تفاوت های دسته بندی و خوشه بندی؛ و در چه زمانی از این دو عملکرد استفاده می شود؟

دسته بندی

در الگوریتم های دسته بندی مجموعه داده اولیه به دو مجموعه داده با عنوان « مجموعه داده های آموزشی » و « مجموعه داده های آزمایشی » تقسیم می شود، با استفاده از مجموعه داده های آموزشی مدل ساخته می شود و از مجموعه داده های آزمایشی برای اعتبار سنجی و محاسبه دقت مدل ساخته شده استفاده می شود. هر رکورد شامل یک مجموعه از ویژگی هاست. یکی از این ویژگی ها، ویژگی دسته نامیده می شود. در الگوریتم های دسته بندی چون ویژگی دسته مربوط به هر رکورد مشخص است بنابراین جزء الگوریتم های با ناظر محسوب می شوند. الگوریتم های با ناظر شامل دو مرحله با عنوان مرحله آموزش ( یادگیری ) و مرحله ارزیابی هستند (صنیعی, محمودی, & طاهرپور, 1394).

خوشه بندی

در مسائل خوشه بندی یک مجموعه رکورد داریم که هر کدام یک مجموعه از ویژگی ها را دارا هستند. یک معیار مشابهت میان آنها تعریف می کنیم. این معیار مشابهت در مسائل مختلف متفاوت است. به عنوان مثال اگر ویژگی ها پیوسته باشند می توان فاصله اقلیدسی را به عنوان معیار مشابهت در نظر گرفت. به این ترتیب هر رکورد را به صورت یک نقطه در فضای چند بعدی در نظر می گیریم. هر بعد، نماینده یکی از ویژگی های مسئله است. در مسائل خوشه بندی هیچ گونه دسته خاصی وجود ندارد. در واقع ویژگی دسته نداریم و فقط بر اساس معیار شباهت گروه بندی و خوشه بندی داده ها صورت می پذیرد. خوشه بندی به این شکل انجام می شود که رکورد هایی که بیشترین شباهت را به یکدیگر دارند ( با توجه به معیار شباهت تعریف شده ) در یک خوشه قرار می گیرند. در نتیجه داده های موجود در خوشه های متفاوت کمترین شباهت را به یکدیگر خواهند داشت. از آنجایی که برای الگوریتم های خوشه بندی ویژگی دسته تعریف نمی شود و رکوردها برچسب خاصی ندارند، بنابراین جزء الگوریتم های بدون ناظر محسوب می شوند. خروجی الگوریتم های خوشه بندی دوباره تحلیل خواهد شد تا در صورت امکان نظمی در خوشه ها آشکار شود. نکته مهمی که می بایست به آن توجه نمود آن است که خوشه بندی همیشه بر اساس ویژگی های ورودی نمونه ها انجام می شود. هدف در همه ی الگوریتم های خوشه بندی کمینه کردن « فاصله درون خوشه ای » و بیشینه نمودن « فاصله بین خوشه ای » می باشد. عملکرد خوب یک الگوریتم خوشه بندی زمانی محرز می شود که تا حد امکان خوشه ها را از یکدیگر دورتر کند ( یعنی رکورد های موجود در خوشه های مختلف کمترین شباهت را با یکدیگر داشته باشند ) و به علاوه رکوردهای موجود در یک خوشه بیشترین شباهت را به یکدیگر دارا باشند (Kumar, Steinbach, & Tan, 2006).

چنان چه بخواهیم خوشه بندی را در مقابل دسته بندی مورد مقایسه قرار دهیم می بایست عنوان نماییم که در دسته بندی هر داده به یک طبقه ( دسته ) از پیش مشخص شده تخصیص می یابد ولی در خوشه بندی هیچ اطلاعی از خوشه وجود ندارد و به عبارتی خود خوشه ها نیز از داده ها استخراج می شوند. در دسته بندی مفهوم دسته در یک حقیقت خارجی نهفته است حال آنکه مفهوم خوشه در نهان فواصل میان رکوردها است (صنیعی, محمودی, & طاهرپور, 1394).

به صورت اختصاصی الگوریتم های مرتبط با هر کدام را نام ببرید و شرح دهید؟

انواع گوناگون الگوریتم های دسته بندی را می توان به صورت ذیل بر شمرد :

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

· روش های مبتنی بر قانون : دسته بندی های مبتنی بر قانون، دسته بندی هایی هستند که دانش خروجی خود را به صورت یک مجموعه از قوانین اگر – آنگاه نشان می دهند. هر قانون یک بخش LHS ( بخش شرایط ) و یک بخش RHS ( بخش نتیجه ) دارد. این دو بخش به شکل گیری قانون کمک می کنند.

· استدلال مبتنی بر حافظه : استدلال مبتنی بر حافظه روشی است که در دسته بندی های « تاخیری » مورد استفاده قرار می گیرد. دسته بندی های تاخیری به دسته بندی هایی گفته می شود که مرحله یادگیری مدل در آنها به صورت مستقل وجود ندارند و در واقع مدلی را یاد نمی گیرند. در این دسته بندی ها کل مجموعه رکورد های آموزشی ذخیره خواهند شد. هنگامی که یک رکورد جدیدی با دسته نا مشخص وارد می شود، این رکورد به تمام رکوردهای موجود نشان داده شده و فاصله این رکورد با تمام رکوردها محاسبه می شود.

· الگوریتم مبتنی بر نظریه بیز : دسته بندی مبتنی بر رابطه نظریه بیز یا همان Naïve Bayes از یک چارچوب احتمالی برای حل مسائل دسته بندی استفاده می کند.

· شبکه های عصبی : شبکه های عصبی یکی از روش های ساخت دسته بند هستند که در آنها مدل یاد گرفته شده به صورت مجموعه ای از گره های به هم متصل به همراه ارتباطات وزن دار آنها نشان داده می شود. از شبکه های عصبی به وفور برای طراحی دسته بند های جعبه سیاه استفاده می شود. منظور از بکار گیری عبارت جعبه سیاه این است که در دسته بندهای مبتنی بر شبکه های عصبی امکان تفسیر دانش خروجی به هیچ وجه وجود ندارد. به عبارت بهتر هرگز نمی توان دانش مستتر کشف شده در شبکه های عصبی را به صورت شفاف مشاهده نمود. دقیقا بر عکس دسته بندهای مبتنی بر درخت و قانون که روش هایی کاملا قابل تفسیر هستند.

· ماشین بردار پشتیبان : استفاده از بردارهای پشتیبان خطی در مسائل دسته بندی، رویکرد جدیدی است که در چند ساله اخیر مورد توجه بسیاری قرار گرفته است. ماشین بردار پشتیبان در ابتدا توسط واپنیک در سال 1990 طراحی شد و نظریه آماری یادگیری را به صورت مستحکمی بنا نهاد. ماشین بردار پشتیبان دارای خواص : « طراحی دسته بندی کننده با حداکثر تعمیم » - « رسیدن به بهینه سراسری تابع هزینه » - « تعیین خودکار ساختار و توپولوژی بهینه برای طبقه بندی کننده » - « مدل کردن توابع تمایز غیر خطی با استفاده از هسته های غیر خطی و مفهوم حاصل ضرب داخلی در فضاهای هیلبرت » . رویکرد SVM به این صورت است که در مرحله آموزش، سعی دارد که « مرز تصمیم گیری » را به گونه ای انتخاب نماید که حداقل فاصله آن با هر یک از دسته های مورد نظر را بیشینه کند. این نوع انتخاب باعث می شود که تصمیم گیری ما در عمل، شرایط نویزی را به خوبی تحمل نموده و همچنین پاسخ دهی مناسبی داشته باشد. این نحو انتخاب مرز بر اساس نقاطی به نام بردارهای پشتیبان انجام می شود. الگوریتم های مبتنی بر ماشین های بردار پشتیبان الگوریتم هایی هستند که سعی می کنند یک حاشیه را بیشینه کنند (Bishop, 2006).

برخی از کاربردهای خوشه بندی :

1- بازاریابی

2- زیست شناسی

3- کتابداری

4- نقشه برداری شهری

5- مطالعات زلزله نگاری

6- وب

7- تشخیص گفتار

8- تقسیم بندی تصاویر (اسماعیلی, 1391).

انواع خوشه ها با توجه به شکل نهایی :

· خوشه های به خوبی جدا شده

· خوشه های مبتنی بر مرکز

· خوشه های مجاورتی

· خوشه های تراکمی

· خوشه های مفهومی

· خوشه های مبتنی بر تابع هدف (اسماعیلی, 1391).

الگوریتم های خوشه بندی :

1- خوشه بندی افرازی : تقسیم مجموعه داده به زیر مجموعه های بدون هم پوشانی به گونه ای که هر داده دقیقا در یک زیر مجموعه قرار داشته باشد.

2- خوشه بندی سلسله مراتبی : یک مجموعه از خوشه ها تودرتو را به شکل درخت های سلسله مراتبی در پایان عملیات خوشه بندی شاهد خواهیم بود.

3- خوشه بندی مبتنی بر چگالی : تقسیم مجموعه داده به زیر مجموعه هایی که چگالی و چگونگی توزیع رکوردها در آنها لحاظ شود.

4- الگوریتم خوشه بندی K – Means : یکی از ساده ترین و البته مشهورترین الگوریتم های « یادگیری بدون نظارت » است. این الگوریتم از روش خوشه بندی افرازی استفاده می کند. ایده اصلی در این الگوریتم تعریف K مرکز برای هریک از خوشه ها است. بهترین انتخاب برای مراکز خوشه ها در الگوریتم K – Means قرار دادن آنها ( مراکز ) در فاصله هر چه بیشتر از یکدیگر است.

5- الگوریتم خوشه بندی K – Medoids : الگوریتم خوشه بندی K – Medoids برای حل یکی از مشکلات الگوریتم K – Means پیشنهاد شده است. این الگوریتم به جای کمینه نمودن مجموع مجذور اقلیدسی فاصله بین نقاط ( که معمولا به عنوان تابع هدف در الگوریتم K – Means مورد استفاده قرار می گیرد ) ، مجموع تفاوت های فواصل جفت نقاط را کمینه می کند.

6- الگوریتم خوشه بندی Bisecting K – Means : الگوریتم خوشه بندی Bisecting K – Means یک گسترش مستقیم از الگوریتم پایه K – Means می باشد. ایده اصلی این الگوریتم بدین شرح است : برای بدست آوردن K خوشه ، ابتدا کل نقاط را به شکل یک خوشه در نظر می گیریم. در ادامه مجموعه ی نقاط تنها خوشه موجود را به دو خوشه تقسیم می کنیم. پس از آن یکی از خوشه های به دست آمده را برای شکسته شدن انتخاب می کنیم. سپس تا زمانی که K خوشه را به دست بیاوریم روال مذکور را ادامه می دهیم.

7- الگوریتم خوشه بندی Fuzzy C – Means : در این الگوریتم تعداد خوشه ها برابر C بوده و همانند الگوریتم K – Means از قبل مشخص است. ایده مهمی که سبب شده است در بسیاری از مسائل خوشه بندی کارایی الگوریتم Fuzzy C – Means نسبت به الگوریتم K – Means کاملا برتر باشد، در نوع نگاهی است که این الگوریتم به مفهوم خوشه و اعضای آن دارد (شیرازی, 1389).

چه استفاده هایی از این دو عملکرد در مدیریت سازمان ها شده است؟

عنوان انگلیسی مقاله: Web Log Clustering Approaches – A Survey

عنوان فارسی مقاله: روش های خوشه بندی لاگ های وب سرور(وب لاگ) یک بررسی.

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

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

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

آیا می توانید در سازمانی که در آن مشغول بکار هستید این نوع عملکردها را در نظر بگیرید و اجرا کنید؟ چه دستاوردی برای مدیریت سازمان خواهد داشت؟

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

چه نوع سوالات پژوهشی را می توان همراستا با خوشه بندی و دسته بندی توصیف کرد؟ به عبارتی شما چگونه میتوانید سوالاتی پژوهشی مرتبط با این دو عملکرد در نظر بگیرید؟

· خوشه بندی دانشجویان در رسته مختلف پروازی

· خوشه بندی دانشجویان در تایپ های مختلف پروازی

· خوشه بندی دانشجویان در انتخاب نوع پرنده بالگرد یا بال ثابت

دو نمونه پژوهش (ترجیحا پایان نامه) که در آن از این دو عملکرد استفاده شده را ارائه دهید. شرح دهید به چ دلیلی پژوهشگر از رویکرد و تکنیک مزبوره استفاده کرده. آیا مقایسه ای بین روشهای مختلف انجام داده؟ چرا ارجحیت برای رویکرد و ابزار خود قائل شده؟

پایان نامه کامل الگوریتم و روش های خوشه بندی جریان داده

چکیده :

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

روشی جدید در خوشه بندی اطلاعات با استفاده از ترکیب الگوریتم K – Means

چکیده :

امروزه، خوشه بندی نقش مهی را در اغلب زمینههای تحقیقاتی مانند مهندسی، پزشکی، زیستشناسی، داده کاوی و… ایفا مینماید. در واقع خوشـه بندی به معنای تقسیم بندی بدون نظارت می باشد؛ با استفاده از آن دادهها به دستههایی که از نظر پارامـترهای مورد علاقه، شباهـت بیشتری به یکدیگر دارند، تقسـیم میگردند. یکی از روشهای معـروف در این زمینه k-means میباشد؛ که علی رغم وابستگی به شرایط اولیه وهمگرائی به نقاط بهیـــنه محلی، تعداد N داده را به k خوشه با سرعت بالا، دسته بندی مینماید. در این رساله جهت رفع مشکلات موجود از روش ترکیبی مبتنی بر الگوریتم رقابت کشــــورهای استعماری و k-means بهره گرفته خواهد شد؛ که علاوه بر رفع مشکلات ذکر شده، مستقل از تعداد متغیرها نیز خواهد بود. در این رساله به منظور اعتبارسنجی، روش پیشنهادی بر روی چندین داده متفاوت مشهور پیاده سازی میگردد و نتــایج با روشهای الگوریتم ژنتیک، مورچگان، اجتماع ذرات، جفت گیری زنبور عسل، آبکاری فولاد و k-means مقایسه خواهد گردید. توانایی بالا و مقاوم بودن این روش بر اساس نتایج مشهود خواهد بود.

منابع

Bishop. (2006). Pattern Rrcognition and Machine Learning. New York: University Press.

Kumar, Steinbach, & Tan. (2006). Introduction to Data Mining. Texas: WP CO.

اسماعیلی, م. (1391). انبار داده ها و داده کاوی. تهران: انتشارات سافت گذر.

شیرازی, م. (1389). داده کاوی : مفاهیم، روش ها و کاربرد ها. تهران: انتشارات دانشگاه خواجه نصیرالدین طوسی.

صنیعی, م., محمودی, س., & طاهرپور, م. (1394). داده کاوی کاربردی. تهران: انتشارات نیاز دانش.