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

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

دسته بندی

در الگوریتم های دسته بندی مجموعه داده اولیه به دو مجموعهداده با عنوان « مجموعه داده های آموزشی » و « مجموعه داده های آزمایشی » تقسیم میشود، با استفاده از مجموعه داده های آموزشی مدل ساخته می شود و از مجموعه داده هایآزمایشی برای اعتبار سنجی و محاسبه دقت مدل ساخته شده استفاده می شود. هر رکوردشامل یک مجموعه از ویژگی هاست. یکی از این ویژگی ها، ویژگی دسته نامیده می شود. درالگوریتم های دسته بندی چون ویژگی دسته مربوط به هر رکورد مشخص است بنابراین جزءالگوریتم های با ناظر محسوب می شوند. الگوریتم های با ناظر شامل دو مرحله با عنوانمرحله آموزش ( یادگیری ) و مرحله ارزیابی هستند (صنیعی, محمودی, & طاهرپور, 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 از قبل مشخص است. ایده مهمی که سبب شده است در بسیاریاز مسائل خوشه بندی کارایی الگوریتم FuzzyC – Meansنسبت به الگوریتم K – Means کاملا برترباشد، در نوع نگاهی است که این الگوریتم به مفهوم خوشه و اعضای آن دارد (شیرازی, 1389).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

چکیده :

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

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

چکیده :

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

منابع

Bishop.(2006). PatteRrcognition and Machine Leaing. New York: University Press.

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

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

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

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

مدیریت فناوری اطلاعات...