مقاله داده کاوی و الگوریتمهای خوشه بندی (docx) 96 صفحه

دسته بندی : تحقیق

نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )

تعداد صفحات: 96 صفحه

قسمتی از متن Word (.docx) :

بسم الله الرحمن الرحيم داده کاوی و الگوریتم های خوشه بندی چکیده تحقیق پیش رو به داده‌کاوی و الگوریتم‌های خوشه‌بندی پرداخته است. داده‌کاوی فرایندی تکرارپذیر است که پیشرفت در آن با کاوش از طریق روش‌های خودکار یا دستی صورت می‌گیرد. به تعبیر بهتر داده‌کاوی تعامل همکاری بین انسان و کامپیوتر است.خوشه‌بندی یکی از بهترین روش‌هایی است که برای کار با داده‌ها ارائه شده است. خوشه‌بندی قابلیت ورود به فضای داده و تشخیص ساختارش را امکان‌پذیر می‌نماید. لذا به عنوان یکی از ایده آل‌ترین مکانیزم‌ها، برای کار با دنیای عظیم داده‌ها محسوب می‌شود.كاوش داده‌ها یكي از تكنيكهاي حائز اهميت رو به رشد معروف به داده‌کاوی اكتشافي مي‏باشد كه در علوم گوناگون مهندسي مختلف مورد استفاده قرار ميگيرد. تحليل داده‌ها زمينه مناسبي را براي بسياري از كاربردهاي محاسباتي فراهم آورده است. الگوریتم‌های خوشه بندي براي دستيابي به خلاصه سازي داده‌ها مورد استفاده و فرايند گروه بندي داده‌ها بر اساس شباهت ميان آنها مي باشد. خوشه بندي می‌تواند به عنوان يك مرحله پيش پردازش جهت استخراج كلاسهاي الگو براي دسته‌بندی همراه با ناظر در مراحل بعدي مورد استفاده قرار گيرد. در این پایان نامه مفاهیم اصلی داده کاوی و مراحل الگوریتم های خوشه بندی، شبکه‌های عصبی مصنوعی، الگوریتم‌های خطا در مربع برای خوشه‌بندی، الگوریتم EM خوشه بندی فازی و غیره مورد بحث و بررسی قرار می گیرد. کلمات کلیدی: داده‌کاوی- کلاسترینگ – الگوریتم خوشه‌بندی. فهرست مطالب TOC \o "1-3" \h \z \t "سبک1;1;سبک2;2;سبک3;3;سبک5;4" فصل اول: مقدمه 1-1- مقدمه PAGEREF _Toc8549449 \h 2 فصل دوم: تعاریف 2-1 تعاریف PAGEREF _Toc8549452 \h 7 2-2 ریشه‌های داده‌کاوی PAGEREF _Toc8549453 \h 10 2-3 فرآیند داده‌کاوی PAGEREF _Toc8549454 \h 10 2-4 انبارهای داده PAGEREF _Toc8549455 \h 10 2-5 الگوریتم کلاسترینگ PAGEREF _Toc8549456 \h 11 2-5-1 گامهاي اساسي در انجام کلاسترينگ PAGEREF _Toc8549457 \h 11 2-5-2 انواع کلاسترینگ PAGEREF _Toc8549458 \h 12 2-6 کاربردهای خوشه‌بندی PAGEREF _Toc8549459 \h 13 2-7 نتیجه‌گیری PAGEREF _Toc8549460 \h 14 فصل سوم: داده کاوی 3-1 داده کاوی PAGEREF _Toc8549463 \h 17 3-2 مفاهیم داده‌کاوی PAGEREF _Toc8549464 \h 18 3-3 ریشه‌های داده‌کاوی PAGEREF _Toc8549465 \h 23 3-4 فرآیند داده‌کاوی PAGEREF _Toc8549466 \h 26 3-4-1 بیان مسئله و فرموله کردن فرضیه PAGEREF _Toc8549467 \h 28 3-4-2 جمع‌آوری داده‌ها PAGEREF _Toc8549468 \h 28 3-4-3 پیش‌پردازش داده‌ها PAGEREF _Toc8549469 \h 29 3-4-4 برآورد و ارزیابی مدل PAGEREF _Toc8549470 \h 30 3-4-5 تفسیر مدل و رسیدن به نتایج PAGEREF _Toc8549471 \h 31 3-5 مجموعه‌های داده‌کاوی PAGEREF _Toc8549472 \h 32 3-6 انباره‌های داده PAGEREF _Toc8549473 \h 41 3-7 نتیجه‌گیری PAGEREF _Toc8549474 \h 48 فصل چهارم: الگوریتم‏های داده‏کاوی 4-1 الگوریتم کلاسترینگ PAGEREF _Toc8549477 \h 51 4-2 انواع الگوریتم کلاسترینگ PAGEREF _Toc8549478 \h 53 4-2-1 الگوریتم‌های کلاسترينگ ترتيبي: PAGEREF _Toc8549479 \h 53 4-3 منطق رتبه صفر PAGEREF _Toc8549480 \h 54 4-4 تخصیص منطق ریاضی PAGEREF _Toc8549481 \h 55 4-5 منطق رتبه اول PAGEREF _Toc8549482 \h 55 4-6 منطق رتبه دوم PAGEREF _Toc8549483 \h 56 4-7 جستجوی سراسری فاصله از تعمیم PAGEREF _Toc8549484 \h 57 4-8 آموزش بدون نظارت PAGEREF _Toc8549485 \h 59 4-9 قطعات و سیستمهای کار خوشه‌بندی PAGEREF _Toc8549486 \h 60 4-10 تعاریف و یادداشتی PAGEREF _Toc8549487 \h 62 4-11 نمایندگی الگو، انتخاب ویژگی و استخراج PAGEREF _Toc8549488 \h 63 4-12 معیارهای تشابه PAGEREF _Toc8549489 \h 64 4-13 تکنیکهای خوشه‌بندی PAGEREF _Toc8549490 \h 67 4-13-1 الگوریتم‌های خوشه‌بندی سلسله مراتبی PAGEREF _Toc8549491 \h 68 4-13-2 تک لینک الگوریتم خوشه‌بندی PAGEREF _Toc8549492 \h 69 4-13-3 الگوریتم خاصیت تراکم کامل لینک خوشه‌بندی PAGEREF _Toc8549493 \h 69 4-13-3-1 خاصیت تراکم الگوریتم خوشه‌بندی سلسله مراتبی PAGEREF _Toc8549494 \h 70 4-14 الگوریتم مرتب‌سازی PAGEREF _Toc8549495 \h 70 4-15 الگوریتم‌های خطا در مربع PAGEREF _Toc8549496 \h 71 4-15-1 مربع خطا در روش خوشه‌بندی PAGEREF _Toc8549497 \h 71 4-16 گراف - خوشه‌بندی تئوری PAGEREF _Toc8549498 \h 74 4-17 مخلوط حل و فصل و حالت طلب الگوریتم(Mixture-Resolving) PAGEREF _Toc8549499 \h 74 4-17-1 الگوریتم EM PAGEREF _Toc8549500 \h 75 4-18 خوشه‌بندی فازی PAGEREF _Toc8549501 \h 75 4-19 شبکه‌های عصبی مصنوعی برای خوشه‌بندی PAGEREF _Toc8549502 \h 77 4-20 روش‌های تکاملی برای خوشه‌بندی PAGEREF _Toc8549503 \h 77 4-21 جستجو بر اساس رویکردهای PAGEREF _Toc8549504 \h 80 4-22 خوشه‌بندی مفهومی PAGEREF _Toc8549505 \h 82 4-23 نتیجه‌گیری PAGEREF _Toc8549506 \h 85 فصل پنجم: نتایج و پیشنهادات 5-1 نتیجه‌گیری PAGEREF _Toc8549509 \h 88 5-2 پیشنهادات PAGEREF _Toc8549510 \h 89 مراجع PAGEREF _Toc8549511 \h 90 فهرست شکلها TOC \o "1-3" \h \z \t "سبک4;1" شکل 3-1 شکل کلی برای شناخت پارامتر PAGEREF _Toc8549567 \h 25 شکل 3-2 فرآیند داده کاوی PAGEREF _Toc8549568 \h 32 شکل 3-3 رشدمیزبان‌های اینترنت PAGEREF _Toc8549569 \h 34 شکل 3-4 نمایش جدولی یک مجموعه داده PAGEREF _Toc8549570 \h 38 شکل 3-5 PAGEREF _Toc8549571 \h 39 فصل اول مقدمه 1-1- مقدمه یکی از ویژگیهای کلیدی در بسیاری از ابتکارات مربوط به تأمین امنیت ملی، داده‌کاوی است. داده‌کاوی که به عنوان ابزاری برای کشف جرائم، ارزیابی میزان ریسک و فروش محصولات به کار می‌رود، در بر گیرنده ابزارهای تجزیه و تحلیل اطلاعات به منظور کشف الگوهای معتبر و ناشناخته در بین انبوهی از داده‌هاست. داده‌کاوی غالباً در زمینه تأمین امنیت ملی به منزله ابزاری برای شناسایی فعالیت‌های افراد خرابکار شامل جابه جایی پول و ارتباطات بین آنها و همچنین شناسایی و ردگیری خود آنها با برسی سوابق مربوط به مهاجرت و مسافرت‌هاست. داده‌کاوی پیشرفت قابل ملاحظه‌ای را در نوع ابزارهای تحلیل موجود نشان می‌دهد اما محدودیت‌هایی نیز دارد. یکی از این محدودیت‌ها این است که با وجود اینکه به آشکارسازی الگوها و روابط کمک می‌کند اما اطلاعاتی را درباره ارزش یا میزان اهمیت آنها به دست نمی‌دهد. دومین محدودیت آن این است که با وجود توانایی شناسایی روابط بین رفتارها و یا متغیرها لزوماً قادر به کشف روابط علت و معلولی نیست. موفقیت داده‌کاوی در گرو بهره‌گیری از کارشناسان فنی و تحلیل‌گران کار آزموده‌ای است که از توانایی کافی برای طبقه‏بندی تحلیل‌ها و تغییر آنها برخوردار هستند. بهره‌برداری از داده‌کاوی در دو بخش دولتی و خصوصی رو به گسترش است. صنایعی چون بانکداری، بیمه، بهداشت و بازاریابی آنرا عموماً برای کاهش هزینه‌ها، ارتقاء کیفی پژوهش‌ها و بالاتر بردن میزان فروش به کار می‌برند. کاربرد اصلی داده‌کاوی در بخش دولتی به عنوان ابزاری برای تشخیص جرائم بوده است اما امروزه دامنه بهره‌برداری از آن گسترش روزافزونی یافته و سنجش و بهینه‌سازی برنامه‌ها را نیز در بر می‌گیرد. بررسی برخی از برنامه‌های کاربردی مربوط به داده‌کاوی که برای تأمین امنیت ملی به کار می‌روند، نشان‌دهنده رشد قابل ملاحظه‌ای در رابطه با کمیت و دامنه داده‌هایی است که باید تجزیه و تحلیل شوند. توانایی‌های فنی در داده‌کاوی از اهمیت ویژه‌ای برخوردارند اما عوامل دیگری نیز مانند چگونگی پیاده‌سازی و نظارت ممکن است نتیجه کار را تحت تأثیر قرار دهند. یکی از این عوامل کیفیت داده‌هاست که بر میزان دقت و کامل بودن آن دلالت دارد. عامل دوم میزان سازگاری نرم‌افزار داده‌کاوی با بانکهای اطلاعاتی است که از سوی شرکت‌های متفاوتی عرضه می‌شوند عامل سومی که باید به آن اشاره کرد به بیراهه رفتن داده‌کاوی و بهره‌برداری از داده‌ها به منظوری است که در ابتدا با این نیت گردآوری نشده‌اند. حفظ حریم خصوصی افراد عامل دیگری است که باید به آن توجه داشت. اصولاً به پرسش‌های زیر در زمینه داده‌کاوی باید پاسخ داده شود: سازمانهای دولتی تا چه حدی مجاز به بهره‌برداری از داده‌ها هستند؟ آیا از داده‌ها در چارچوبی غیر متعارف بهره‌برداری می‌شود؟ کدام قوانین حفظ حریم خصوصی ممکن است به داده‌کاوی مربوط شوند؟ کاوش در داده‌ها بخشی بزرگ از سامانه‌های هوشمند است. سامانه‌های هوشمند زیر شاخه‌ایست بزرگ و پرکاربرد از زمینه علمی جدید و پهناور یادگیری ماشینی که خود زمینه‌ای‌ست در هوش مصنوعی. فرایند گروه گروه کردن مجموعه‌ای از اشیاء فیزیکی یا مجرد به صورت طبقه‌هایی از اشیاء مشابه هم را خوشه‌بندی می‌نامیم. با توجه به اندازه‌های گوناگون (و در اغلب کاربردها بسیار بزرگ و پیچیده) مجموعه‌های داده‌ها مقیاس‌پذیری الگوریتم‌های به کار رفته معیاری مهم در مفاهیم مربوط به کاوش در داده‌ها است. کاوش‌های ماشینی در متون حالتی خاص از زمینه عمومی‌تر کاوش در داده‌ها بوده، و به آن دسته از کاوش‌ها اطلاق می‌شود که در آن‌ها داده‌های مورد مطالعه از جنس متون نوشته شده به زبان‌های طبیعی انسانی باشد. در حال حاضر یک تغیر الگو از مدل‌سازی و تحلیل کلاسیک بر پایه اصول به مدل‌های در حال پیشرفت و تحلیل‌های مربوطه به طور مستقیم از داده‌ها وجود دارد. ما به تدریج با این واقعیت رشد کرده‌ایم که حجم عظیمی از داده‌ها وجود دارد که کامپیوترها، شبکه‌ها و در حقیقت تمام زندگی ما را فرا گرفته است. سازمان‌های دولتی مؤسسات علمی و تجاری، سرمایه هنگفتی را برای جمع‌آوری و ذخیره این داده‌ها اختصاص داده‌اند در عمل، دو هدف اصلی داده‌کاوی شامل پیش‌گویی و توصیف می‌باشد. پیش‌گویی شامل به کارگیری بعضی متغیرها یا فیلدها در مجموعه داده برای پیش‌گویی مقادیر ناشناخته یا آتی دیگر متغیرها می‌باشد. توصیف، از سوی دیگر بر روی یافتن الگوهای توصیف داده‌ها که توسط انسان‌ها قابل تفسیر هستند، تأکید دارد؛ بنابراین، می‌توان فعالیت‌های داده‌کاوی را در گروه زیر طبقه‌بندی نمود: 1. داده‌کاوی پیش‌گویانه که مدلی از سیستم را ارائه می‌دهد، توسط مجموعه داده‌های مشخصی توصیف می‌شود، یا 2. داده‌کاوی توصیفی که اطلاعات جدید و غیر بدیهی را بر اساس مجموعه داده‌های موجود ارائه می‌دهد. اهداف «پیش‌بینی» و «توصیف» با استفاده از روش و تکنیک‌های داده‌کاوی محقق می‌شود: طبقه‌بندی 2. رگرسیون 3. دسته‌بندی. 4. مختصر سازی. 5. مدلسازی وابستگی 6. تشخیص تغییر و انحراف. داده‌کاوی یکی از سریعترین زمینه‌های رشد در صنعت کامپیوتر است. زمانی که یک زمینه خاص و محدود مورد علاقه در رشته کامپیوتر یا آمار گشوده می‌شود، به سرعت پیشرفت و به سطح و جایگاه واقعی خود گسترش پیدا می‌کند. یکی از مهمترین توانایی‌های داده‌کاوی در دامنه وسیع متدولوژی‌ها و تکنیک‌های آن نمایان شده که می‌تواند برای میزبانی مجموعه مسائل مختلف نیز صادق باشد. در فصل اول پژوهش حاضر به تعاریف داده‌کاوی و کلاسترینگ پرداخته شده است. در فصل دوم فرایند داده‌کاوی و ریشه‌ها و اهداف آن و چگونگی مدل‌سازی بیان شده است. فصل سوم تحقیق به الگوریتم‌های کلاسترینگ (خوشه‌بندی) پرداخته است. فصل دوم تعاریف 2-1 تعاریف داده‌کاوی به بهره‌گیری از ابزارهای تجزیه و تحلیل داده‌ها به منظور کشف الگوها و روابط معتبری که تا کنون ناشناخته بوده‌اند اطلاق می‌شود. این ابزارها ممکن است مدلهای آماری، الگوریتم‌های ریاضی و روش‌های یادگیرنده باشند که کار این خود را به صورت خودکار و بر اساس تجربه‌ای که از طریق شبکه‌های عصبی یا درخت‌های تصمیم‌گیری‏ به دست می‌آورند بهبود می‌بخشد. داده‌کاوی منحصر به گردآوری و مدیریت داده‌ها نبوده و تجزیه و تحلیل اطلاعات و پیش‌بینی را نیز شامل می‌شود برنامه‌های کاربردی که با بررسی فایل‌های متن یا چند رسانه‌ای به کاوش داده‌ها می‌پردازند پارامترهای گوناگونی را در نظر می‌گیرد که عبارت‌اند از: رابطه: الگوهایی که بر اساس آن یک رویداد به دیگری مربوط می‌شود مثلاً خرید قلم به خرید کاغذ. ترتیب: الگویی که به تجزیه و تحلیل توالی رویدادها پرداخته و مشخص می‌کند کدام رویداد، رویدادهای دیگری را در پی دارد مثلاً تولد یک نوزاد و خرید پوشک. دسته‌بندی: شناسایی الگوهای جدید مثلاً همزمانی خرید چسب و پوشه خوشه‌بندی: کشف و مستندسازی مجموعه‌ای از حقایق ناشناخته مثلاً موقعیت جغرافیایی خرید محصولی با مارک خاص پیش‌بینی: کشف الگوهایی که بر اساس آنها پیش‌بینی قابل قبولی از رویدادهای آتی ارائه می‌شود، مثلاً رابطه عضویت در یک باشگاه ورزشی با شرکت در کلاسهای ورزشی. مصورسازی: مصورسازی داده‌ها یکی از قدرتمندترین و جذابترین روش‌های اکتشاف در داده‌ها می‌باشد. برنامه‌های کاربردی که در زمینه تجزیه و تحلیل اطلاعات به کار می‌روند از امکاناتی چون پرس و جوی ساخت یافته که در بسیاری از بانک‌های اطلاعاتی یافت می‌شود و از ابزارهای تجزیه و تحلیل آماری برخوردارند اما برنامه‌های مربوط به داده‌کاوی در عین برخورداری از این قابلیت‌ها از نظر نوع با آنها تفاوت دارند. بسیاری از ابزارهای ساده برای تجزیه و تحلیل داده‌ها روشی بر پایه راستی آزمایی را به کار می‌برند که در آن فرضیه‌ای بسط داده شده آنگاه داده‌ها برای تائید یا رد آن بررسی می‌شوند. به طور مثال ممکن است این نظریه مطرح شود که فردی که یک چکش خریده حتماً یک بسته میخ هم خواهد خرید. کارایی این روش به میزان خلاقیت کاربر برای ارائه فرضیه‌های متنوع و همچنین ساختار برنامه بکار رفته بستگی دارد. در مقابل در داده‌کاوی روشهایی برای کشف روابط بکار برده می‌شوند و به کمک الگوریتم‌هایی روابط چند بعدی بین داده‌ها تشخیص داده شده و آنهایی که یکتا یا رایج هستند شناسایی می‌شوند. به طور مثال در یک فروشگاه سخت‌افزار ممکن است بین خرید ابزار توسط مشتریان با تملک خانه شخصی یا نوع خودرو، سن، شغل، میزان درآمد یا فاصله محل اقامت آنها با فروشگاه رابطه‌ای برقرار شود. در نتیجه قابلیت‌های پیچیده‌اش برای موفقیت در تمرین داده‌کاوی دو مقدمه مهم است یکی فرمول واضحی از مشکل که قابل حل باشد و دیگری دسترسی به داده متناسب. بعضی از ناظران داده‌کاوی را مرحله‌ای در روند کشف دانش در پایگاه داده‌ها می‌دانند. (KDD) مراحل دیگری در روند KDD به صورت تساعدی شامل، پاکسازی داده، انتخاب داده انتقال داده، داده‌کاوی، الگوی ارزیابی، و عرضه دانش می‌باشد. بسیاری از پیشرفت‌ها در تکنولوژی و فرایندهای تجاری بر رشد علاقه‌مندی به داده‌کاوی در بخش‌های خصوصی و عمومی سهمی داشته‌اند. بعضی از این تغییرات شامل: رشد شبکه‌های کامپیوتری که در ارتباط برقرار کردن پایگاهها داده مورد استفاده قرار می‌گیرند. توسعه افزایش تکنیکهایی بر پایه جستجو مثل شبکه‌های عصبی و الگوریتم‌های پیشرفته. گسترش مدل محاسبه کلاینت سروری که به کاربران اجازه دسترسی به منابع داده‌های متمرکز شده را از روی دسک تاپ می‌دهد. و افزایش توانایی به تلفیق داده از منابع غیر متناجس به یک منبع قابل جستجو می‌باشد. علاوه بر پیشرفت ابزارهای مدیریت داده، افزایش قابلیت دسترسی به داده و کاهش نرخ نگهداری داده نقش ایفا می‌کند. در طول چند سال گذشته افزایش سریع جمع‌آوری و نگه‌داری حجم اطلاعات وجود داشته است. با پیشنهادهای برخی از ناظران مبنی بر آنکه کمیت داده‌های دنیا به طور تخمینی هر ساله دو برابر می‌گردد. در همین زمان هزینه ذخیره‌سازی داده‌ها بطور قابل‌توجهی از دلار برای هر مگابایت به پنی برای مگابایت کاهش پیدا کرده است. مطابق قدرت محاسبه‌ها در هر ۱۸ – ۲۴ ماه به دو برابر ارتقاء پیدا کرده است این در حالی است که هزینه قدرت محاسبه رو به کاهش است. داده کاو به طور معمول در دو حوزه خصوصی و عمومی افزایش پیدا کرده است. سازمانها داده‌کاوی را به عنوان ابزاری برای بازدید اطلاعات مشتریان کاهش تقلب و اتلاف و کمک به تحقیقات پزشکی استفاده می‌کنند. با اینهمه ازدیاد داده‌کاوی به طبع بعضی از پیاده‌سازی و پیامد اشتباه را هم دارد. اینها شامل نگرانی‌هایی در مورد کیفیت داده‌ای که تحلیل می‌گردد، توانایی کار گروهی پایگاه‌های داده و نرم‌افزارها بین ارگانها و تخطی‌های بالقوه به حریم شخصی می‌باشد. همچنین ملاحظاتی در مورد محدودیتهایی در داده‌کاوی در ارگان‌ها که کارشان تأثیر بر امنیت دارد، نادیده گرفته می‌شود. 2-2 ریشه‌های داده‌کاوی داده‌کاوی ریشه در آموزه‌های متنوعی از دو موضوع، آمار و یادگیری ماشین دارد. آمار، ریشه در ریاضیات دارد و بنابراین، تأکید بر روی دقت ریاضی بوده است. 2-3 فرآیند داده‌کاوی داده‌کاوی به فرآیند جست‌وجو و کشف مدل‌های گوناگون، مختصر سازی ها و اخذ مقادیر از مجموعه‌ای از داده‌های معلوم اطلاق می‌گردد. در اینجا کلمه و اصطلاح «فرآیند» بسیار مهم است. حتی در بعضی محیط‌های حرفه‌ای این نظر وجود دارد که داده‌کاوی شامل انتخاب و به کارگیری ابزار مبتنی بر کامپیوتر برای حل مسائل فعلی و به دست آوردن راه‌حلی به طور خودکار می‌باشد. 2-4 انبارهای داده یک انبار داده مجموعه‌ای از پایگاه داده‌های یکپارچه، موضوع گرا می‌باشد که به منظور حمایت از رویکرد پشتیبانی تصمیم (DSF) طراحی شده است به نحوی که هر واحد از داده‌ها به چند دقیقه از زمان وابسته هستند. 2-5 الگوریتم کلاسترینگ خوشه‌بندی، یافتن ساختاری در مجموعه‌ای از داده‌ها است که طبقه‌بندی نشده‌اند. به بیان دیگر می‌توان گفت که خوشه‌بندی قرار دادن داده‌ها در گروه‌هایی است که اعضای هر گروه از زاویه خاصی شبیه یکدیگرند. در نتیجه شباهت بین داده‌های درون هر خوشه حداکثر و شباهت بین داده‌های درون خوشه‌های متفاوت حداقل می‌باشد. معیار شباهت در اینجا، فاصله بوده یعنی نمونه‌هایی که به یکدیگر نزدیکترند در یک خوشه قرار می‌گیرند. به عنوان نمونه در خوشه‌بندی اسناد دوری و یا نزدیکی داده‌ها متناسب با تعداد کلمه‌های مشترکی که در دو سند وجود دارد و یا در خوشه‌بندی سبد خرید مشتریان، فاصله بر اساس شباهت خرید تعیین می‌شود. لذا محاسبه فاصله بین دو داده در خوشه‌بندی بسیار مهم می‌باشد؛ زیرا کیفیت نتایج نهایی را دستخوش تغیر قرار خواهد داد. در واقع کلاستر، يک مجموعه از داده‌هاست بطوريکه: داده‌هاي موجود در يک کلاستر شبيه يکديگر هستند. داده‌هاي موجود در کلاسترهاي مختلف به يکديگر شبيه نيستند. 2-5-1 گامهاي اساسي در انجام کلاسترينگ به منظور ايجاد کلاسترها (انجام عمل کلاسترينگ) اعمال زير بايد انجام شوند: 1. انتخاب ويژگي: خصوصيات بايد به طور مناسبي انتخاب شوند تا اکثر اطلاعات را کدگذاري کنند. 2. مقياس نزديکي: معياري است که ميزان شباهت و يا عدم شباهت دو بردار خصوصيت را مشخص می‌کند. تمام خصوصيات انتخاب شده بايد در محاسبه اين معيار شرکت کنند و هيچ خصوصيتي نبايد بر بقيه غلبه کند. به عنوان مثال فاصله اقليدسي يا فاصله منهتن. 3. ملاک دسته‌بندی: که در قسمتهاي بالا در مورد آن صحبت شده است. 4. الگوريتم کلاسترينگ: پس از اينکه ملاک دسته‌بندی و مقياس نزديکي انتخاب شدند در اين گام يک الگوريتم خاص جهت روشن کردن ساختار دسته‌بندی مجموعه داده انتخاب می‌شود. 5. اعتبار نتايج: زمانيکه نتايج کلاسترينگ بدست آمد بايد صحت و درستي آنها بررسي شوند. اين کار معمولاً بوسيله تست‌های مناسبي انجام می‌شود. 2-5-2 انواع کلاسترینگ الگوریتم‌های کلاسترينگ ترتيبي: (اين الگوریتم‌ها در ابتدا يک کلاستر تک توليد می‌کنند و روش‌هاي سريع و واضحي می‌باشند. در اکثر آنها بردارهاي خصوصيات به تعداد دفعات کمي و يا تنها يک بار به الگوريتم داده مي شوند.) الگوریتم خوشه‌بندی طیفی: (خوشه‌بندی طیفی به گروهی از تکنیک‌هایی که به ساختار همگن یک ماتریکس همسان مرتبط هستند، اشاره می‌کند، خوشه‌ها در این الگوریتم با استفاده از تقسیم‌بندی نقاط داده، توسط ماتریکس همسان (مشابه) تشکیل می شوند.) الگوریتم خوشه‌بندی بر مبنای شبکه: (الگوریتم شبکه ایی فضای اشیا را به تعداد محدودی از سلول‌هایی که یک ساختار شبکه ایی را تشکیل می‌دهند تبدیل می‌کند عملیاتی بر روی این شبکه‌ها صورت می‌گیرد.) الگوریتم خوشه‌بندی بر مبنای تراکم: (الگوریتم خوشه‌بندی متراکم به توسعه خوشه‌های داده شده می‌پردازد تاجائیکه تراکم در خوشه مجاور تا آستانه خاصی افزایش پیدا کند این الگوریتم برای رفع پارازیت (اختلال) در مجموعه داده‌ها مناسب است.) 2-6 کاربردهای خوشه‌بندی خوشه‌بندی در زمینه‌های متنوعی به کار گرفته شده است چنانچه در زیر تعدادی از کاربردهای موضوعی توضیح داده شده‌اند: 1- مهندسی (بینش محاسباتی، یادگیری ماشین، تشخیص الگو، مهندسی مکانیکی، مهندسی برق).  کاربردهای موضوعی  خوشه‌بندی در محدوده  مهندسی  از شناسایی  بیومتریک و شناسایی گفتار «در ساخت کتاب کد از بردارهای ویژگی، در تقسیم  کردن گفتار بر حسب گویندگان ان و یا فشرده‌سازی گفتار»تا تحلیل سیگنال رادار، خلاصه کردن اطلاعات و رفع پارازیت می‌باشد. 2 - علوم کامپیوتر. کاربردهای  خیلی  زیادی از خوشه‌بندی را در وب کاوی «دسته‌بندی اسناد و یا دسته‌بندی مشتریان به سایت‌ها»، تحلیل پایگاه داده فضایی، بازیابی اطلاعات، گرداوری مستندات متنی و پردازش تصویر «تقسیم‌بندی تصاویر پزشکی و یا ماهواره‌ای» مشاهده کرده‌ایم. 3 - علوم پزشکی  و زندگی (ژنتیک، زیست‌شناسی «دسته‌بندی حیوانات و گیاهان  از روی ویژگی‌های آن ها»، میکروب‌شناسی،  دیرین‌شناسی، روانپزشکی، درمانگاه، تکامل  نژادی،  آسیب‌شناسی).  این حوزه‌ها  در وهله  اول  شامل  کاربردهای  عمده خوشه‌بندی هستند و تا این که یکی از زمینه‌های اصلی  الگوریتم‌های خوشه‌بندی گردند ادامه پیدا می‌کنند.  کاربردهای مهم شامل تعریف طبقه‌بندی، شناسایی کارکرد پروتئین و ژن، تشخیص و درمان بیماری و ... می‌باشند. 4 - علوم زمین و ستاره‌شناسی (جغرافیا، زمین‌شناسی، دریافت متحرک).  خوشه‌بندی می‌تواند برای طبقه‌بندی کردن ستاره‌ها و سیارات، تحقیق در مورد ساختار زمین، تفکیک کردن مناطق و شهرها «دسته‌بندی خانه‌ها بر اساس نوع و موقعیت جغرافیایی ان ها»، و مطالعه سیستم‌های رودخانه و کوه‌ها، مطالعات زلزله‌نگاری «تشخیص مناطق حادثه‌ خیز بر اساس مشاهدات قبلی » به کار رود. 5 - علوم اجتماعی (جامعه‌شناسی، روان‌شناسی، انسان‌شناسی، کتابداری «دسته‌بندی کتاب‌ها»، آموزش و پرورش).  کاربردهای  جالب‌توجه ای  می‌تواند در تحلیل الگوی  رفتاری، شناسایی رابطه در میان خوشه‌های متفاوت، ساختار تاریخ تکاملی زبان‌ها، تحلیل  شبکه‌های اجتماعی، تشخیص باستان‌شناسی و طبقه‌بندی مصنوعی و مطالعه روان‌شناسی جنایی یافت شود. 6 - اقتصاد (بازاریابی، تجارت).  کاربردهایی  در شناسایی  الگوی  خرید و مشخصات خوشه‌بندی، گروه‌بندی شرکت‌ها، و تحلیل روند  ذخیره‌سازی، همه  از کاربرد  تحلیل خوشه‌بندی سودمند می‌گردند. ویژگی‌های الگوریتم‌های خوشه‌بندی مربوط  به داده‌کاوی شامل موارد زیراست: ─ قابلیت قیاس با پایگاه داده‌های بزرگ، ─ قابلیت کار با داده‌های با ابعاد زیاد، ─ قابلیت یافتن خوشه‌های با حالت غیرمعمول، ─ اداره کردن خوشه‌های پرت، ─ پیچیدگی زمانی (اغلب به سادگی از اصطلاح پیچیدگی استفاده می‌کنیم)، ─ وابستگی تنظیم داده‌ها، ─ تکیه بر دانش قبلی و پارامترهای تعریف شده کاربر، ─ قابلیت تفسیر و ترجمه نتایج 2-7 نتیجه‌گیری جامعه مبتنی بر اطلاعات را می‌توان به عنوان جامعه‌ای تعريف نمود که بخش غالب اجتماع به جای کارهای فيزيکی درگیر کارهای فکری هستند. در چنين جامعه‌ای بيشترين توجه به فعاليتهای اطلاعاتی از قبيل: فراهم آوری، پردازش، توليد، ثبت، انتقال، اشاعه و مديريت اطلاعات مبذول می‌گردد و بیشترین هزینه‌ها صرف فرايندهای اطلاعاتی می‌شود (cawkell، 1387). با گسترش سيستمهاي پايگاهي و حجم بالاي داده‌های ذخيره شده در اين سیستم‌ها، به ابزاري نيازاست تا بتوان اين داده‌ها را پردازش کرد و اطلاعات حاصل از آن را در اختيار کاربران قرار داد. معمولاً کاربران پس از طرح  فرضیه‌ای بر  اساس گزارشات مشاهده شده به اثبات يا رد آن می‌پردازند، در حالي که امروزه به روشهايي نیاز داریم كه به اصطلاح به کشف دانش(Knowledge Discovery) بپردازند يعني روشهائي كه با کمترين دخالت کاربر و به صورت خودکار الگوها و رابطه‌های منطقي را بيان نمايند. يکي از روشهاي بسيار مهمي كه با آن می‌توان الگوهاي مفيدي را در ميان داده‌ها تشخيص داد، داده‌کاوی است، اين روش كه با حداقل دخالت كاربران همراه است اطلاعاتي را در اختيار آنها و تحلیل‌گران قرار ميدهد تا بر اساس آنها تصميمات مهم و حياتي در سازمانشان اتخاذ نمايند. بايد توجه داشت که اصطلاح داده‌کاوی زماني به کار برده می‌شود که با حجم بزرگي از داده‌ها، در حد مگا يا ترابايت، مواجه باشيم. در تمامي منابع داده‌کاوی بر اين مطلب تأکید شده است. هر چه حجم داده‌ها بيشتر و روابط ميان آنها پیچیده‌تر باشد دسترسي به اطلاعات نهفته در ميان داده‌ها مشکلتر می‌شود و نقش داده‌کاوی به عنوان يکي از روشهاي کشف دانش، آشكارتر می‌گردد. داده‌کاوی از چندين رشته علمي بطور همزمان بهره ميبرد نظير: تكنولوژي پايگاه داده، هوش مصنوعي، شبکه‌های عصبي، آمار، سیستم‌هاي مبتني بر دانش، بازيابي اطلاعات و غیره. فصل سوم داده کاوی 3-1 داده کاوی در حالیکه محصولات داده‌کاوی ابزارهای قدرتمندی می‌باشند، اما در نوع کاربردی کافی نیستند. برای کسب موفقیت، داده‌کاوی نیازمند تحلیل‌گران حرفه‌ای و متخصصان ماهری می‌باشد که بتوانند ترکیب خروجی بوجود آمده را تحلیل و تفسیر نمایند. در نتیجه محدودیتهای داده‌کاوی مربوط به داده اولیه یا افراد است تا اینکه مربوط به تکنولوژی باشد. اگرچه داده‌کاوی به الگوهای مشخص و روابط آنها کمک می‌کند، اما برای کاربر اهمیت و ارزش این الگوها را بیان نمی‌کند. تصمیماتی از این قبیل بر عهده خود کاربر است. برای نمونه در ارزیابی صحت داده‌کاوی، برنامه کاربردی در تشخیص مظنونان تروریست طراحی شده که ممکن است این مدل به کمک اطلاعات موجود در مورد تروریستهای شناخته شده، آزمایش شود. با اینهمه در حالیکه ممکن است اطلاعات شخص بطور معین دوباره تصدیق گردد، که این مورد به این منظور نیست که برنامه مظنونی را که رفتارش به طور خاص از مدل اصلی منحرف شده را تشخیص بدهد. تشخیص رابطه بین رفتارها و یا متغیرها یکی دیگر از محدودیتهای داده‌کاوی می‌باشد که لزوماً روابط اتفاقی را تشخیص نمی‌دهد. برای مثال برنامه‌های کاربردی ممکن است الگوهای رفتاری را مشخص کند، مثل تمایل به خرید بلیط هواپیما درست قبل از حرکت که این موضوع به مشخصات درآمد، سطح تحصیلی و استفاده از اینترنت بستگی دارد. در حقیقت رفتارهای شخصی شامل شغل (نیاز به سفر در زمانی محدود) وضع خانوادگی (نیاز به مراقبت پزشکی برای مریض) یا تفریح (سود بردن از تخفیف دقایق پایانی برای دیدن مکان‌های جدید) ممکن است بر روی متغیری اضافه تأثیر بگذارد. 3-2 مفاهیم داده‌کاوی علوم مهندسی نوین بر پایه به کار گیری مدل‌های بنیادی اولیه برای تحلیل سیستم‌های فیزیکی، بیولوژی و اجتماعی استوار هستند. چنین رویکردی با یک مدل علمی بنیادی آغاز می‌شود مانند قوانین حرکت نیوتن یا معادلات ماکسول در الکترومغناطیس که بر اساس آنها کاربردهای گونانی در زمینه مهندسی مکانیک و مهندسی الکترونیک شکل می‌گیرد. در این روش، از داده‌های آزمایشی برای بازبینی مدل‌های بنیادی اولیه و برآورد برخی پارامترهایی که اندازه‌گیری آنها به طور مستقیم دشوار و گاهی اوقات غیر ممکن است، استفاده می‌شود. با این حال در بسیاری از زمینه‌های، اصول بنیادی اولیه ناشناخته بوده یا سیستم‌های تحت بررسی و مطالعه برای قرار گرفتن در قالب های ریاضی بسیار پیچیده هستند. با افزایش کاربرد کامپیوتر، مقدار زیادی از داده‌ها از طریق چنین سیستم‌هایی ایجاد می شوند. در صورت فقدان مدل‌های بنیادی اولیه، می‌توان از چنین داده‌هایی که به راحتی در دسترس هستند، برای برآورد و ایجاد مدل‌هایی با رابطه‌ای سودمند بین متغیرهای یک سیستم استفاده نمود (یعنی وابستگی‌های ورودی- خروجی مجهول و ناشناخته)؛ بنابراین، در حال حاضر یک تغیر الگو از مدل‌سازی و تحلیل کلاسیک بر پایه اصول به مدل‌های در حال پیشرفت و تحلیل‌های مربوطه به طور مستقیم از داده‌ها وجود دارد. ما به تدریج با این واقعیت رشد کرده‌ایم که حجم عظیمی از داده‌ها وجود دارد که کامپیوترها، شبکه‌ها و در حقیقت تمام زندگی ما را فرا گرفته است. سازمان‌های دولتی مؤسسات علمی و تجاری، سرمایه هنگفتی را برای جمع‌آوری و ذخیره این داده‌ها اختصاص داده‌اند. در حالی که در واقع، فقط مقدار کمی از این داده‌ها مورد استفاده قرار می‌گیرند؛ زیرا در بسیاری از موارد، حجم داده‌های لازم برای سازماندهی بسیار بالا بوده یا ساختار آنها برای تحلیل مؤثر و کارا، بسیار پیچیده است. به طور کلی، این مسئله چگونه اتفاق می‌افتد؟ دلیل اصلی این است که اغلب تلاش‌های اصلی برای ایجاد یک مجموعه داده بر روی موضوعاتی از قبیل کارآمدی ذخیره‌سازی متمرکز می شوند و در حقیقت هیچ‌گونه طرح یا برنامه‌ای برای اینکه در نهایت، داده‌ها چگونه استفاده و تحلیل می شوند، وجود ندارد. ضرورت درک مجموعه داده‌های بزرگ، پیچیده و اطلاعات کامل و غنی در زمینه تجارت، علوم و مهندسی کمابیش رایج است. در دنیای تجارت، داده‌های شرکت‌ها و مشتریان به عنوان یک سرمایه استراتژیک مطرح هستند. توانایی استخراج دانش و اطلاعات مفید موجود در این داده‌ها و امکان استفاده از این دانش در جهان رقابتی امروز بیش‌ازپیش حائز اهمیت است. به کل فرایند به کارگیری متدولوژی مبتنی بر کامپیوتر از جمله روش‌های جدید برای دریافت دانش و اطلاعات از داده‌ها راه داده‌کاوی می‌گویند. داده‌کاوی فرایندی تکرارپذیر است که پیشرفت در آن با کاوش از طریق روش‌های خودکار یا دستی صورت می‌گیرد. داده‌کاوی سودمندترین سناریوی تحلیلی اکتشافی است که در آن تصور و برداشت از پیش تعیین شده‌ای درباره نتیجه «قابل‌توجهی»که به دست می‌آید، وجود ندارد. در حقیقت داده‌کاوی، جست‌وجوی لازم برای یافتن اطلاعات کلی جدید، ارزشمند و غیر بدیهی از میان حجم زیاد داده‌ها می‌باشد. به تعبیر بهتر داده‌کاوی تعامل همکاری بین انسان و کامپیوتر است. بهترین نتایج از ایجاد تعادل بین دانش متخصصان در توصیف مسائل و اهداف با قابلیت‌های جست‌وجوی کامپیوتر به دست می‌آید. در عمل، دو هدف اصلی داده‌کاوی شامل پیش‌گویی و توصیف می‌باشد. پیش‌گویی شامل به کار گیری بعضی متغیرها یا فیلدها در مجموعه داده برای پیش‌گویی مقادیر ناشناخته یا آتی دیگر متغیرها می‌باشد. توصیف، از سوی دیگر بر روی یافتن الگوهای توصیف داده‌ها که توسط انسان‌ها قابل تفسیر هستند، تأکید دارد؛ بنابراین، می‌توان فعالیت‌های داده‌کاوی را در گروه زیر طبقه‌بندی نمود: 1. داده‌کاوی پیش‌گویانه که مدلی از سیستم را ارائه می‌دهد، توسط مجموعه داده‌های مشخصی توصیف می‌شود. 2. داده‌کاوی توصیفی که اطلاعات جدید و غیر بدیهی را بر اساس مجموعه داده‌های موجود ارائه می‌دهد. در طیف پیش‌بینی، انتهای کار و هدف کلی داده‌کاوی ایجاد مدلی است که بعنوان یک برنامه و کد اجرایی بتوان از آن برای طبقه‌بندی، پیش‌بینی، برآورد و دیگر اعمال مشابه استفاده نمود. از طرف دیگر در طیف توصیف، نهایت کار و هدف کلی به دست آوردن یک شناخت از سیستم‌های تجزیه و تحلیل شده توسط الگوها و روابط آشکار در مجموعه داده‌های بزرگ می‌باشد. اهمیت نسبی طیف «پیش‌بینی»و «توصیف» برای کاربردهای خاص داده‌کاوی می‌تواند به طور قابل ملاحظه‌ای متفاوت باشد. اهداف «پیش‌بینی» و «توصیف» با استفاده از روش و تکنیک‌های داده‌کاوی محقق می‌شود: طبقه‌بندی. شناخت کارکرد یادگیری پیشگویانه ای که یک قلم اطلاعاتی را در یکی از چندین گروه کلاس از پیش تعریف شده، طبقه‌بندی می‌کند. رگرسیون. شناخت کارکرد یادگیری پیشگویانه ای که یک قلم اطلاعاتی را به یک متغیر پیش‌بینی با مقدار واقعی نگاشت یا تبدیل می‌کند. دسته‌بندی. یک وظیفه توصیفی معمول که طی یک جستجو، مجموعه‌ای متناهی از گروه‌ها یا دسته‌ها را برای توصیف داده‌ها، تعیین می‌کند. مختصر سازی. یک وظیفه توصیفی اضافی که روشهایی را برای یافتن توصیف فشرده برای مجموعه‌ای (یا زیرمجموعه‌ای) از داده‌ها را در بر می‌گیرد. مدلسازی وابستگی. یافتن یک مدل محلی که وابستگی‌های مهم بین متغیرها یا بین مقادیر یک مشخصه در مجموعه داده‌ها یا در قسمتی از مجموعه داده‌ها را توصیف می‌کند. تشخیص تغییر و انحراف. پیدا کردن تغییرات مهم در مجموعه داده‌ها. یک روش رسمی‌تر با نمایش‌های گرافیکی اهداف و وظایف داده‌کاوی برای مجموعه داده‌های حجیم و پیچیده وجود دارد. طبقه‌بندی‌ها و تعاریف مقدماتی موجود که در اینجا مطرح می‌شود تنها برای ایجاد یک احساس در خواننده در مورد طیف گسترده مسائل و وظایفی است که ممکن است با به کار گیری تکنولوژی داده‌کاوی حل شود. موفقیت عملکرد داده‌کاوی شبیه حل یک معما یا یک پازل است. قطعات مجزای پازل به تنهایی ساختار پیچیده‌ای ندارند در عین حال بعنوان یک مجموعه می‌توانند سیستم‌های بسیار پیچیده‌ای را ایجاد کنند، زمانی که شما سعی می‌کنید که این مجموعه را از یکدیگر جدا کنید. احتمالاً حس بیهودگی پیدا می‌کنید و شروع به چسباندن قطعات به یکدیگر می‌کنید و معمولاً در تمام مراحل کار ناراحت و نگران خواهید بود اما زمانیکه یاد میگیرید چگونه با ابن قطعات کار کنید، می‌فهمید که این کار آنقدر که در ابتدا به نظر می‌آمد سخت نبوده و به همین ترتیب مقایسه مشابهی را می‌توان برای داده‌کاوی به کار برد. در ابتدا، طراحان فرآیند داده‌کاوی احتمالاً چیز زیادی در مورد منابع اصلی داده‌ها نمی‌دانستند. اگر انها از این فرآیند اطلاع می‌داشتند، به احتمال زیاد جذب اجرای داده‌کاوی نمی‌شدند. به طور جداگانه داده‌ها به نظر ساده، کامل و قابل توضیح می‌رسند؛ اما در مجموع آنها ظاهری جدید به خود می‌گیرند که مانند پازل درک آن سخت و دشوار است؛ بنابراین، طراح و تحلیل‌گر فرآیند داده‌کاوی به دانش حرفه‌ای کامل، فکر خلاق و تمایل به بررسی جنبه‌های متفاوت نیاز دارد. داده‌کاوی یکی از سریعترین زمینه‌های رشد در صنعت کامپیوتر است. زمانی که یک زمینه خاص و محدود مورد علاقه در رشته کامپیوتر یا آمار گشوده می‌شود، به سرعت پیشرفت و به سطح و جایگاه واقعی خود گسترش پیدا می‌کند. یکی از مهمترین توانایی‌های داده‌کاوی در دامنه وسیع متدولوژی‌ها و تکنیک‌های آن نمایان شده که می‌تواند برای میزبانی مجموعه مسائل مختلف نیز صادق باشد. نظر به اینکه داده‌کاوی یک فعالیت طبیعی است که بر روی مجموعه داده‌های حجیم و بزرگ اعمال می‌شود، یکی از بزرگترین بازارهای هدف، انبار جامع داده‌ها، مراکز داده اختصاصی و سیستم پشتیبانی تصمیم به دست آوردن تخصص‌هایی در صنایعی مانند خرده فروشی، تولید، مخابرات و ارتباطات، بهداشت عمومی، بیمه و حمل و نقل است. در مباحث تجاری از داده‌کاوی می‌توان برای ارائه روش‌های جدید خرید، استراتژی های سرمایه‌گذاری و تشخیص هزینه‏های غیرمجاز در سیستم حسابداری استفاده نمود. داده‌کاوی می‌تواند رقابت و بازده بازاریابی را بهبود بخشیده و درآمدها، حمایت و رضایت مشتریان را جلب کند. همچنین از تکنیک‌های داده‌کاوی می‌توان برای حل مشکلات فرآیند تجارت استفاده نمود که در حقیقت هدف، درک تقابل و ارتباط بین شیوه‌های کسب و کار و سازماندهی‌های لازم می‌باشد. بسیاری از مجریان قانون و واحدهای بازرسی ویژه که مأمور شناسایی فعالیت‌های کلاهبرداران و کشف روش‌های ارتکاب جرم هستند، به طور موفقیت‌آمیزی از فرایند داده‌کاوی استفاده و از مزیت نسبی آن بهره‌مند می شوند. برای مثال، این متدولوژی می‌تواند متخصصین و تحلیلگران را در تشخیص الگوهای بحران رفتاری در رابطه با مواد مخدر، معاملات و تراکنش‌های پول‌شویی، حرکات و فعالیت‌های گروه‌های آدمکشان زنجیره‌ای و شناسایی قاچاقچیان در نقاط مرزی یاری دهد. تکنیک‌های داده‌کاوی همچنین در مباحث مرتبط با مأموران اطلاعاتی توسط افرادی که بسیاری از منابع داده‌های بزرگ و حجیم را به عنوان بخشی از فعالیت‌های مربوط به امور امنیت ملی ذکر می‌کنند، مورد استفاده قرار می‌گیرند. 3-3 ریشه‌های داده‌کاوی با توجه به دیدگاه و توضیحات متفاوتی که نویسندگان در مورد داده‌کاوی، بیان می‌کنند توافق جهانی بر روی توصیف واحدی از داده‌کاوی و یا حتی آنچه داده‌کاوی ارائه می‌دهد، وجود ندارد. آیا داده‌کاوی شکلی از آمار است که با تئوری یادگیری همراه شده است و یا یک پدیده جدید و انقلاب علمی در این مباحث می‌باشد؟ به نظر می‌رسد اکثر مسائل داده‌کاوی و راه‌حل‌های متناظر با آن، ریشه در تحلیل داده‌های کلاسیک دارند. داده‌کاوی ریشه در آموزه‌های متنوعی از دو موضوع، آمار و یادگیری ماشین دارد. آمار، ریشه در ریاضیات دارد و بنابراین، تأکید بر روی دقت ریاضی بوده است. گرایش برای ایجاد و تثبیت مسئله‌ای که قبل از تست عملی آن در زمینه‌های تئوری محسوس و نمایان است. در مقابل سیستم یادگیری ماشین ریشه در کاربرد کامپیوتر دارد. این موضوع منجر به گرایش کاربردی جهت تست مسئله و چگونگی اجرای آن بدون در نظر گرفتن علت کارایی آن می‌شود. اگر یکی از تفاوت‌های اساسی بین شیوه‌های یادگیری ماشین و آماری در مبحث داده‌کاوی اهمیتی باشد که به ریاضیات و فرمول نویسی می‌دهند، تفاوت دیگر، تأکید متناسبی است که به مدل‌ها و الگوریتم‌ها داده می‌شود. علوم آماری جدید تقریباً به طور کامل، از ایده یک مدل نشأت می‌گیرد. این یک ساختار درخواستی با یک ساختار تقریبی می‌باشد که می‌تواند منجر به داده‌ها شود. یادگیری ماشین برخلاف تأکیدات آماری بر روی نمونه‌ها، تأکید بر روی الگوریتم دارد. پس جای تعجب است که در خیلی از مواقع کلمه «یادگیری»شامل مفهوم یک فرآیند یا یک الگوریتم ضمنی می‌باشد. اصول اساسی مدل‌سازی در داده‌کاوی همچنین ریشه در تئوری کنترل دارد که در ابتدا برای سیستم‌های مهندسی و فرایندهای صنعتی به کار می‌رفت. موضوع ایجاد یک مدل ریاضی برای یک سیستم ناشناخته و مجهول (که در واقع به همان سیستم هدف اشاره دارد)از طریق مشاهده دقیق زوج‌های داده‌ای ورودی- خروجی عموماً منجر به همان شناسایی سیستم می‌گردد. اهداف شناسایی سیستم متعدد هستند و از نقطه‌نظر داده‌کاوی مهمترین هدف سیستم، پیش‌بینی عملکرد آن و توضیح تقابل و ارتباط بین متغیرهای یک سیستم می‌باشد. شناخت سیستم عموماً دو مرحله از بالا به پایین را در برمی‌گیرد: 1. شناخت ساختار. در این مرحله، ما نیاز داریم تا دانش اولیه‌ای درباره سیستم هدف برای تعیین یک کلاس یا گروه از مدل‌هایی که طی جست‌وجو برای مناسب‌ترین مدل جمع‌آوری شده‌اند را فراهم کنیم. معمولاً این کلاس یا گروه از مدل‌ها به وسیله یک عنصر پارامتری (t،u)y =f نشان داده می شوند به نحوی که y خروجی مدل،u بردار ورودی و بالاخره t بردار پارامتر می‌باشد. تشخیص کاربرد f، بر مبنای مسئله بوده (مسئله گرا می‌باشد) و عملکرد آن به تجربه طراح، به علاوه قوانین طبیعی حاکم بر سیستم هدف بستگی دارد. 2. شناخت پارامتر. در مرحله دوم زمانی که ساختار مدل شناخته می‌شود، تمام آنچه که لازم است انجام گیرد، به کارگیری تکنیک‌های بهینه‌سازی برای تشخیص بردار پارامتر (f*،u) y*=f می‌باشد تا اینکه مدل به دست آمده بتواند سیستم را بطور مناسب توصیف کند. به طور کلی، شناخت سیستم یک فرایند یک مرحله‌ای نیست، لازم است که شناخت ساختار و شناخت پارامتر به طور مکرر و تکراری انجام شود تا این که یک مدل رضایت‌بخش ایجاد گردد. این فرآیند به صورت گرافیکی در شکل 2-1 مشخص شده است. مراحل نمونه در هر تکرار عبارتند از: تعیین و پارامتر بندی یک کلاس یا گروه از مدل‌های فرموله شده (ریاضی)، (t،u)y*=f که نشان‌دهنده سیستمی خواهد بود که باید مورد شناسایی قرار گیرد. انجام شناخت پارامتر به منظور انتخاب پارامترهایی که بهتربن و مناسب‌ترین انتخاب برای مجموعه داده‌های موجود هستند(تفاوت y-y* حداقل و جزئی است). اجرای آزمون‌های ارزیابی و اعتبار سنجی برای تعیین اینکه آیا مدل شناخته شده به درستی به یک مجموعه داده نا پیدا و مشاهده نشده پاسخ می‌دهد(این موضوع اغلب به عنوان تست، اعتبار سنجی یا بررسی مجموعه داده‌ها معرفی می‌شود). خاتمه فرآیند در زمانی که نتایج تست‌های ارزیابی رضایت‌بخش باشند. u y y*سیستم هدفی که باید شناسایی شود+ y*=f(u,t) مدل ریاضی∑ y- y*تکنیک های شناسایی شکل 3-1 شکل کلی برای شناخت پارامتر اگر ما هیچ شناخت قبلی و مقدماتی درباره سیستم هدف نداشته باشیم، آنگاه شناسایی ساختار کاری بس دشوار خواهد بود و ما مجبور خواهیم شد تا ساختار را از طریق روش آزمون و خطا انتخاب کنیم. در حالی که ما اطلاعات زیادی درباره ساختار اکثر سیستم‌های مهندسی و فرآیندهای صنعتی داریم، در اکثر سیستم‌های هدف که داده‌کاوی در آنها استفاده می‌شود، این ساختارها به طور کلی ناشناخته بود و یا آنقدر پیچیده هستند که به دست آوردن یک مدل ریاضی برای آنها غیر ممکن است؛ بنابراین، تکنیک‌های جدید برای شناخت پارامترها توسعه یافته و امروزه آنها قسمتی از طیف تکنیک‌های داده‌کاوی هستند. سرانجام، ما می‌توانیم بین دو اصطلاح «مدل» و «الگو» که در داده‌کاوی تعریف شده‌اند، تفاوت قائل شویم. در حقیقت، مدل یک ساختار «در مقیاس بزرگ» می‌باشد و شاید برای خلاصه کردن رابطه‌های بسیاری از مدل‌ها (گاهی همه مدل)در حالی که الگو یک ساختار محلی می‌باشد و در موارد و حالات معدودی یا در اندازه‌گیری یک‌یک منطقه کوچک از فضای داده رضایت‌بخش خواهد بود. همچنین باید در اینجا دقت شود که کلمه الگو زمانی که در مبحث شناسایی الگو به کار می‌رود، معنای متفاوتی نسبت به مبحث داده‌کاوی دارد. در مبحث شناسایی الگو، اصطلاح «الگو» به بردار اندازه‌گیری یک شی خاص که در واقع نقطه‌ای در فضای داده‌ها می‌باشد، اطلاق می‌گردد. برعکس در داده‌کاوی، الگو صرفا یک مدل محلی است. در این کتاب ما به بردارهای n بعدی داده‌ها به عنوان نمونه‌ها اشاره خواهیم نمود. 3-4 فرآیند داده‌کاوی بدون سعی خاصی برای پوشش همه روش‌های ممکن در دیدگاه‌های متفاوت درباره داده‌کاوی به عنوان یک نظم و آموزه، اجازه دهید که با یک تعریف به مقدار کافی جامع در خصوص داده‌کاوی بحث را شروع کنیم. تعریف: داده‌کاوی به فرآیند جست‌وجو و کشف مدل‌های گوناگون، مختصر سازی ها و اخذ مقادیر از مجموعه‌ای از داده‌های معلوم اطلاق می‌گردد. در اینجا کلمه و اصطلاح «فرآیند» بسیار مهم است. حتی در بعضی محیط‌های حرفه‌ای این نظر وجود دارد که داده‌کاوی شامل انتخاب و به کارگیری ابزار مبتنی بر کامپیوتر برای حل مسائل فعلی و به دست آوردن راه‌حلی به طور خودکار می‌باشد. این برداشت در حقیقت یک تصور اشتباه بر پایه آرمان‌گرایی تصنعی جهان است. البته دلایل زیادی برای این برداشت اشتباه وجود دارد. یکی از این دلایل این است که داده‌کاوی فقط مجموعه‌ای از ابزارهای ایزوله شده نیست بلکه هر کدام کاملاً از یکدیگر متفاوت بوده و به دنبال حل مسائل هستند. دلیل دوم در انطباق یک مسئله با یک تکنیک نهفته است. خیلی به ندرت این حالت وجود دارد که یک پرسش تحقیقی با دقت کافی، کاربرد ساده و منحصر به فرد، یک روش و تکنیک را بیان کند. در حقیقت در عمل چه روی می‌دهد که داده‌کاوی به یک فرآیند تکرارپذیر تبدیل می‌گردد. به طور دقیق‌تر ما داده‌ها را مطالعه می‌کنیم، آنها را با استفاده از بعضی تکنیک‌های تحلیلی بررسی و بالاخره به آنها از دیدگاه‌ها و زوایای دیگری توجه می‌کنیم. شاید انها را اصلاح کنیم و در این راستا لازم باشد کار را از ابتدا شروع و ابزار تحلیل داده دیگری را اعمال کنیم که حاصل همه اینها، شاید رسیدن به یک نتیجه جدید یا بهتر باشد. این فرآیند می‌تواند بارها و بارها تکرار شود. هر تکنیک برای بررسی جنبه‌های تا حدودی متفاوت داده‌ها استفاده می‌شود. مطرح کردن یک سؤال تااندازه‌ای متفاوت راجع به داده‌ها چیزی است که در اینجا اساساً به عنوان یک سفر اکتشافی که داده‌کاوی جدید را هیجان‌انگیز می‌سازد، توصیف می‌شود. با این وجود، داده‌کاوی یک کاربرد تصادفی از روشهای آماری، یادگیری ماشین و دیگر روشها و ابزارها نیست. همچنین داده‌کاوی یک قدم زنی تصادفی در فضای روشهای تحلیلی نمی‌تواند باشد، بلکه این مبحث و پدیده جدید، یک فرآیند تصمیم‌گیری با دقت برنامه‌ریزی شده می‌باشد که بسیار سودمند، امیدوارکننده مناسب بنظر می‌رسد. شناسایی مشکلات کاوش یا برآورد وابستگی‌ها از داده‌ها یا کلاً کاوش داده‌های جدید تنها قسمتی از شیوه‌های تجربی مورد استفاده دانشمندان، مهندسین و دیگر کسانی است که روش‌های استانداردی را برای کسب نتایج داده‌ها بکار می برند. روشهای تجربی معمول با مسائل داده‌کاوی منطبق شد و مراحل زیر را دربر می‌گیرد: 3-4-1 بیان مسئله و فرموله کردن فرضیه بیشتر مطالعات بر مبنای مدل‌سازی در زمینه کاربردی خاصی انجام می شوند. دانش و تجربه در حوزه‌ای خاص معمولاً به منظور ذکر یا بیان معنی‌دار مسئله ضروری است. متأسفانه بسیاری از مطالعات کاربردی به تأکید بر روی تکنیک‌های داده‌کاوی به قیمت بیان واضح مسئله تمایل دارند. در این مرحله، یک مدل‌ساز معمولاً یک سری از متغیرها را برای تابع وابستگی ناشناخته و مجهول و اگر ممکن باشد یک شکل کلی از این وابستگی را بعنوان پیش فرض اصلی مشخص می‌کند، در این مرحله برای یک مسئله یگانه ممکن است چندین فرضیه فرموله شده مطرح گردد. در مرحله اول آنچه نیاز است ترکیبی از تخصص یک زمینه کاربردی و یک مدل داده‌کاوی است. در عمل، آن به معنی یک تقابل نزدیک بین متخصص داده‌کاوی و متخصص کاربردی است. در کاربردهای موفق داده‌کاوی، این همکاری در مرحله اولیه متوقف نشده بلکه در کل فرآیند داده‌کاوی ادامه پیدا می‌کند. 3-4-2 جمع‌آوری داده‌ها این مرحله در ارتباط با چگونگی تولید و جمع‌آوری داده‌ها می‌باشد. به طور کلی، دو امکان متمایز وجود دارد. اولین امکان زمانی است که فرآیند تولید داده‌ها تحت کنترل یک متخصص (مدل‌ساز) می‌باشد. این روش به نام آزمون طراحی شده شناخته می‌شود. امکان دوم زمانی مطرح می‌شود که متخصص نمی‌تواند فرآیند تولید را تحت تأثیر قرار دهد. این روش به نام روش یا شیوه دیداری مطرح می‌شود. مشخصاً روش دیداری یعنی تولید داده‌های تصادفی که در بیشترین کاربردهای داده‌کاوی در نظر گرفته می‌شود. بطور کلی، بعد از اینکه داده‌ها جمع‌آوری شدند یا در فرآیند جمع‌آوری داده‌ها تااندازه‌ای قرار گرفتند، توزیع نمونه‌گیری کاملاً نامعلوم است. هرچند، درک این مطلب بسیار مهم است که چگونه جمع‌آوری داده‌ها، توزیع تئوریک (نظری) خود را تحت تأثیر قرار می‌دهند زیرا چنین دانش مقدماتی می‌تواند برای مدل‌سازی و سپس تفسیر نتایج، بسیار سودمند و مفید باشد. همچنین این اطمینان باید حاصل شود که داده‌های استفاده شده برای ارزیابی یک مدل و داده‌هایی که بعداً برای تست و به کارگیری آن مدل به کار می‌رود، از یک توزیع نمونه‌برداری مشابه و ناشناخته استفاده کنند. اگر چنین نباشد، مدل برآورد شده نمی‌تواند به طور موفقیت‌آمیزی در کاربرد نهایی نتایج مورد استفاده قرار گیرد. 3-4-3 پیش‌پردازش داده‌ها در روش و تنظیم دیداری، داده‌ها معمولاً از پایگاه داده‌های موجود در انبار داده‌ها و مرکز داده‌ها «جمع‌آوری» می‌شود. فرآیند پیش‌پردازش داده‌ها معمولاً شامل حداقل دو مرحله متداول می‌باشند: آشکارسازی (و حذف) داده‌های غیرعادی. داده‌های غیرمعمول یا غیرعادی در حقیقت مقادیر داده نامنطبق و غیرمرسوم هستند که با بیشترین مشاهدات سازگار نیستند. معمولاً داده‌های غیرعادی نتیجه سنجش خطاها، کد نویسی و ثبت خطاها بوده و گاهی اوقات نیز مقادیر طبیعی و غیرعادی هستند. چنین نمونه‌هایی غیرقابل ارائه می‌توانند بعداً مدل‌های ایجاد شده را کاملاً تحت تأثیر قرار دهند. در اینجا دو خط مشی در خصوص داده‌های غیرعادی وجود دارد: الف. تشخیص و حذف علمی داده‌های غیرعادی به عنوان بخشی از مرحله پیش‌پردازش، یا ب. توسعه روشهای قوی مدل‌سازی که به داده‌های غیرعادی و ناخواسته غیر حساس باشند. جنبه‌ها و ویژگی‌های مقیاس بندی، رمزگذاری و انتخاب. پیش‌پردازش داده‌ها شامل چندین مرحله است از جمله مقیاس بندی متغیر و انواع مختلف رمزگذاری. برای مثال یک مشخصه با دامنه [0,1] و دیگری با دامنه [-100,1000] دارای ارزش مشابهی در تکنیک اعمال شده نیستند. آنها همچنین بر روی نتایج نهایی داده‌کاوی به طور متفاوتی تأثیر خواهند گذاشت؛ بنابراین، توصیه می‌شود که آنها را مقیاس بندی نموده و برای تحلیل و بررسی بیشتر هر دو جنبه را به وزن یکسانی تبدیل کنیم. همچنین روش‌های رمزگذاری با تأکید بر کاربرد خاص، معمولاً کاهش ابعاد را از طریق ایجاد مشخصه‌های حاوی اطلاعات مفید در مقادیر کوچکتر برای مدل‌سازی ثانویه داده‌ها سبب می شوند. این دو گروه و کلاس از وظایف پیش‌پردازش تنها مثال‌های نمایشی از طیف بزرگ فعالیت‌های پیش‌پردازش در فرایند داده‌کاوی هستند. مراحل پیش‌پردازش داده‌ها نباید کاملاً مستقل از دیگر مراحل داده‌کاوی در نظر گرفته شود. در هر بار تکرار فرایند داده‌کاوی، تمام فعالیت‌ها با یکدیگر می‌توانند مجموعه داده‌های جدی و بهبود یافته‌ای را برای تکرارهای بعدی تعریف کنند. به طور کلی، یک روش پیش‌پردازش مناسب، نمایش بهینه‌ای را برای تکرارهای بعدی تعریف کنند. به طور کلی، یک روش پیش‌پردازش مناسب، نمایش بهینه‌ای را برای یک تکنیک داده‌کاوی از طریق یکپارچه‌سازی دانش قبلی و در قالب مقیاس بندی و رمزگذاری کاربردی خاص ارائه می‌دهد. پیش‌پردازش به لحاظ وظیفه مندی و تکنیک‌های متناظر آن به دو زیر گروه تقسیم می شوند: آماده‌سازی داده‌ها و کاهش ابعاد داده‌ها. 3-4-4 برآورد و ارزیابی مدل انتخاب و پیاده‌سازی تکنیک‌های مناسب داده‌کاوی کار اصلی این مرحله است. این فرآیند معمولاً چندان روشن و واضح نیست. معمولاً در عمل پیاده‌سازی آن مبتنی بر چندین مدل بوده و انتخاب بهترین آنها یک وظیفه و کار اضافی محسوب می‌گردد. 3-4-5 تفسیر مدل و رسیدن به نتایج در اکثر موارد، مدل‌های داده‌کاوی باید در تصمیم‌گیری مؤثر باشند؛ بنابراین، چنین مدل‌هایی برای اینکه مفید باشند، لازم است که قابل تفسیر و قابل فهم باشند زیرا انسان‌ها به احتمال زیاد و بر پایه مدل‌های پیچیده جعبه سیاه تصمیم‌گیری نمی‌کنند. توجه داشته باشید که اهداف درستی مدل و دقت تفسیر آن تا حدودی یک مسئله ضد و نقیض می‌باشد. معمولاً مدل‌های ساده بیشتر قابل تفسیر و قابل فهم هستند. در عین اینکه دقت کمتری دارند. از روش‌های جدید داده‌کاوی انتظار می‌رود که در استفاده از مدل‌های دارای ابعاد بزرگ نتایجی با دقت بالا ارائه دهند و مسئله تفسیر این مدل‌ها در عین مبهم بودن یک وظیفه مجزا و جداگانه است که با تکنیک‌های ویژه برای معتبر سازی نتایج در نظر گرفته می‌شود. مسلما صدها صفحه اطلاعات حاوی اعداد و ارقام مختلف برای یک کاربر چندان مفید فایده نبوده و مورد قبول او قرار نخواهد گرفت. همچنین کاربر نمی‌توان این نتایج را خلاصه و تفسیر نمود و از آنها برای یک تصمیم‌گیری موفق استفاده کند. اگرچه تأکید این کتاب بر روی مراحل 3 و 4 فرآیند داده‌کاوی است اما باید به این نکته اساسی توجه داشت که اینها فقط دو مرحله از یک فرآیند بسیار پیچیده هستند همه مراحل به طور مجزا و تمام فرآیند داده‌کاوی به عنوان یک کل، بسیار تکرارپذیر هستند. همان طور که در شکل 2-2 نشان داده شده است درک مناسب از کل فرآیند برای هر کاربرد موفق، مهم است بدون توجه به اینکه چه میزان روش داده‌کاوی به کار رفته در مرحله 4 توانمند است، اگر داده‌ها به درستی جمع‌آوری و پیش‌پردازش نشوند یا اگر فرمول مسئله معنی‌دار نباشد، مدل حاصل چنان معتبر نخواهد بود. جمع آوری داده هابیان مسأله انجام پردازش برآورد مدل(کاوش داده ها) تفسیر مدل و رسیدن به نتایج شکل 3-2 فرآیند داده کاوی 3-5 مجموعه‌های داده‌کاوی همانگونه که ما وارد عصر اطلاع‌رسانی دیجیتال می‌شویم، مسئله سرریزی و حجم زیاد داده‌ها همه جا پیش روی ماست. توانایی ما در تجزیه و تحلیل و درک مجموعه داده‌های انبوه یا همان داده‌های بزرگ به مراتب فراتر از توانایی ما در جمع‌آوری و ذخیره‌سازی داده‌ها می‌باشد. پایگاه داده‌های بزرگ اطلاعات دیجیتالی در همه جا موجود می‌باشد. داده‌ها از طرق مختلف دریافت می‏شوند از جمله از طریق دستگاه ثبت اطلاعات گیشه پرداخت پول فروشگاه محله شما، دستگاه خودپرداز، کارت‌های هوشمند سوابق پزشکی، کارت‌های تلفن و کاربرد بسیار زیاد اسناد دیجیتالی در پایگاه داده‌های کلان در ایجاد رکوردهای بایگانی. امروزه دانشمندان در سطح بالاتری از روند مکانیزه جمع‌آوری اطلاعات قرار دارند. آنها داده‌ها را از منابع مختلف دریافت می‌کنند، از ایستگاه‌های راه دور هوشمند تا کاوش میکروسکوپی جزئیات سلول‌ها. ابزار علمی به سادگی می‌توانند ترابایت داده را در مدت‌زمان کوتاهی تولید کنند و آنها را در کامپیوتر ذخیره نمایند. عصر اطلاع‌رسانی با گسترش اینترنت، رشد فزاینده‌ای را در منابع اطلاعاتی و نیز در واحدها و رسانه‌های ذخیره‌سازی ایجاد نموده است. در این رابطه یک مثال توصیفی در شکل 3-2 آورده شده است به نحوی که شما می‌توانید افزایش چشم‌گیر میزبان‌های اینتر نت را فقط در 3 سال اخیر مشاهده کنید. در این تصویر مشاهده می‌کنید که این ارقام مستقیماً متناسب با مقدار ذخیره شده در اینترنت می‌باشد. باید توجه داشت که یک شکاف عمیق بین قابلیت‌های جمع‌آوری داده‌ها و سازماندهی آن با توانایی برای تحلیل آن داده‌ها وجود دارد. سخت‌افزار جاری و فناوری بانک‌های اطلاعاتی، دسترسی و ذخیره‌سازی داده‌های قابل اطمینان، کم هزینه و کارا را امکان‌پذیر می‌کند. به هر حال اعم از اینکه زمینه یا مقوله مربوطه تجاری، پزشکی، علمی یا دولتی باشد، مجموعه داده‌ها در شکل خام و پرداخت نشده خودشان از ارزش کمی برخوردار هستند. آنچه که در حقیقت ارزشمند است، دانش و شناختی است که می‌تواند از داده‌ها نتیجه و مورد استفاده قرار گیرد. برای مثال پایگاه داده‌های بازاریابی یک شرکت کالاهای مصرفی ممکن است شناخت و دانش ارتباط بین فروش محصولات خاص و طبقه‌بندی جمعیتی را مشخص و ارائه دهد. این آگاهی و دانش می‌تواند برای معرفی فعالیت‌های جدید و سازمان یافته بازاریابی همراه با یک بازگشت سرمایه قابل پیش‌بینی علی رقم فعالیت‌های سازمان یافته غیر متمرکز مورد استفاده قرار گیرد. 16,000,000 شماره میزبان ها 400,000 سال200019881999 شکل 3-3 رشدمیزبان‌های اینترنت ریشه مسئله این است که اندازه و ابعاد داده‌ها برای تحلیل و بررسی غیر خودکار (دستی) یا حتی برای بعضی تحلیل‌های نیمه‌خودکار بر مبنای کامپیوتر بیش از اندازه بزرگ و حجیم هستند. یک دانشمند یا یک مدیر تجاری به طور مؤثری می‌تواند با چند صد یا چند هزار سند و رکورد اطلاعاتی کار کند. کاوش میلیون ها داده که هر کدام با ده‌ها و صدها ویژگی توصیف می شوند، خود موضوع و مقوله دیگری است. تصور کنید قرار است تحلیل و بررسی یک ترابایت داده که شامل تصاویر فضایی با وضوح بالا از اجرام آسمانی است، صورت گیرد (به عنوان مثال 23040 *23040 پیکسل در هر تصویر)یا به عنوان مثال پایگاه ژنتیکی انسان با بیلیون‌ها جزء و عنصر را در نظر بگیرید. از نظر تئوری «داده‌های حجیم و بزرگ» می‌توانند به نتایج قوی‌تری منجر شوند؛ اما عملاً مشکلات زیادی به وجود می‌آید. جامعه تجاری به خوبی از سرریزی و حجم زیاد اطلاعات امروز آگاه است و یک بررسی در همین مورد نشان می‌دهد که 61% از مدیران اعتقاد دارند که سرریزی اطلاعات در محل کارشان وجود دارد. 80% عقیده دارند که موقعیت فوق بدتر خواهد شد. بیش از 50% مدیران از داده‌ها در مراحل تصمیم‌گیری فعلی به واسطه سرریزی اطلاعات چشم‌پوشی می‌کنند. 84% از مدیران، این اطلاعات را برای آینده ذخیره می‌کنند و از آنها برای تحلیل‌های جاری استفاده نمی‌کنند. 60% عقیده دارند که هزینه جمع‌آوری اطلاعات سنگین‌تر از ارزش خود اطلاعات است. به عقیده شما راه‌حل چیست؟ برای پاسخ به این سؤال بیشتر تأمل کنید! بلی اما با توجه به نزدیک بودن این محدودیت‌ها تا چه مدتی شما می‌توانید به این کار ادامه دهید البته اگر شما توان مالی لازم را داشته باشید می‌توانید یک معاون استخدام کنید یا می‌توانید از داده‌ها چشم‌پوشی کنید در این صورت دیگر در بازار رقابتی نخواهی بود. تنها راه‌حل واقعی جایگزین کردن متدلوژی تحلیل و تفسیر داده‌های مرسوم و کلاسیک (هم غیر خودکار و هم مبتنی بر کامپیوتر) با یک تکنولوژی داده‌کاوی جدید است. در تئوری، بیشتر روش‌های داده‌کاوی باید با مجموعه داده‌های بزرگ متناسب و از آن ها استقبال کنند. مجموعه داده‌های بزرگ دارای این پتانسیل هستند که اطلاعات ارزشمندتری را نتیجه دهند. اگر داده‌کاوی، یک جست‌وجو در یک فضای ممکن باشد، پس مجموعه داده‌های بزرگ امکانات خیلی بیشتری را برای شمارش و برآورد پیشنهاد می‌کنند. پتانسیل لازم برای شمارش و جست‌وجوی افزایش یافته از طریق محدودیت‌های اجرایی متعادل می‌شود. علاوه بر پیچیدگی محاسباتی الگوریتم‌های داده‌کاوی که با مجموعه داده‌های بزرگ کار می‌کنند، جست‌وجوی فراگیرتری نیز ممکن است وجود داشته باشد که خطر پیدا کردن برخی از راه‌حل‌های با احتمال پایین را افزایش می‌دهند. این راه‌حل‌ها برای مجموعه داده‌های مشخص به خوبی ارزیابی می شوند ولی ممکن است انتظارات آتی را برآورده نکنند. در محیط‌های امروزی که بر اساس مفاهیم چند رسانه‌ای پایه‌ریزی شده و دارای یک ساختار اینترنتی عظیم می‌باشد، انواع متفاوتی از داده‌ها به طور دیجیتالی تولید و ذخیره می شوند. برای آماده‌سازی روش‌های داده‌کاوی مناسب، مجبور هستیم انواع اصلی و خصوصیات مجموعه داده‌ها را تحلیل و بررسی کنیم. اولین گام در این تحلیل، سیستماتیک کردن داده‌هاست این مسئله با در نظر گرفتن نمایش و کاربرد کامپیوتری آن داده‌ها صورت می‌گیرد. داده‌ها که در حقیقت منبعی برای یک فرآیند داده‌کاوی هستند می‌توانند به مباحثی چون داده‌های ساخت یافته، داده‌های نیمه ساخت یافته و داده‌های غیر ساخت یافته تقسیم می‌شود اکثر پایگاه‌های داده تجاری شامل داده‌های ساخت‌یافته‌ای هستند که خود حاوی فیلدها با مقادیر عددی و آلفا عددی می‌باشد در حالیکه پایگاه داده‌های علمی ممکن است شامل هر سه گروه یاد شده باشند. مثال‌ها و نمونه‌هایی که از داده‌های نیمه ساخت یافته می‌تواند شامل تصاویر الکترونیک اسناد تجاری، گزارشات پزشکی، خلاصه‌های اجرایی و اسناد راهنمای تعمیرات باشد. اکثر اسناد وب نیز در این تقسیم‌بندی قرار می‌گیرند. یک مثال از داده‌های غیر ساخت یافته می‌تواند تصاویر ضبط شده توسط یک دوربین مدار بسته در یک مرکز خرید بزرگ باشد. چنین داده‌های بصری و چند رسانه‌ای از رویدادها یا فرایندهای مورد علاقه عموماً به طور مداوم در حال گسترش است و البته این رویکرد به خاطر کاهش هزینه های سخت‌افزاری موردنیاز می‌باشد. این شکل از داده‌ها عموماً پردازش گسترده‌ای را برای استخراج و ایجاد ساختارهای لازم برای اطلاعات موجود در خود دارد. داده‌های ساخت یافته اغلب به همان داده‌های سنتی اشاره دارد. در حالیکه داده‌های نیمه ساخت یافته و غیر ساخت یافته در کنار هم به عنوان داده‌های غیر سنتی در نظر گرفته می‌شود(همچنین داده‌های چند رسانه‌ای نیز نامیده می شوند.) اکثر روش‌های فعلی داده‌کاوی و ابزار تجاری بر روی داده‌های سنتی اعمال می شوند. هر چند، توسعه ابزار داده‌کاوی برای داده‌های غیر سنتی همچنین واسطه‌هایی برای تبدیل آنها به قالب های ساخت یافته با سرعت بالایی روبه گسترش است. مدل استاندارد داده‌های ساخت یافته برای داده‌کاوی مجموعه‌ای از حالات مختلف می‌باشند. سنجش‌های بالقوه به نام «خصیصه‌ها» یا «ویژگی‌ها» مشخص می‌گردد. این خصیصه‌ها به طور یکنواخت در حالات مختلف مورد سنجش و اندازه‌گیری قرار می‌گیرد. معمولاً نمایش داده‌های ساخت یافته برای مسائل داده‌کاوی به شکل جدول یا در قالب یک تک رابطه ارائه می‌گردد (اصطلاح به کار رفته در پایگاه داده رابطه‌ای)به نحوی که ستون‌ها خصیصه‌های اشیای ذخیره شده در جدول و ردیف‌ها مقادیر این خصیصه‌ها برای نهادهای خاص هستند. یک نمایش گرافیکی ساده برای مجموعه داده‌ها و ویژگی‌های آن در شکل 2=4 ارائه شده است. در اصطلاحات و ادبیات مربوط به داده‌کاوی، ما معمولاً از اصطلاح نمونه یا حالات برای سطرها استفاده می‌کنیم. خیلی از انواع خصیصه‌ها (صفات یا متغیرها) یعنی فیلدها در رکوردهای داده ساخت یافته داده‌کاوی معمول و متداول هستند، تمام روش‌های داده‌کاوی به یک اندازه در تقابل با انواع مختلفی از خصیصه‌ها مناسب و مفید نیستند. نمونه هاخصیصه‌ها مقدار خصیصه برای نمونه مربوطه شکل 3-4 نمایش جدولی یک مجموعه داده چندین روش برای متمایز کردن خصیصه‌ها وجود دارد. یک روش جست‌وجو در یک خصیصه یا در یک شکل‌دهی فرآیند که اغلب برای آن از اصطلاح رایج «متغیر» استفاده می‌شود، این است که بررسی کنیم آیا آن یک متغیر مستقل یا متغیر وابسته می‌باشد یا خیر یعنی آیا آن متغیری است که مقادیرش وابسته به مقادیر دیگر متغیرهای ارائه شده در مجموعه داده‌ها است یا خیر؟ این یک شیوه مبتنی بر مدل است که متغیرها را دسته‌بندی می‌کند. تمام متغیرهای وابسته به عنوان خروجی سیستمی در نظر گرفته می شوند که ما برای آن مدلی را طراحی کردیم و متغیرهای مستقل ورودی سیستمی که در شکل 2-5 نمایش داده شده‌اند. سیستم Yx z شکل 3-5 برخی متغیرهای دیگر وجود دارند که بر روی عملکرد سیستم تأثیرگذار هستند، اما مقادیر متناظر آنها در یک مجموعه داده و در طی فرآیند مدل سازی، متغیر نیستند. دلایل متفاوتی در این خصوص وجود دارد. از پیچیدگی بالا و هزینه سنجش این خصیصه‌ها تا یک مدل‌ساز که قادر به درک اهمیت بعضی از فاکتورها و تأثیرات آن بر روی مدل نیستند. اینها معمولاً متغیرهای غیرقابل رؤیت (غیر مشهود)نامیده می شوند و مسلما دلیل اصلی بروز ابهام و ارزیابی در یک مدل هستند. کامپیوترهای امروزی و ابزارهای نرم‌افزار متناظر با آنها، پردازش مجموعه داده‌های میلیون ها نمونه و صدها خصیصه را پشتیبانی می‌کنند. مجموعه داده‌های بزرگ شامل داده‌هایی از نوع ترکیبی یک محیط مقدماتی خاص برای به کار گیری تکنیک‌های داده‌کاوی فراهم می‌کنند. زمانی که حجم زیادی از داده‌ها در یک کامپیوتر ذخیره می شوند، هیچ‌کس نمی‌تواند به تکنیک‌های داده‌کاوی بپردازد زیرا مسئله مهم کیفیت داده‌هاست که باید در ابتدا حل شوند. همچنین واضح است که یک تحلیل کیفیت دستی (غیر خودکار)در این مرحله امکان‌پذیر نمی‌باشد؛ بنابراین ارائه یک تحلیل کیفی از داده‌ها در مراحل آغازین فرایند داده‌کاوی لازم است و معمولاً این کار در مرحله پیش‌پردازش داده‌ها انجام می‌گیرد. کیفیت داده‌ها تأثیر بنیادی بر روی تصویر و برداشت سیستم داشته و مدل متناظری که تلویحاً توصیف شده است را مشخص می‌کند. کیفیت داده‌ها همچنین می‌تواند توانایی کاربران نهایی را در تصمیم‌گیری‌های آگاهانه خود محدود نماید. با به کار گیری تکنیک‌های داده‌کاوی، اگر داده‌ها از کیفیت پایینی برخوردار باشند، اعمال تغییرات کیفی اساسی در یک سازمان کار مشکل و دشواری خواهد بود. همچنین اعمال یک کاوش جدید و کامل در داده‌های علمی با کیفیت ضعیف تقریباً غیر ممکن خواهد بود. باید توجه داشت که مجموعه‌ای از شاخص‌ها برای کیفیت داده‌ها وجود دارد: داده‌ها باید دقیق باشند و تحلیلگر باید نام داده را بطور کامل بررسی کند که آیا به درستی نوشته شده‌اند یا خیر؟ همچنین باید مطمئن شود که آیا کد در بازه مربوطه می‌باشد و آیا مقدار آن کامل است و سایر موارد. داده‌ها باید طبق نوع آن ذخیره شوند. تحلیلگر باید مطمئن شود که مقادیر عددی در قالب کاراکتر نمایش داده نشوند و همچنین باید دقت شود که اعداد صحیح به صورت اعداد اعشاری ارائه نشوند. داده‌ها باید دارای جامعیت باشند. به هنگام رسانی‌ها نباید به واسطه اختلاف بین کاربران مختلف از دست برود. اگر داده‌ها بخشی از سیستم مدیریت پایگاه داده‌ها نباشند، فرایند نسخه پشتیبان و بازیابی باید انجام شود. داده‌ها باید سازگار باشند. شکل و محتوا بعد از ادغام و یکپارچگی مجموعه‌های بزرگ از منابع مختلف باید یکسان باشد. داده‌ها نباید زائد باشند. در عمل داده‌های زائد باید حداقل شوند و تکرار معقول باید کنترل شده و رکوردهای تکراری باید حذف شوند. داده‌ها باید به هنگام باشند بخش جزء زمانی داده‌ها باید به راحتی از روی داده‌ها تشخیص داده شود یا تلویحاً عملکرد و نوع ساختار آن مشخص شود. داده‌ها باید به راحتی قابل فهم باشند نامگذاری استاندارد یک ضرورت است ولی تنها وضعیت برای درک مناسب داده‌ها نیست. کاربر باید بداند که داده‌ها با چه دامنه و حوزه خاصی مطابقت دارد. مجموعه داده‌ها باید کامل باشد. از دست دادن داده‌ها که عملاً اتفاق می‌افتد، باید به حداقل برسد. از دست دادن داده‌ها سبب کاهش کیفیت یک مدل کلی می‌گردد؛ به عبارت دیگر، بعضی از تکنیک‌های داده‌کاوی برای حمایت از تحلیل مجموعه داده‌ها در عین از دست دادن مقادیر به قدر کافی قوی هستند. 3-6 انباره‌های داده اگرچه وجود یک انبار داده، پیش‌نیاز داده‌کاوی نیست ولی در عمل داده‌کاوی به خصوص برای بعضی از شرکت‌های بزرگ با داشتن دسترسی به یک انبار داده بسیار آسان‌تر می‌شود. هدف اصلی یک انبار داده افزایش «هوشمندی»در یک فرآیند تصمیم‌گیری و افزایش دانش افراد درگیر در این فرآیند می‌باشد. به عنوان مثال، توانایی انجام بازاریابی محصول با نگاهی چند بعدی، کار فروش محصول بر حسب منطقه، بر حسب نوع فروش، برحسب خصوصیات آماری مشتریان، موجب تلاش‌های بهتر، افزایش تولید یا تصمیمات جدید در ساخت و توزیع محصول می‌شود. باید توجه کنیم که اکثر شرکت‌ها با اطلاعات متوسط و کلی کار می‌کنند. شرکت‌های برتر و ممتاز با پرداختن به جزئیات خودشان را متمایز می‌کنند. آنها ممکن است نیاز داشته باشد تا داده‌ها را به راه‌های مختلف تقسیم و تجزیه نمایند تا درک عمیق‌تری را از سازمان خود به دست آورند و موجب پیشرفت ممکن گردند. برای نیل هدف به این اهداف و فرآیندها، کاربران باید بدانند که چه داده‌هایی وجود دارند، کجا قرار دارند و بالاخره چگونه می‌توان به آن دسترسی داشت. یک انبار داده برای افراد مختلف معانی متفاوتی دارد. بعضی از تعاریف محدود به داده‌ها هستند و بعضی از تعاریف نیز به افراد، فرآیندها، نرم‌افزار، ابزارها و داده‌ها بر می‌گردد. یکی از تعاریف کلی به شکل زیر است: یک انبار داده مجموعه‌ای از پایگاه داده‌های یکپارچه، موضوع گرا می‌باشد که به منظور حمایت از رویکرد پشتیبانی تصمیم (DSF) طراحی شده است به نحوی که هر واحد از داده‌ها به چند دقیقه از زمان وابسته هستند. بر اساس این تعریف یک انبار داده می‌تواند به عنوان مخزن داده‌های یک سازمان در نظر گرفته شود تا از تصمیم‌گیری‌های راهبردی حمایت کند. وظیفه انبار داده این است که داده‌های قدیمی یک سازمان را به روشی یکپارچه ذخیره نماید به نحوی که این امر نشان‌دهنده جنبه‌های مختلف یک سازمان یا یک کسب و کار باشد. داده‌ها در یک انبار هرگز به هنگام نمی‌شوند، اما فقط برای پاسخ به تقاضاهای کاربران نهایی که معمولاً تصمیم‌گیرنده نیز هستند، مورد استفاده قرار می‌گیرند و نوعاً انبار داده‌ها حجیم و بزرگ می‌باشند و می‌توانند بیلیون‌ها رکورد را ذخیره کنند اغلب به آنها مراکز داده‌ها گفته می‌شود. یک مرکز داده در حقیقت یک انبار داده می‌باشد که برای برآورد کردن نیازهای یک گروه خاص از کاربران طراحی شده و بسته به نوع زمینه کاری ممکن است بزرگ یا کوچک باشد. اکنون در مراحل اولیه تکامل انبار داده‌ها جای تعجب نیست اگر پروژه‌های زیادی را پیدا کنیم که به خاطر عدم درک اساسی در موارد این که یک انبار داده چیست، دچار اشتباه می شوند. آنچه که جای تعجب دارد اندازه و مقیاس این پروژه‌هاست. بسیاری از شرکت‌ها به این علت که تعریف دقیقی از یک انبار داده ندارند، دچار خطا می شوند. اینکه چه مشکلات شغلی را حل می‌کند و فواید آن مربوط به چه بخش‌هایی می‌باشد، دو جنبه از انبار داده‌ها برای درک بهتر از فرآیند طراحی آن بیشترین اهمیت را دارند: اولی شامل انواع مشخص (طبقه‌بندی)داده‌هایی که در انبار ذخیره می شوند و دومی ایجاد تغییر شکل‌هایی برای آماده‌سازی شکل نهایی داده‌ها به منظور تصمیم‌گیری می‌باشد. یک انبار داده شامل گروه‌های داده زیر می‌باشد. به نحوی که این گروه‌بندی یا طبقه‌بندی همراه با منابع داده وابسته به زمان می‌باشد: 1. داده‌های مفصل قدیمی 2. داده‌های مفصل فعلی (جدید) 3. داده‌های تااندازه‌ای خلاصه شده 4. داده‌های بسیار خلاصه 5. فراداده‌ها(راهنمای داده‌ها یا دفتر داده‌ها) برای آماده کردن این پنج نوع داده اولیه یا داده‌های مشتق شده در انبار داده‌ها، انواع بنیادی تبدیل یا تغییر شکل داده‌ها استاندارد شده‌اند. هرکدام از این نوع چهار نوع اصلی تبدیل یا تغییر شکل دارای ویژگی‌های خاص خود هستند: تغییر شکل ساده. این تغییر شکل یا تبدیل، بلوک‌های ساختاری همه تبدیل‌های پیچیده‌تر دیگر می‌باشند. این طبقه یا گروه شامل دستکاری داده‌هایی هستند که برای یک موضوع در یک زمان متمرکز می شوند(بدون در نظر گرفتن مقادیر آنها در فیلدهای مربوطه). مثال‌های این مورد شامل تغییر نوع داده‌های یک فیلد یا جایگزینی یک فیلد رمزگذاری شده با یک مقدار رمز گشایی شده می‌باشد. تمیز کردن و پاک‌سازی. این تبدیل‌ها یا تغییر شکل‌ها، فرمت بندی مداوم و کاربرد یک فیلد یا گروه مرتبطی از فیلدها را تضمین می‌کند. بعنوان مثال، این نوع تبدیل همچنین شامل وارسی‌هایی برای مقادیر مجاز در یک فیلد خاص می‌باشد(معمولاً وارسی و کنترل دامنه‌ها یا انتخاب از یک لیست شمارش شده). یکپارچگی. این یک فرآیند استفاده از داده‌های عملیاتی از یک یا چند منبع و نگاشت آنها فیلد به فیلد به ساختار داده‌های جدید در انبار داده‌ها می‌باشد. مشکل شناسه متداول، یکی از مشکل‌ترین موضوعات یکپارچگی در ایجاد و ساخت یک انبار داده‌ها می‌باشد. اساساً، این وضعیت زمانی اتفاق می‌افتد که چند منبع سیستمی برای نهادهای مشابه وجود دارند و هیچ‌گونه راه‌حل روشنی برای شناسایی این نهادها بعنوان نهاد واحد وجود ندارد. در حقیقت، این مسئله یک چالش و موضوع قابل‌توجه می‌باشد. در خیلی از مواقع این مشکل بصورت خودکار قابل حل نیست. در اینجا به ندرت به الگوریتم‌های پیچیده برای تشابهات احتمالی نیاز است. زمانیکه منابع متعددی برای یک داده وجود دارد، سناریوی پیچیده دیگری از ادغام داده‌ها مطرح میگردد. در دنیای واقعی، این یک مسئله معمول و مرسوم است که بعضی از مقادیر متضاد باشند و مسلما بر طرف کردن این تضادها یک فرآیند ساده نیست. درست همان قدر که داشتن داده‌های متضاد مشکل می‌باشد، به همان میزان هم نداشتم قدار برای یک عنصر داده در انبار داده‌ها نیز مشکل است. تمام مشکلات و راه‌حل‌های خودکار یا نیمه‌خودکار متناظر همراه وابسته به دامنه می‌باشند. متراکم سازی و خلاصه‌سازی. اینها روشهای متراکم سازی نمونه داده‌های موجود در محیط اجرایی هستند که به نمونه داده‌های کوچکتر در محیط انبار داده‌ها تبدیل می شوند. اگرچه اصطلاحات «متراکم سازی»و «خلاصه‌سازی» اغلب در این گونه مباحث به صورت یکسانی استفاده می شوند، ولی در اینجا معتقدیم که آنها معنی متفاوتی در بحث انبار داده‌ها دارند. در حقیقت «خلاصه‌سازی»، اضافه کردن ساده مقادیر در یک یا چند بعد از داده‌ها می‌باشد. به عنوان مثال، اضافه کردن فروش روزانه به فروش ماهانه یک محصول.«متراکم سازی » به اضافه کردن عناصر تجاری مختلف به یک مقدار کل اشاره دارد. این روش بسیار وابسته به دامنه می‌باشد. به عنوان مثال،«متراکم سازی» اضافه کردن فروش تولید روزانه و فروش مورد نظر بطور ماهانه برای بدست آوردن ترکیب کل ماهانه می‌باشد. این تبدیل یا تغییر شکل علت و دلیل اصلی است که یک انبار داده‌ها به عنوان یک منبع داده برای فرایند داده‌کاوی در نظر گرفته می‌شود. اگر انبار داده‌ها در دسترس باشد، مرحله پیش‌پردازش در داده‌کاوی بطور چشم‌گیری کاهش و گاهی اوقات حتی حذف می‌گردد. فراموش نکنید که این آماده‌سازی داده‌ها مرحله‌ایست که بیشترین زمان را به خود اختصاص می‌دهد. اگرچه ایجاد یک انبار داده یک کار پیچیده است و در بسیاری از متون با جزئیات بسیار توضیح داده شده اما در اینجا فقط مشخصات اصلی ان ارائه می‌شود. فرآیند سه مرحله‌ای توسعه انبار داده‌ها در مراحل اساسی زیر خلاصه می‌شود: 1. مدل‌سازی. به عبارت ساده، به صرف زمان لازم برای درک فرآیندهای تجاری، نیازمندیهای اطلاعات این فرآیندها و تصمیماتی که اخیراً در پی فرآیندها اتخاذ می‌شود، اطلاق می‌شود. 2. ساخت. به فراهم آوردن ابزار لازم جهت حمایت و انطباق بر انواع پشتیبانی‌های تصمیم برای فرآیند تجاری مورد هدف گفته می‌شود. ایجاد یک مدل داده برای تعیین نیازهای اطلاعاتی بیشتر، تجزیه مسائل مربوط به ویژگی‌ها و مشخصه‌های داده و انبار داده‌های واقعی که در نهایت و در شکل نهایی خود به ایجاد یک مرکز داده و انبار داده جامع می‌شود. 3. توسعه و فراگیری. به منظور پیاده‌سازی نسبتاً زود هنگام در کل فرایند طبیعت و ماهیت داده‌هایی که باید انبار شوند و ابزار هوشمند تجاری مختلف بررسی و مورد استفاده قرار می‌گیرد. مرحله توسعه بطور مشخص شامل زمانیست که کاربران هم منبع - برای درک داده‌هایی که در دسترس بودند یا باید در دسترس باشند) - و هم انبار داده‌های فعلی را کاوش می‌کنند. این مسئله می‌تواند سبب تکامل انبار داده‌هایی گردد که شامل اضافه کردن داده‌های بیشتر افزایش دوره‌های زمانی یا بازگشت به مرحله ساخت به منظور گسترش دامنه انبار داده‌ها از طریق یک مدل داده می‌باشد. داده‌کاوی یکی از کاربردهای اصلی برنامه انبار سازی داده‌ها می‌باشد، زیرا وظیفه اصلی یک انبار داده فراهم کردن اطلاعات برای کاربران نهایی به منظور پشتیبانی تصمیم می‌باشد. برخلاف دیگر ابزار تقاضا و سیستم‌های کاربردی، فرآیند داده‌کاوی برای یک کاربر نهایی ظرفیتی برای استخراج اطلاعات مخفی و غیر بدیهی ایجاد می‌کند. اگرچه استخراج چنین اطلاعاتی سخت و دشوار می‌باشد، ولی می‌تواند دستاوردهای تجاری و علمی بالاتری را فراهم کند و در حقیقت می‌توان «انبار سازی داده‌ها» و «داده‌کاوی» را بعنوان یک سرمایه‌گذاری مفید در نظر گرفت. در اینجا سؤال مهم که مطرح می‌گردد این است که چگونه داده‌کاوی با سایر کاربردهای خاص انبار داده‌ها از قبیل زبانهای تقاضا یا ساخت یافته (SQL)و ابزارهای پردازش تحلیلی بر خط (OLAP)که برای انبار داده‌ها بکار می‌روند، متفاوت است.SQL یک زبان استاندارد بانک اطلاعات رابطه‌ای است و برای تقاضاهایی مناسب است که برخی از انواع محدودیت‌ها را برای داده‌های بانک اطلاعاتی به منظور استخراج یک پاسخ مناسب اعمال می‌کند. در مقابل، روشهای داده‌کاوی برای تقاضاهایی مناسب هستند که ذاتاً اکتشافی هستند یعنی سعی در پیدا کردن داده‌های پنهان دارند نه داده‌های بسیار آشکار. لازم به یادآوری می‌باشد که SQL زمانی مناسب است که ما دقیقاً بدانیم که چه اطلاعاتی را جست‌وجو می‌کنیم و بتوانیم بطور رسمی انها را توصیف کنیم. مسلما ما زمانی از روشهای داده‌کاوی استفاده می‌کنیم که در آنچه که دنبال آن هستیم ابهام داشته باشیم؛ بنابراین، این دو گروه از کاربردهای انبار سازی داده‌ها مکمل هم هستند. در سالهای اخیر ابزارها و روشهای OLAP بسیار معمول و متداول شده‌اند بطوریکه به کاربران اجازه می‌دهند تا با ایجاد دیدگاه‌های چند گانه از داده‌ها که توسط نمایش‌های گرافیکی پیشرفته حمایت و پشتیبانی می‌شود، داده‌های لازم در یک انبار را تحلیل و بررسی کند. در این دیدگاه‌ها، ابعاد متفاوت داده‌ها با خصوصیات مختلف تجاری مطابقت دارند. ابزار OLAP مانند ابزار داده‌کاوی، نتایج را ارائه و از داده‌ها و شباهت بین آنها در اینجا استفاده می‌کنند. استخراج نتایج از داده‌ها در OLAP شبیه محاسبات در مبحث صفحه گسترده است، زیرا آنها از محاسبات ساده و از قبل آماده استفاده می‌کنند. همچنین ابزار OLAP از داده‌ها چیزی نمی‌آموزند و دانش جدیدی را نیز ایجاد نمی‌کنند. آنها معمولاً ابزار مجسم سازی با اهداف خاصی هستند که می‌توانند به کاربران نهایی در نتیجه‌گیری و تصمیم‌گیری بر اساس داده‌های فشرده گرافیکی کمک کنند. ابزار OLAP یک فرآیند داده‌کاوی بسیار سودمند و مفید هستند. البته آنها می‌توانند بخشی از فرآیند داده‌کاوی باشند اما نه جانشینی برای آن. 3-7 نتیجه‌گیری داده‌کاوی پل ارتباطی میان علم آمار، علم کامپیوتر، هوش مصنوعی، الگوشناسی، فراگیری ماشین و بازنمایی بصری داده می‌باشد. داده‌کاوی فرآیندی پیچیده جهت شناسایی الگوها و مدل‌های صحیح، جدید و به صورت بالقوه مفید، در حجم وسیعی از داده می‌باشد، به طریقی که این الگوها و مدلها برای انسانها قابل درک باشند. داده‌کاوی به صورت یک محصول قابل خریداری نمی‌باشد، بلکه یک رشته علمی و فرآیندی است که بایستی به صورت یک پروژه پیاده‌سازی شود. داده‌ها اغلب حجیم می‌باشند و به تنهایی قابل استفاده نیستند، بلکه دانش نهفته در داده‌ها قابل استفاده می‌باشد؛ بنابراین بهره‌گیری از قدرت فرآیند داده‌کاوی جهت شناسایی الگوها و مدلها و نیز ارتباط عناصر مختلف در پایگاه داده جهت کشف دانش نهفته در داده‌ها و نهایتاً تبدیل داده به اطلاعات، روزبه‌روز ضروری‌تر می‌شود. امروزه عملیات داده‌کاوی به صورت گسترده توسط تمامی شرکت‌هایی که مشتریان در کانون توجه آنها قرار دارند، استفاده می‌شود، از جمله فروشگاه‌ها، شرکت‌های مالی، ارتباطاتی، بازاریابی و غیره. استفاده از داده‌کاوی به این شرکتها کمک می‌کند تا ارتباط عوامل داخلی از جمله قیمت، محل قرارگیری محصولات، مهارت کارمندان را با عوامل خارجی از جمله وضعیت اقتصادی، رقابت در بازار و محل جغرافیایی مشتریان کشف نمایند. از آنجـائیـکه هـوش مصنوعی یکی از اصلی‌ترین  عنــاصـر داده‌کاوی می‌باشد و با توجه به اینکه به کمک سیستم‌های کامپیوتری و پایگاه‌های داده، روزانه به میزان داده‌ها افزوده می‌شود، بنابراین استفاده هوشمندانه از دانش بالقوه‌ای که در این داده نهفته است در دنیای رقابتی امروز برای شرکت‌ها حیاتی می‌باشد. داده‌کاوی پیش‌بینی وضع آینده بازار، گرایش مشتریان و شناخت سلیقه‌های عمومی آنها را برای شرکت‌ها ممکن می‌سازد. انـبـار داده  بـه مجموعه‌ای از داده‌ها گفـتـه می‌شود که از منابع مختلف اطلاعاتی سازمان جمع‌آوری، دسته‌بندی و ذخیره می‌شود. در واقع یک انبار داده مخزن اصلی کلیه داده‌های حال و گذشته یک سازمان می‌باشد که برای همیشه جهت انجام عملیات گزارش‌گیری و آنالیز در دسترس مدیران می‌باشد. انبارهای داده حاوی داده‌هایی هستند که به مرور زمان از سیستم‌های عملیاتی آنلاین سازمان استخراج می شوند، بنابراین سوابق کلیه اطلاعات و یا بخش عظیمی از آنها را می‌توان در انبار داده‌ها مشاهده نمود. از آنجائیکه انجام عملیات آماری و گزارشات پیچیده دارای بارکاری بسیار سنگینی برای سرورهای پایگاه داده می‌باشند، وجود انبار داده سبب می‌گردد که اینگونه عملیات تأثیری بر فعالیت برنامه‌های کاربردی سازمان نداشته باشد. همانگونه که پایگاه داده سیستمهای عملیاتی سازمان (برنامه‌های کاربردی) به گونه‌ای طراحی می شوند که انجام تغییر و حذف و اضافه داده به سرعت صورت پذیرد، در مقابل انبار داده‌ها دارای معماری ویژه‌ای می‌باشند که موجب تسریع انجام عملیات آماری و گزارش‌گیری می‌شود فصل چهارم الگوریتم‏های داده‏کاوی 4-1 الگوریتم کلاسترینگ کلاسترينگ به معناي کلاس‌بندی بدون نظارت است که کلاسها از قبل تعيين شده نيستند و يا به عبارت ديگر برچسب کلاس الگوهاي آموزشي در دسترس نيست. بنابراين اکنون هدف اصلي ما سازماندهي الگوها به گروهاي sensible است؛ که به ما اجازه می‌دهند که شباهت و تفاوت بين الگوها را کشف کنيم و نتايج مفيد را درباره آنها استنتاج نماييم. اين ايده در زمینه‌های مختلف ديده می‌شود. مثال زير از زیست‌شناسی الهام گرفته شده است و صورت مسئله را براي ما واضح می‌سازد. به حيوانات زير توجه کنيد: گوسفند، سگ و گربه (پستاندار)، گنجشک و بلبل (پرنده)، ماهي قرمز، شاه‌ماهی (ماهي)، افعي و مارمولک(خزنده) و غوک(دوزيست). به منظور مرتب کردن اين حيوانات در داخل کلاسترها نياز داريم که يک ملاک دسته‌بندی تعريف کنيم. اگر وجود شش‌ها را بررسي کنيم، ماهي قرمز و شاه‌ماهی در يک کلاستر و بقيه در يک کلاستر ديگر قرار می‌گیرند. اگر ملاک دسته‌بندی را محيطي که حيوانات زندگي می‌کنند قرار دهيم آنگاه گوسفند، سگ، گربه، گنجشک، بلبل، افعي و مارمولک (حيواناتي که بيرون آب زندگي می‌کنند) کلاستر اول و ماهي قرمز و شاه‌ماهی (حيواناتي که در آب زندگي می‌کنند) کلاستر دوم را تشکيل می‌دهند و غوک که می‌تواند هم در آب و هم در خشکي زندگي کند کلاستر سوم را تشکيل می‌دهد. اگر وجود ستون فقرات را ملاک دسته‌بندی باشد تمام حيوانات در يک دسته قرار می‌گیرند. ما می‌توانيم از ملاک دسته‌بندی مرکب استفاده کنيم. اين مثال نشان می‌دهد که فرايند نسبت دادن اشيا به کلاسترها ممکن است به نتايج بسيار متفاوتي منجر شود. کلاسترينگ يکي از ابتدایی‌ترین فعالیت‌های ذهني است که براي کنترل کردن مقادير زياد اطلاعات دريافت شده هر روزي استفاده می‌شود. پردازش هر بخش از اطلاعات به عنوان يک موجوديت تک امکان‌پذیر نيست. بنابراين انسانها به دسته‌بندی موجودیت‌ها (حوادث، انسانها، اشيا و غيره) در کلاسترها روي می‌آورند. هر کلاستر توسط خصوصيات مشترک موجودیت‌هايي که درون آن قرار می‌گیرند تعريف می‌شود. کلاستر، يک مجموعه از داده‌هاست بطوريکه: داده‌هاي موجود در يک کلاستر شبيه يکديگر هستند. داده‌هاي موجود در کلاسترهاي مختلف به يکديگر شبيه نيستند. کلاسترها انواع مختلفي دارند که در به زير تعدادي از آنها اشاره شده است: كلاسترهاي بخوبي جدا شده: مجموعه نقاط داخل اين كلاستر نسبت به نقاط خارج آن به يكديگر بسيار شبيهند. كلاسترهاي مبتني به مركز: مجموعه نقاط داخل اين كلاستر به مركز كلاستر نسبت به مراكز كلاسترهاي ديگر بسيار نزديكترند. كلاسترهاي مبتني بر مجاورت و نزديكي: مجموعه نقاط داخل اين كلاستر به يك يا تعداد بيشتري از نقاط داخل كلاستر نسبت به نقاط خارج آن شبيهند. گامهاي اساسي در انجام کلاسترينگ: به منظور ايجاد کلاسترها (انجام عمل کلاسترينگ) اعمال زير بايد انجام شوند: 1. انتخاب ويژگي: خصوصيات بايد به طور مناسبي انتخاب شوند تا اکثر اطلاعات را کدگذاري کنند. 2. مقياس نزديکي: معياري است که ميزان شباهت و يا عدم شباهت دو بردار خصوصيت را مشخص می‌کند. تمام خصوصيات انتخاب شده بايد در محاسبه اين معيار شرکت کنند و هيچ خصوصيتي نبايد بر بقيه غلبه کند. به عنوان مثال فاصله اقليدسي يا فاصله منهتن. 3. ملاک دسته‌بندی: که در قسمتهاي بالا در مورد آن صحبت شده است. 4. الگوريتم کلاسترينگ: پس از اينکه ملاک دسته‌بندی و مقياس نزديکي انتخاب شدند در اين گام يک الگوريتم خاص جهت روشن کردن ساختار دسته‌بندی مجموعه داده انتخاب می‌شود. 5. اعتبار نتايج: زمانيکه نتايج کلاسترينگ بدست آمد بايد صحت و درستي آنها بررسي شوند. اين کار معمولاً بوسيله تست‌های مناسبي انجام می‌شود. 4-2 انواع الگوریتم کلاسترینگ • الگوریتم‌های کلاسترينگ ترتيبي • الگوریتم‌های کلاسترينگ سلسله مراتبي • الگوریتم‌های کلاً سترينگ مبتني بر بهینه‌سازی تابع هزينه 4-2-1 الگوریتم‌های کلاسترينگ ترتيبي: اين الگوریتم‌ها در ابتدا يک کلاستر تک توليد می‌کنند و روش‌هاي سريع و واضحي می‌باشند. در اکثر آنها بردارهاي خصوصيات به تعداد دفعات کمي و يا تنها يک بار به الگوريتم داده مي شوند. در اينجا بطور خلاصه الگوريتم ترتيبي پايه را توضيح می‌دهیم. در اين نمونه تمام بردارها يک بار به الگوريتم ارائه مي شوند. تعداد دسته‌ها در اين مورد از قبل مشخص نيستند. در واقع کلاسترهاي جديد در حين اجراي برنامه ايجاد مي شوند. اگر   به معناي فاصله (عدم شباهت) بين بردار خصوصيت و کلاستر  باشد، هر بردار  بسته به فاصله از کلاستر، به کلاسترهاي موجود و يا به کلاستر جديد نسبت داده می‌شود. در زير الگوريتم کلاسترينگ ترتيبي پايه آورده شده است. در الگوریتم‌های کلاسترينگ ترتيبي نتيجه نهايي به ترتيبي که بردارها به الگوريتم ارائه مي شوند بستگي دارد. -13622594890 وقتی می‌خواهیم یک کاری توسط کامپیوتری حل شود، اولین سؤالی که مطرح می‌شود اینست که چگونه مسئله را باید به ترمهای محاسباتی نشان بدهیم. در یادگیری ماشین این بدان معناست که چگونه مفاهیم، مثالهای آموزشی و دانش اولیه را نمایش دهیم. برای تشریح مفاهیم و نمونه‌ها از زبانهای نمایشی استفاده می‌کنیم. از نظر قدرت بیان و پیچیدگی می‌توان زبانها را طبقه‌بندی کرد و در یک ترتیب صعودی داریم: Zero-order Logic، Attribute-value Logic، Horn Clauses و Second-order Logic. در ادامه به معرفی کوتاهی از این چهار مدل زبان تشریحی می‌پردازم ولی اساس کار در این پروژه استفاده از منطق ارزش- ویژگی میباشد. 4-3 منطق رتبه صفر در منطق رتبه صفر، مفاهیم و نمونه‌ها را با ترکیب عطفی از ثابتهای بولی که هر کدام نماد یک ویژگی مجزا (مقادیر ویژگیها) می‌باشد. در مدل ریاضی، این نوع تشریح را می‌توان بصورت زیر نشان داد: «یک شیء نمونه‌ای از مفهوم C میباشد هر گاه x,y,z هر سه درست باشند ...» برای مثال یک تشریح اولیه و ابتدایی از شوهر کاندیدا برای Jane را تصور کنید: در این مدل تشریحی می‌توان از عملگر نقیض و یا ترکیب فصلی هم استفاده کرد. همانطور که ملاحظه می‌کنید این مدل تنها می‌تواند مفاهیم ساده را بیان کند و به عبارت دیگر از قدرت تشریحی پایینی برخوردار می‌باشد. 4-4 تخصیص منطق ریاضی از نظر رسمی این مدل به مانند منطق رتبه صفر می‌باشد، اما ساختار آن غنی تر و با انعطاف بیشتر می‌باشد. ایده اساسی در این مدل تمییز دادن نمونه‌ها و مفاهیم از روی مقادیری است که از قبل تحت عنوان ویژگی تعریف شده است (مثل رنگ، قد و ...). ارتقاء این مدل نسبت به منطق رتبه صفر (که مفاهیم از روی ترکیب عطفی ثابتها تمییز داده می شوند) اینست که ویژگیها متغیر می‌باشند و مقادیر مختلفی را به خود می‌گیرند. نمونه‌ها معمولاً در یک جدول قرار میگیرند و هر ستون نماد یک ویژگی است. 4-5 منطق رتبه اول منطق رتبه اول یک قالب رسمی را برای بیان و نتیجه‌گیری از اشیاء و روابط آنها مهیا می‌کند. یک زیرمجموعه مهم از منطق رتبه اول، خوشه های اصلی ها می‌باشند که هر عبارت در این مدل از دو قسمت سر و بدنه تشکیل شده است: Grandparent (X,Y):= Parent (X,Z) Parent (Z,Y) «فرد X جد فرد Y است اگر فرد Z ی پیدا شود که X والد Z و Z والد Y باشد ... » قسمت سمت چپ =: را Head و قسمت سمت راست را Body می‌نامیم. همچنین به ترمهایی چون والد ، گزاره و متغیرهای داخلی آن را آرگومان مینامیم. تعداد آرگومانها متنوع می‌باشد ولی برای یک گزاره داده شده این تعداد ثابت می‌باشد. اگر تمام گزاره‌ها تنها یک آرگومان داشته باشند، این زبان به Attribute-value Logic منتهی می‌شود و درصورتی‌که تمام گزاره‌ها صفر آرگومان داشته باشند، منطق رتبه صفر داریم. Horn Clauses ها می‌توانند یک زبان تشریحی پیشرفته‌ای (چون Prolog) را بسازند که مفاهیم پیچیده را می‌توان با آن نمایش داد. 4-6 منطق رتبه دوم در این منطق اسم گزاره‌ها را هم متغیر در نظر می‌گیریم و خانواده بزرگتری از زبانها معرفی می‌شود. برای مثال شمای زیر را در نظر بگیرید: p(X,Y):= q(X,XW) q(Y,YW) r(XW,YW) اگر جایگزینی= {p=Brothers, q=Son, r=Equal} را انجام دهیم، خواهیم داشت: Brothers(X,Y):= Son(X,XW) Son(Y,YW) Equal(XW,YW) و با یک جایگزینی دیگر = {p=Lighter, q=Weight, r=Less} 2داریم: Lighter(X,Y):= Weight(X,XW)Weight(Y,YW) Less(XW,YW) بنابراین همانطور که ملاحظه می‌کنید اسکلت عبارت دست نخورده باقی می‌ماند و تنها اسم گزاره‌ها تغییر می‌کند. آنچه در پشت این ایده می‌باشد اینست که معمولاً گروهی از مفاهیم ساختار بیانی قابل‌پذیرش مشترکی دارند و با این مدل بیانی می‌توان کمک بزرگی به جستجو مفاهیم کرد؛ اما از آنجاییکه این زبان بسیار پیچیده می‌باشد، خیلی بندرت از آن استفاده می‌شود (برای آشنایی بیشتر می‌توانید به برنامه CIA که در Raedt 1992 آمده است رجوع کنید). 4-7 جستجوی سراسری فاصله از تعمیم فرض کنید که یک زبان نمایشی انتخاب شده است. حال نوبت اینست که ماشین از روی نمونه‌های آموزشی و دانش اولیه می‌خواهد عمل یادگیری مفهوم را انجام دهد. در حالت کلی یادگیری را می‌توان به دو گروه اصلی تقسیم کرد: یادگیری با نظارت و یادگیری بدون نظارت . در دسته‌بندی با نظارت (یا تحلیل تفکیکی- Discrimination-) ما با یک کلکسیونی از نمونه‌های برچسب خورده (از قبل کلاسه‌بندی شده) مواجه هستیم. هدف برچسب زدن یک نمونه جدید می‌باشد که تا حال به سیستم معرفی نشده است؛ اما در مورد دسته‌بندی بدون نظارت (و یا کلاسترینگ)، هدف گروهبندی کلکسیونی از نمونه‌های برچسب نخورده به گروههای با معنا می‌باشد. برای بیان این معنا برچسبهائی را به هر گروه تخصیص می‌دهیم، با این تفاوت که منشأ این برچسب‌ها منحصراٌ از خود داده گرفته شده‌اند - Data-Driven -. فرض کنید که نمایش نمونه‌ها و مفاهیم بر اساس Attribute-value Logic باشد. در اینصورت فضای نمایشی برای بیان تمامی مفاهیم بسیار گسترده خواهد شد. برای مثال اگر ده ویژگی داشته باشیم که هر کدام می‌توانند پنج مقدار را بگیرند، پنج به توان ده (در حدود 9764625) بردار ممکن برایش وجود دارد. هر زیرمجموعه‌ای از این بردارها را می‌توان برای نمایش یک مفهوم استفاده کرد. با این تفاسیر برای این ده ویژگی می‌تواند دو به توان 9764625 مفهوم وجود داشته باشد. این عدد برای کامپیوترهای امروزی هم بزرگ خواهد بود و در زبانهای کمی پیچیده این مقدار خیلی بزرگتر هم خواهد شد؛ اما در این میان دانش اولیه از داده‌ها می‌تواند چاره‌ساز باشد و این مقدار را کاهش می‌دهد؛ بنابراین یادگیرها معمولاً از دو تکنیک استقرا و هوشمندی بهره می برند. برای روشن شدن استقرا، خصوصیات یک گنجشک را بعنوان یک نمونه مثبت برای مفهوم پرنده در نظر بگیرید. حال برای اینکه پرنده‌های دیگر را تشخیص دهیم و در این گروه قرار دهیم، حفظ کردن محض ویژگیهای گنجشک مذکور ما را به جائی نمی‌رساند. در حقیقت تعمیمی از این نمونه لازم می‌باشد؛ اما تا چه اندازه؟ برای ایجاد محدودیت نیازمند مثالهای آموزشی منفی می‌باشیم (نمونه‌ای که پرنده نباشد، مثلاً سگ). وقتی فضای جستجو بزرگ می‌شود، استفاده از تکنیکهای هوشمند ضروری می‌باشد. منظور از هوشمندی آنست که تصمیم بگیرد کدامیک از عملگرهای موجود، جستجو را به نزدیکترین مجاورت حالت پایانی هدایت می‌کند. این امر مستلزم به یک تابع ارزیابی است که مقدار هر حالتی را که به آن می‌رسیم، محاسبه کند (مثلاً آنتروپی). تکنیکهای یادگیری با ناظر را می‌توان در یک تقسیم‌بندی بفرم زیر نشان داد. در اینجا تنها به همین تقسیم‌بندی بسنده می‌کنم و در قسمت بعدی یادگیری بدون ناظر را که شاید بتوان حالت عام‌تری از دسته‌بندی با ناظر در نظر گرفت را شرح خواهم داد. -Inductive Essence of Learning -Exhaustive Search -Heuristic Search        Best-First Search Algorithm        Beam-Search Algorithm -Classic Methods of Learning        Divide & Conquer Learning     TDIDT        AQ Learning -Artificial discovery 4-8 آموزش بدون نظارت کلاسترینگ یک دسته‌بندی بدون نظارت از نمونه‌ها (مشاهدات، آیتمهای داده و بردارهای ویژگی) به گروهها (کلاسترها) می‌باشد. مسئله کلاسترینگ در زمینه‌های مختلفی توسط محققین به طرق مختلفی مطرح شده است؛ و این مسئله بیانگر اینست که کلاسترینگ یکی از مراحل مهم و اساسی در تحلیل اکتشافی داده می‌باشد. رویه‌های تحلیل داده ممکن است اکتشافی باشد یا تأییدی؛ اما عنصر کلیدی در هر دو نوع رویه‌ها (چه برای شکل‌دهی یک فرضیه یا یک تصمیم‌گیری) گروهبندی می‌باشد. آنالیز گروهبندی در حقیقت سازماندهی کلکسیونی از نمونه‌ها به کلاسترها بر پایه تشابهات می‌باشد؛ یعنی اینکه نمونه‌هایی که دریک کلاستر قرار دارند، ویژگیهای مشابه‌تری نسبت بهم دارند تا به ویژگی نمونه‌های کلاستر دیگر. شماره‌هایی که به هر کدام از نمونه‌ها داده شده است، برچسب آن کلاستر تلقی می‌شود. وجود تکنیکهای متعدد برای نمایش داده، اندازه‌گیری مجاور(تشابه) بین عناصر داده و گروه‌بندی آنها باعث شده است که متدهای کلاسترینگ به انواع مختلف در طبقه‌بندیهای مختلف معرفی شوند. کلاسترینگ در زمینه‌های مختلفی استفاده می‌شود که از جمله آنها تحلیل اکتشافی نمونه‌ها، گروهبندی، تصمیم‌گیری، موارد یادگیری ماشین شامل داده‌کاوی، بازیابی اسناد، قطعه‌بندی تصویر بکار گرفته می‌شود. اگرچه در بسیاری از موارد فوق با کمبود اطلاعات از قبل (شامل مدلهای آماری) در مورد داده‌ها مواجه می‌باشیم؛ بنابراین تصمیم‌گیرنده می‌بایست تا آنجا که ممکن است فرضیاتی را در مورد داده متصور شود. تحت این محدودیت است که متدلوژی کلاسترینگ بعنوان یک راهکار مناسب برای کشف ارتباطهای معنایی میان داده‌ها بشمار می‌رود که می‌توان از آن بعنوان یک دانش اولیه از داده‌ها یاد کرد. 4-9 قطعات و سیستمهای کار خوشه‌بندی فعالیتهایی که برای یک عملیات کلاسترینگ انجام می‌گیرد به قرار زیر می‌باشد: 1. نمایش الگو 2. تعریف یک شاخص مجاورت برای الگو متناسب با دامنه داده 3. گروهبندی (کلاسترینگ) 4. تجرد داده (در صورت لزوم) 5. ارزیابی خروجی Pattern Representation: معطوف به تعداد کلاسها، تعداد نمونه‌های موجود و تعداد، نوع و وزن ویژگیهای موجود برای آن الگوریتم کلاسترینگ می‌باشد. بعضی از اطلاعات ممکن است که برای فرد قابل کنترل و دستکاری نباشد. این بدان معناست که نمی‌توان مستقیماً از آن داده استفاده کرد. بدین منظور از دو رویه مهم کمک گرفته می‌شود. 1: گزینش ویژگی -، فرآیندی است که برای شناسایی مؤثرترین زیرمجموعه از ویژگیهای اولیه برای کلاسترینگ استفاده می‌شود. 2: استخراج ویژگی-، استفاده از یک یا چند مرحله تبدیل از ویژگیهای ورودی بمنظور بدست آوردن ویژگیهای برجسته جدید می‌باشد. از این دو تکنیک میتوان برای بدست آوردن مجموعه مناسبی از ویژگیها در امر کلاسترینگ استفاده کرد. مجاورت میان الگوها معمولاً توسط یک تابع مسافت که بروی جفتهایی از نمونه اعمال می‌شود، اندازه‌گیری می‌شود. ساده‌ترین معیار برای مسافت، فاصله اقلیدسی است که بیانگر افتراق بین دو نمونه می‌باشد. این در حالیست که معیارهای تشابه هم می‌توانند برای تشخیص تشابهات معنایی در میان نمونه‌ها استفاده شوند [Michalaski Stepp 1983]. جزئیات بیشتر این موضوع در ادامه تشریح خواهم کرد. گروهبندی به طرق مختلف قابل اجراست. بطور کلی دسته‌های خروجی به دو حالت ظاهر می شوند: - سخت می‌باشند، یعنی اینکه یک پارتیشنی از داده به گروهها نگاشت می‌شود. - فازی می‌باشند و هر نمونه با یک درجه عضویت به هر کدام از گروهها تعلق دارد و مانند حالت قبل این گونه نیست که نمونه‌ها انحصاراً به یک و تنها یک گروه تعلق داشته باشند. الگوریتمهای کلاسترینگ سلسله مراتبی، یک سری از پارتیشنهای تودرتو بر اساس یک معیار برای ادغام یا شکستن کلاسترینگ بر پایه تشابه تولید می‌کنند. در دسته مقابل الگوریتمهای سلسله مراتبی، الگوریتمهای کلاسترینگ پارتیشنی قرار دارند که مرزهایی در میان داده‌ها متصور می‌شود که معیار دسته‌بندی را (معمولاً بطور محلی) بهینه می‌کند. در قسمتهای بعدی این دو نوع الگوریتم به همراه دیگر الگوریتمهای کلاسترینگ از جمله متدهای احتمالی و بیزین و شبکه‌های عصبی و ... معرفی خواهد شد. استخراج داده: فرآیندی است از استخراج یک نمایش ساده و در عین حال غنی شده از مجموعه داده‌ها می‌باشد. در اینجا سادگی دو معنا دارد: - انالیز اتوماتیک، از دیدگاه ماشین که بتواند پردازشهای جلوتر را مؤثرتر انجام دهد. - قابل درک توسط انسان، از دیدگاه انسان بدین صورت که این نمایشهای داده برای او آسان و بطور مستقیم قابل فهم باشد. در قالب کلاسترینگ، یک تجرد داده شامل یک تشریح غنی از هرکلاستر می‌باشد. بطور سطحی و آسان شما می‌توانید مجموعه ویژگیهای عنصر مرکزی یک کلاستر را بعنوان برچسب و ماهیت آن کلاستر تعریف کنید. Assessment of Output: مسائلی که در زمینه ارزیابی یک الگوریتم مطرح می شوند، بدنبال این هستند که کدام نتیجه خوب می‌باشد و کدام ضعیف. این قدرت و ضعف بر اساس این است که دسته‌های خروجی چقدر به آن معیار نزدیک می‌باشد و برای ما معنا دار است. بر اساس اینکه داده‌ها چه پراکنده‌ای و رفتاری داشته باشند، الگوریتمها ممکن است پارامتریک، نیمه پارامتریک یا بدون پارامتریک باشند. این اطلاعات از قبل به ما کمک می‌کند که طبقه‌بندی خود را بهینه‌تر کنیم و در عین اگر پارامتریک باشد با مدلهای آماری موجود می‌توان کلاسترینگ را ارزیابی کرد (با آزمونهای مختلف). 4-10 تعاریف و یادداشتی قبل از اینکه تکنیکهای مختلف را معرفی کنم، لازم است که مفاهیم زیر را بدانیم: 1- یک Pattern (یک بردار ویژگی، مشاهده، اطلاع) را با x نشان می‌دهیم که شامل یک آیتم داده یگانه ایست که توسط الگورتیم کلاسترینگ استفاده می‌شود. x = (x1,x2,…,xd) d بعد این الگو (یا فضای الگو) را تعین می‌کند و xi هم یک عنصر مجزای اسکالری است که آنرا ویژگی -Attribute- می‌نامیم. 2- یک مجموعه ازالگوها - Pattern set - را با X = {x1,x2,…,xn}نشان می‌دهیم و i-امین نمونه در X بفرم xi = {xi,1,xi,2,…,xi,d} می‌باشد. در بسیاری از مواقع مجموعه الگویی که قرار است کلاستر شود، با یک ماتریس n*d از نمونه‌ها نمایش داده می‌شود. 3- یک کلاس -Class- به حالتی اشاره می‌شود که دلالت دارد بر فرآیند تولید آن نمونه. تکنیکهای کلاسترینگ در واقع تلاش می‌کنند که نمونه‌ها را گروهبندی کنند تا کلاسهای بدست آمده از این دسته‌بندی منعکس‌کننده فرآینده‌های مختلف از بوجود آمدن نمونه‌ها در یک Pattern set باشند. 4- تکنیکهای کلاسترینگ سخت یک برچسب کلاس li را به هر نمونه xi نسبت می‌دهند که بیانگر کلاس آنها می‌باشد. k تعداد کلاسترها می‌باشد li = {1,…,k} 5- رویه‌های کلاسترینگ فازی، به هر نمونه ورودی xi، یک عدد کسری fij را نسبت می‌دهند که بیانگر درجه عضویت آن نمونه به هر کدام از j تا کلاستر خروجی می‌باشد. 6- معیار مسافت - Distance measure - (حالت خاصی از معیار مجاورت) یک متراژی است بر روی فضای نمونه که تشابهات بین نمونه‌ها را کوانتیزه می‌کند. 4-11 نمایندگی الگو، انتخاب ویژگی و استخراج در واقع هیچ راهنمای تئوریکی وجود ندارد که به ما پیشنهاد کند که از چه نمونه‌ها و ویژگیهایی در امر کلاسترینگ استفاده کنیم. فی‌الواقع فرآیند تولید نمونه بطور مستقیم برای ما قابل کنترل نیست. نقش کاربر در یک فرآیند نمایش نمونه‌اینست که تا حد ممکن حدسیات و واقعیات مربوط به داده را جمع‌آوری کند و بطور اختیاری عملیات گزینش یا استخراج الگو را روی آنها پیاده کند و در نهایت عناصر بعدی که نیاز سیستم کلاسترینگ است را طراحی کند. بخاطر مصائبی که در نمایش الگو وجود دارد، برای سادگی فرض می‌شود که این نمایش الگو از قبل برای کلاسترینگ موجود می‌باشد. در کنار این مسئله یک بررسی دقیق حتی اگر خیلی ساده بر روی ویژگیهای موجود و اعمال یک یا چند تبدیل کمک شایانی به سطح کیفی کلاسترینگ می‌کند. نقاط در داخل این فضای ویژگی دوبعدی بر روی یک منحنی قرار گرفته‌اند که فاصله نسبتاً ثابتی را با مبدأ دارند. حال اگر کسی مختصات کارتزین را برای نمایش الگو انتخاب کند، بسیاری از الگوریتمهای کلاسترینگ مایل هستند که کلاستر مذکور را به چند کلاستر تقسیم کنند؛ اما اگر کسی از مختصات قطبی برای نمایش الگو استفاده کند، این الگوریتمها تنها یک کلاستر را بعنوان دسته خروجی تولید می‌کنند. ویژگیها را می‌توان در حالت کلی بقرار زیر تقسیم‌بندی کرد: 1. ویژگیهای کمی a. مقادیر پیوسته (مانند وزن) b. مقادیر گسسته (تعداد کامپیوترها) c. مقادیر فاصله و مدت دار - Interval - (مدت‌زمانی که یک رخداد طول می‌کشد) 2. ویژگیهای کیفی a. اسمی یا بدون ترتیب (رنگ) b. ترتیبی (درجات ارتش و یا ارزشیابی‌های کیفی مثل سرما و گرما) 4-12 معیارهای تشابه ازآنجایی‌که تشابه یک رکن اصلی از یک کلاستر بشمار می‌رود، تعیین یک معیار تشابه در فضای ویژگیها امری ضروری برای رویه‌های کلاسترینگ می‌باشد. بخاطر تنوعی که در انواع ویژگی‌ها وجود دارد، معیار مسافت می‌بایست به دقت انجام بگیرد. همانطور که در قبل متذکر شدم، استفاده از معیار مسافت برای محاسبه میزان افتراق بین دو نمونه بکار می‌رود. معروفترین متراژی که بر روی ویژگیهای پیوسته بکار برده می‌شود، فاصله اقلیدسی. این روش برای جاهایی که بعد فضا دو یا سه باشد، کارآئی خوبی دارد (در ضمن بهتراست که مجموعه داده‌های ما ایزوله و متراکم باشد). مشکل اصلی این روش اینست که ویژگیهایی با اندازه بزرگتر بر روی دیگر ویژگیها حاکمیت می‌کنند. راهکارهای بسیاری در راستای بهبود آن صورت گرفته که از جمله آن نرمال کردن ویژگیهای پیوسته در یک رنج مشخص می‌باشد. وابستگی خطی میان ویژگیها دومین مشکل این روش بحساب می‌آید که با اعمال تبدیل وزنی زیر می‌توان آنرا رفع کرد. رابطه بالا به Squared Mahalanobis Distance شهرت دارد. نمونه‌های xi و xj بصورت بردار فرض شده‌اند و ∑ ماتریس کواریانس میباشد. dm(0,0) وزنهای مختلفی را به ویژگیهای مختلف بر اساس واریانس آنها و وابستگی خطی بین هر دو نمونه نسبت میدهد. بعضی از الگوریتمهای کلاسترینگ بجای مجموعه نمونه اولیه از یک ماتریس مجاورت استفاده می‌کنند. با این ترفند می‌توان برای n نمونه، فاصله هر دو نمونه که تعدادی برابر n(n-1)/2 میباشد (تعداد عناصر بالا مثلث) را از قبل محاسبه کرد. حال اگر مقادیر ویژگیها پیوسته نباشند، خود مشکل دیگری است. در این گونه موارد معنای مجاورت و نزدیکی را می‌توان در یک حالت ساده با مقادیر بولی پاسخ گفت. در این زمینه کارهای مختلفی انجام گرفته است. Wilson and Martinez [1997] روشی جدید را پیشنهاد داده‌اند که ترکیبی از فاصله اقلیدسی برای ویژگیهای پیوسته و فاصله شمردنی (ازدحام) برای ویژگیهای اسمی می‌باشد. Michalaski and Stepp [1983] هم در کتاب خود از Context نام برده‌اند که دلالت میکند بر محیطی داده‌ها در آن قرار گرفته‌اند. حال تشابه بین دو نقطه xi و xj بصورت زیر تعریف می‌شود: ξ در این Context (مفهوم)، مجموعه‌ای از نقاط محاطی می‌باشند. یک متراژ معمول برای توصیف این Context، فاصله همسایگی دوطرفه (Mutual Neighbor Distance یا MND) میباشد (Gowda and Krishina [1977]). NN(xi,xj) در عبارت بالا به تعداد همسایگان xj با توجه به xi اشاره میکند. در شکل 4، نزدیکترین همسایه به A، B میباشد و برعکس. پس NN(A,B) = NN(B,A) = 1 و MND بین A و B برابر با دو میشود. همین طور برای دو نقطه B و C روابط زیر را داریم: NN(B,C) = 1 NN(C,B) = 2 MND (B,C) = 2+1 = 3 در این حالت MND (B,C) مانند قبل سه میباشد، اما MND (A,B) = 5 میشود. توجه داشته باشید که NN(B,A) = 3 میباشد و F جزء همسایگان A بشمار نمیرود. تئوری آقای Watanabe در سال 1985 که معروف به بچه اردک زشت میباشد، به قرار زیر است که: از آنجا که ما با استفاده از یک مجموعه متناهی از گزاره‌های که قادر به تشخیص هر دو اشیاء در نظر گرفته شده است، تعدادی از گزاره‌های به اشتراک گذاشته شده توسط هر دو جسم ثابت، مستقل از انتخاب اشیا است. بر اساس نظریه بالا این طور بنظر میرسد که میتوان هر دو نمونه دلخواهی را تقریباً شبیه بهم کرد که این کار با کدینگ کردن آن دو با تعداد قابل‌توجه و کافی از ویژگیها امکانپذیر است. برای مثال در کلاسترینگ معنایی - Conceptual Clustering - که در Michalaski and stepp 1983 معرفی شده (در ادامه این تکنیک را معرفی خواهم کرد)، تشابه بین xi و xj را اینطور بیان کرده: در عبارت بالا به مجموعه‌ای از مفاهیم از پیش تعریف شده اطلاق می‌شود. این نکته در شکل 6 نمایش داده شده است که فاصله اقلیدسی بین نقاط A و B کمتر از B و C می‌باشد؛ اما میتوان اینطور معنا کرد که B به C بیشتر شبیه – more similar - هست (مفهومی که با بیضی نشان داده شده) تا به A (مفهوم چهارضلعی) 4-13 تکنیکهای خوشه‌بندی در بالاترین سطح میتوان تکنیکهای کلاسترینگ را به دو شاخه سلسله مراتبی و پارتیشنی تقسیم کرد؛ اما قبل از معرفی تکنیکها، به نظرم آشنایی با بعضی از اصطلاحات مفید می‌باشد. - Agglomerative vs. Divisive: انباره‌ای یا تقسیم شدن به ساختار و عملکرد الگوریتم مربوط می‌شود. یک الگوریتم انباره‌ای با قرار دادن هر نمونه در یک کلاستر مجزا کار خود را شروع می‌کند و سعی می‌کند که این کلاسترها را در هم ادغام کند و در نهایت با رسیدن به یک آستانه قابل قبول به کار خود پایان می‌دهد؛ اما در حالت تقسیمی، الگوریتم همه نمونه‌ها را در یک کلاستر واحد قرار می‌دهد و بعد شروع به شکستن کلاسترها می‌کند تا به آن حد آستانه مطلوب برسد. - Monothetic vs. Polythetic: این خصیصه مربوط به آن است که در یک فرآیند کلاسترینگ، ویژگیها را بصورت دنباله‌ای بکار ببریم یا همزمان. - Hard vs. Fuzzy: در الگوریتمهای کلاسترینگ سخت، هر نمونه به یک و تنها یکی از کلاسترهای خروجی تعلق دارد؛ اما در الگوریتمهای کلاسترینگ فازی، هر نمونه با یک درجه‌ای از عضویت به هر کدام از کلاسترهای خروجی تعلق دارد. در این حالت می‌توان با انتخاب بزرگترین عدد عضویت برای یک نمونه، آن نمونه را به آن کلاستر نسبت داد. با این کار میتوان فازی را به سخت تبدیل کرد. - Deterministic vs. Stochastic: این مسئله قطعیت یا تصادفی بودن بیشتر درگیر با الگوریتمهای پارتیشنی است که سعی بر اینست که تابع مربع خطا بهبود یابد. این بهبودی از دو طریق قابل اعمال است: استفاده از تکنیکهای سنتی و یا از طریق جستجوی تصادفی در فضای حالت که شامل تمامی برچسبهای ممکن می‌باشد. - Incremental vs. Non-Incremental: این موضوع در جاهائی که مجموعه نمونه‌ها خیلی بزرگ باشد، مطرح می‌شود و دو عامل محدود کننده زمان اجرا و حافظه مصرفی ساختار الگوریتمها را از هم متمایز می‌کند. الگوریتمهای قدیمی طوری طراحی شده بودند که با نمونه‌های خیلی بزرگ سروکار نداشتند؛ اما با ظهور داده‌کاوی این نیاز احساس شد که الگوریتمهای کلاسترینگ به سوی مینیمم کردن تعداد دفعات اسکن سوق پیدا کنند (کم کردن تعداد دفعات آزمایش نمونه‌ها در طول اجرا و یا کم کردن سایز ساختارهای داده در طول عملیات الگوریتمها). 4-13-1 الگوریتم‌های خوشه‌بندی سلسله مراتبی حاصل این گونه الگوریتمها، یک dendrogram می‌باشد که نمایانگر یک گروهبندی تودرتو از نمونه‌ها و سطح تشابه آنها وقتی که گروهبندیها تغییر می‌کند، می‌باشد. dendrogram که از این هفت نقطه بوجود میاید (از الگوریتم single-link بدست آمده). dendrogram را می‌توان در سطوح مختلف شکاند تا کلاسترهایی از داده را نشان داد. سه تا از مهمترین الگوریتمهای کلاسترینگ سلسله مراتبی عبارتند از: 1. single-link [Sneath and Sokal 1973] 2. Complete-link [King 1967] 3. minimum-variance [Murtagh 1984] دو الگوریتم single-link و Complete-link بسیار معروف می‌باشند و تفاوت آنها در تشخیص تشابه بین هر دو کلاستر می‌باشد. در روش single-link، فاصله بین دو کلاستر عبارت است از مینیمم ترین فاصله‌ای که میان تمامی جفتهای دو طرف برقرار می‌باشد (یک نمونه از کلاستر اول و دومی از کلاستر دوم)؛ اما در روش Complete-link فاصله بین دو کلاستر از روی ماکزیمم ترین فاصله دو نمونه از دو کلاستر تعیین می‌شود. حال که فاصله بین کلاسترها مشخص شد، هر دو روش با شروع از کمترین فاصله، کلاسترها را در هم ادغام می‌کنند. الگوریتمهای Complete-link بیشتر مایلند که کلاسترهائی متراکم تولید کنند. این در حالیست که کلاسترهای خروجی الگوریتم single-link پراکنده و کشیده می‌باشد. اینکه بگوییم کدام بهتر است، پرسشی جالب بنظر نمی‌رسد. چون هر کدام از آنها می‌توانند کلاسترهایی تولید کنند که دیگری توانایی آنرا ندارد. برای مثال در شکل 12 تنها الگوریتم single-link است که می‌تواند کلاسترهای هم مرکز استخراج کند؛ اما از نقطه‌نظر عملی، الگوریتمهای Complete-link محبوبیت بیشتری دارند. 4-13-2 تک لینک الگوریتم خوشه‌بندی 1- در ابتدا هر نمونه را در یک کلاستر جداگانه گذاشته و فاصله هر دو نمونه مجزا را بدست آورید. این فاصله‌ها را در یک لیست قرار داده و بصورت صعودی مرتب کنید. 2- از میان لیست مرتب شده، برای هر مقدار افتراق مجزای dk نمونه‌های متناظر را بهم متصل کنید. این کار تا زمانی ادامه پیدا می‌کند که تمامی نمونه‌ها عضو یک گراف متصل (Connected-Graph) باشند. در غیر اینصورت این مرحله تکرار می‌شود. خروجی این الگوریتم یک سلسله مراتب تودرتو از گرافهایی می‌باشد که می‌توان آنرا در سطوح افتراق دلخواه شکاند و براحتی پارتیشنها (کلاسترها) را بوجود آورد. 4-13-3 الگوریتم خاصیت تراکم کامل لینک خوشه‌بندی این الگوریتم هم مانند قبلی است تنها با این تفاوت که فاصله بین دو نمونه به طریقی که قبلاً شرح آن آمد، می‌باشد و شرط خاتمه مرحله دوم این است که تمامی نمونه‌ها عضو یک گراف متصل کامل باشد. الگوریتمهای سلسله مراتبی نسبت به الگوریتمهای پارتیشنی که در قسمت بعد آنها را معرفی می‌کنم، از تنوع بیشتری برخوردارند. برای مثال الگوریتم کلاسترینگ single-link برای داده‌هایی که خواص مشترکی ندارند – non-isotropic – (پراکندگی خوب، زنجیره‌ای مانند و یا هم مرکز) بسیار خوب عمل می‌کند. این در حالیست که الگوریتم پارتیشنی چون K-means بر روی مجموعه داده‌هایی که isotropic هستند، کارا می‌باشد؛ اما از نظر پیچیدگی زمانی و فضا، الگوریتمهای پارتیشنی موقعیت بهتری را نسبت به سلسله مراتبی دارند. این موضوع باعث شده که در کاربردهای عملی از تلفیقی (Hybrid) از این دو نوع الگوریتم استفاده شود. 4-13-3-1 خاصیت تراکم الگوریتم خوشه‌بندی سلسله مراتبی 1- در ابتدا ماتریس مجاورتی می‌سازیم که فاصله هر دو نمونه را در آن نمایش می‌دهیم. در واقع با هر نمونه به عنوان یک کلاستر رفتار می‌کنیم. 2- با استفاده از ماتریس حاصل، جفتی را پیدا می‌کنیم که بسیار بهم شبیه‌ترند (کمترین عدد در ماتریس). آندو را در یک کلاستر ادغام می‌کنیم و ماتریس مجاورت را به روز می‌کنیم تا مبین این عمل ادغام باشد. 3- شرط خاتمه: تمامی نمونه‌ها در یک کلاستر باشند. در غیر اینصورت به مرحله دو می‌رویم. بر اساس اینکه در مرحله دوم ماتریس مجاورت را چگونه به روز کنیم، الگوریتمهای انباره‌ای مختلفی طراحی شده‌اند. الگوریتمهای تقسیمی سلسله مراتبی با یک کلاستر واحد شامل تمامی نمونه‌ها شروع بکار میکند و آنقدر کلاسترها را بر اساس یک معیاری میشکند تا به پارتیشنی از کلاسترهای یگانه برسد. 4-14 الگوریتم مرتب‌سازی آنچه که از یک الگوریتم کلاسترینگ پارتیشنی بدست می‌آید، یک پارتیشن واحدی از داده بجای یک ساختار کلاستری (چیزی شبیه dendrogram ی که در تکنیکهای سلسله مراتبی حاصل میشد) می‌باشد. متدهای پارتیشنی از این مزایا برخوردارند که می‌توانند با مجموعه وسیعی از داده‌ها کار کنند، و می‌دانیم که ساختن یک dendrogram از نظر محاسباتی مقرون به صرفه نخواهد بود؛ اما مشکلی که الگوریتمهای پارتیشنی را دنبال میکند، اینست که تعداد کلاسترهای خروجی چگونه انتخاب شود. روند تولید کلاسترها در تکنیکهای پارتیشنی بر این اساس است که یک تابع سنجش از قبل تعریف شده را بهینه کند؛ که این تابع ممکن است محلی باشد (بر روی زیرمجموعه‌ای از نمونه‌ها تعریف می‌شود) و یا سراسری (بر روی تمام نمونه‌ها). محاسبه مقدار بهینه واضح است که پر هزینه می‌باشد؛ بنابراین در عمل معمولاً این الگوریتمها را چندین بار با حالات شروع مختلف بر روی نمونه‌ها اجرا می‌کنند و بهترین ترکیب بدست آمده برای خروجی کلاسترینگ استفاده می‌گردد. 4-15 الگوریتم‌های خطا در مربع پرکاربردترین و مستقیم‌ترین تابع سنجش در تکنیکهای کلاسترینگ پارتیشنی، معیار خطای مربعی می‌باشد که بر روی کلاسترهای متراکم و ایزوله بسیار خوب جواب می‌دهد. 4-15-1 مربع خطا در روش خوشه‌بندی 1- یک پارتیشن اولیه‌ای از نمونه‌ها را با یک تعداد کلاستر تعیین شده به همراه عناصر مرکزیشان را انتخاب کنید. 2- هر نمونه را به نزدیکترین عنصر مرکزی (متعلق به هر کلاستر) را نسبت دهید و مراکز جدید کلاسترها را محاسبه کنید و آنرا جایگزین مرکزی قبلی نمایید. این عملیات را دوباره تکرار کنید تا یک همگرایی حاصل شود (تا زمانیکه این عضویتها پایدار شوند). 3- کلاسترها را بر اساس یکسری اطلاعات اکتشافی و ابتکارانه ادغام و بشکنید و بطور اختیاری مرحله دوم را تکرار کنید. k-mean ساده‌ترین و معمول‌ترین الگوریتمی است که از این معیار خطای مربعی استفاده می‌کند. این الگوریتم با یک پارتیشن تصادفی اولیه شروع به کار می‌کند و سعی می‌کند که هر نمونه را به یک کلاستر نسبت دهد. این کار بر اساس اینکه هر نمونه به کدامیک از عناصر مرکزی کلاسترها شبیه‌تر می‌باشد، انجام می‌شود و آن نمونه را به آن کلاستر نسبت می‌دهد. در مرحله بعد عناصر مرکزی جدید هر کلاستر محاسبه می‌شود و جایگزین مرکزی قبلی می‌شود. حال دوباره سعی می‌کنیم نمونه‌ها را با مراکز جدید بسنجیم و آنها را به کلاسترهای مربوطه جدید دوباره نسبت می‌دهیم. این عملیات آنقدر ادامه پیدا می‌کند تا به یک معیار همگرایی برسیم. این معیار همگرایی می‌تواند این باشد که دیگر نتوانیم یک نمونه را از یک کلاستر به کلاستر دیگر نسبت دهیم و یا اینکه بعد از چند مرحله کاهش خطای مربعی غیر محسوس باشد. در این حالت الگوریتم متوقف می‌شود. علت محبوبیت این الگوریتم در اینست که بسادگی قابل پیاده‌سازی است و پیچیدگی زمانی آن O(n) میباشد (n تعداد نمونه‌ها)؛ اما مشکل بزرگی که k-mean را تهدید می‌کند اینست که احتمال دارد در مینیمم محلی متوقف شود (اگر حالت اولیه را به درستی انتخاب نکنیم). این مسئله در شکل 13 نشان داده شده است. اگر این الگوریتم را با نمونه‌های اولیه A,B,C آغاز کنیم (یعنی می‌خواهیم در آخر تنها سه کلاستر خروجی داشته باشیم)، در آخر با پارتیشن {{A},{B,C},{D,E,F,G}} متوقف خواهیم شد. این پارتیشن‌بندی در شکل با بیضی نمایش داده شده است. حال مسئله را با نمونه‌های دیگری چون A,D,F اگر آغاز کنیم، به پارتیشن {{A,B,C},{D,E},{F,G}} می‌رسیم. برای اینکه بفهمیم کدامیک بهتر عمل کرده، خطای مربعی را برای دو پارتیشن بدست آمده محاسبه می‌کنیم و مشاهده می‌شود که خطای مربعی دومی کمتر از اولی می‌باشد. این بدان معناست که اگر راه اول را رفته باشیم در مینیمای محلی گیر خواهیم افتاد انواع مختلفی از الگوریتم k-mean در مقالات متعدد ذکر شده است. بعضی از آنها تلاش کرده‌اند که یک پارتیشن اولیه خوبی را انتخاب کنند تا الگوریتم بتواند به سوی پیدا کردن مقدار مینیمم سراسری متمایل شود. انواع دیگر کلاسترهای نتیجه را ادغام و یا می‌شکانند. معمولاً یک کلاستر شکسته می‌شود هرگاه واریانس آن بیشتر از یک حد تعریف شده باشد؛ و دو کلاستر در هم ادغام می شوند هر گاه فاصله بین دو عنصر مرکزی از دو کلاستر کمتر از یک حد آستانه تعریف شده باشد. فکر می‌کنم با این ابتکار بتوان با هر پارتیشن اولیه‌ای، به یک پارتیشن بهینه نهایی رسید (البته باید مقادیر پیش فرض آستانه را به واقع تخمین زد). الگوریتم ISODATA که بسیار معروف میباشد [Ball and Hall 1965] از همین تکنیک شکستن و ادغام استفاده می‌کند. برای مثال اگر پارتیشن بیضی در شکل 13 را بعنوان پارتیشن اولیه به این الگوریتم بدهید، می‌توان به سه کلاستر بهینه که با چهارضلعی نشان داده شده است، رسید. این الگوریتم در ابتدا دو کلاستر {A} و{B,C} را در یک کلاستر ادغام می‌کند (چون فاصله بین دو مرکز کوچک می‌باشد) و بعد کلاستر{D,E,F,G} که واریانس بزرگی دارد را به دو کلاستر{D,E} و{F,G} می‌شکند. بعضی دیگر از انواع الگوریتم k-mean از یک تابع سنجش دیگری استفاده می‌کنند. برای مثال Diday [1973] یک راهبرد کلاسترینگ دینامیکی را معرفی کرده که مسئله کلاسترینگ را با تخمین حداکثر اشتیاق (Maximum-Likelihood Estimation) پاسخ داده است. در ضمن بسیاری از مواقع در عمل از این الگوریتم بطور غیرمستقیم استفاده می‌شود. همانطور که در بالا ذکر کردم پیچیدگی زمانی این الگوریتم خطی و پیاده‌سازی آن آسان می‌باشد. به همین دلیل تلفیقی از این الگورتیم با دیگر الگوریتمها کارآیی خوبی دارد. برای مثال در قسمت بعد الگوریتمهای ژنتیکی را برای کلاسترینگ معرفی خواهم کرد از این الگوریتمها می‌توانیم برای پیدا کردن پارتیشن اولیه که ورودی الگوریتم k-mean است، استفاده کنیم. 4-16 گراف - خوشه‌بندی تئوری شناخته‌ترین الگوریتم کلاسترینگ تقسیمی بر پایه تئوری گراف، ساختن درخت مینیمال از نمونه‌های آموزشی می‌باشد [Zahn 1971]. که در این الگوریتم سعی می‌شود که یالهای با طول بزرگترین حذف می‌شود تا کلاسترهای دلخواه تولید شوند با شکستن اتصال CD با طول 6 (ماکزیمم فاصله اقلیدسی)، دو کلاستر{A,B,C} و{D,E,F,G,H,I} حاصل خواهند شد. در ادامه دومین کلاستر هم شکسته می‌شود، چون یال EF طولی برابر با 4.5 دارد. راهبردهای سلسله مراتبی را هم می‌توان به این نوع کلاسترینگ (بر پایه تئوری گراف) نسبت داد. به این معنا که کلاسترهای single-link در واقع زیرگرافهایی از این درخت مینیمال بشمار می‌روند. کلاسترهای Complete-link هم زیرگرافهای کامل ماکزیمال از گراف هستند (گراف رنگ‌آمیزی بر اساس رئوس). در واقع بر اساس ادعای Backer and Hubert [1967] این زیرگراف کامل ماکزیمال یک تعریف سخت و محکمی از کلاسترینگ در نظر گرفته می‌شود. 4-17 مخلوط حل و فصل و حالت طلب الگوریتم(Mixture-Resolving) راهبرد برطرف سازی مخلوط - Mixture-Resolving - برای عملیات کلاسترینگ به طرق مختلف تعریف شده‌اند. برای مثال Jain and Dubes [1988] در یک دسته‌بندی الگوریتمها را به دو قسمت طبقه‌بندی کرده‌اند: پارامتریک و ناپارامتریک. در تکنیکهای پارامتریک پیش فرضی که در نظر گرفته می‌شود اینست که نمونه‌ها از یک یا چندین توزیع گرفته شده است و هدف پیدا کردن پارامترهایی برای آن می‌باشد. در اکثر مواقع فرض میشود که اجزای مجزا از توزیع مخلوط بصورت گاوسین- Gaussian - می‌باشند. در اینصورت پارامترها در گاوسین های مجزا در طی یک پروسه‌ای تخمین زده می شوند (تخمین ماکزیمم اشتیاق). یکی از الگوریتمهایی که برای تخمین پارامترها بکار گرفته می‌شود، Expectation-Maximization می‌باشد که شرح کامل آن در کتاب Mitchell 1997 آورده شده است. در قالب کاری EM، پارامترهای اجزای تراکم نامعلوم می‌باشد (مخلوط) و از روی نمونه‌ها تخمین زده می شوند. پروسه EM با یک بردار احتمال اولیه از پارامترها شروع می‌شود و بصورت چرخه‌ای هر نمونه را در مقایسه با توزیع مخلوطی که توسط بردار پارامتر ساخته شده بود، امتیازدهی می‌کند. در مرحله بعد بردار پارامترها را تصحیح کرده و کار تکرار می‌شود. 4-17-1 الگوریتم EM فرض می‌کنیم هر نمونه بصورت Yi = باشد (k تا توزیع گاوسین داریم) که zij در این عبارت به معنای تعلق نمونه xi به توزیع گاوسین j-ام می‌باشد (zij مقدار بولی می‌گیرد). 1- یک بردار پارامتر پیش فرض برای این توزیع مخلوط متصور می‌شویم. h = 2- با استفاده از بردار پارامتر بدست آمده، امید k تا توزیع را بدست می آوریم. 3- با استفاده از k توزیعی که در بالا بدست آمده، بردار پارامتر را تصحیح می‌کنیم. اگر به یک معیار همگرایی رسیده باشیم الگوریتم متوقف می‌شود و در غیر اینصورت به مرحله دو می‌رویم. برای جزئیات بیشتر شما را به کتاب Machine Learning نوشته Ethem Alpaydin ارجاع میدهم که نسخه‌ای از آن در کتابخانه مرکزی دانشگاه امیرکبیر موجود می‌باشد. در این کتاب علاوه بر تکنیکهای پارامتریک و ناپارامتریک، دسته جدیدی را تحت عنوان نیمه پارامتریک - Semi-Parametric - معرفی کرده است. 4-18 خوشه‌بندی فازی در راهبردهای کلاسترینگ سنتی آنچه تولید می‌شد، یک پارتیشنی از داده‌ها بود. در این پارتیشن هر نمونه به یک و تنها یک کلاستر تعلق داشت؛ بنابراین کلاسترها در کلاسترینگ سخت از هم جدا و منفصل می‌باشند. منطق فازی که توسط آقای لطفی زاده در 1965 مطرح شد، این مفهوم را به کلاسترینگ افزود که هر نمونه را می‌توان با یک تابع عضویت به هر کدام از کلاسترها نسبت داد. مراحل کلی یک الگوریتم فازی به قرار زیر است: [Jan 1999 ] A.K. Jain and M.N. Murty and P.J. Flynn 1- ماتریس U را با سایز N*K عنصر اولیه مقداردهی می‌کنیم. (N شیء را به K کلاستر نسبت می‌دهیم). هر عنصر uij از این ماتریس بیانگر درجه عضویت شیء xi به کلاستر cj می‌باشد. معمولاً مقدار uij متعلق به بازه صفر تا یک می‌باشد. 2- با استفاده از ماتریس U بدست آمده، مقدار یک تابع سنجش فازی را پیدا میکنیم (برای مثال تابع سنجش خطای مربعی اوزان مربوط به آن پارتیشن) (در واقع k-امین مقدار مرکزی کلاستر فازی می‌باشد) در یک چرخه نمونه‌ها را دوباره به کلاسترها نسبت می‌دهیم تا این تابع سنجش معرفی شده در بالا را کاهش دهیم و دوباره ماتریس U را می‌سازیم. 3- مرحله دو را آنقدر تکرار می‌کنیم تا درایه‌های U تغییرات چشم‌گیری نکنند. ؛ اما یک الگوریتم کلاسترینگ فازی ممکن است F1 و F2 را در شکل بوجود بیاورند (بیضی) که هر نمونه دارای مقدار عضویتی بین صفر و یک می‌باشد. مثلاً F1= {(1,0.9), (2,0.8), (3,0.7), (4,0.6), (5,0.55), (6,0.2), (7,0.2), (8,0.0), (9,0.0)} F2= (1,0.0), (2,0.0), (3,0.0), (4,0.1), (5,0.15), (6,0.4), (7,0.35), (8,1.0), (9,0.9)} جفت مرتب در هر کلاستر نشان‌دهنده i-امین نمونه و مقدار عضویت آن به کلاستر می‌باشد. مقادیر عضویت بزرگ بیانگر اطمینان بالای انتساب یک نمونه به آن کلاستر است. همانطور که در قبل ذکر کردم، یک کلاسترینگ سخت را می‌توان با قرار دادن یک حد آستانه در کلاسترینگ فازی، بدست آورد. 4-19 شبکه‌های عصبی مصنوعی برای خوشه‌بندی همانطور که می‌دانیم، شبکه‌های عصبی مصنوعی از الگوی شبکه‌های عصبی بیولوژیکی ایده گرفته است. برخی از ویژگیهایی که باعث شده از ANN ها برای کلاسترینگ استفاده کنیم، عبارتند از: 1- ANN ها با بردارهای عددی کار می‌کنند، بنابراین نمونه‌های آموزشی می‌بایست تنها از ویژگیهای شمارشی برای نمایش استفاده کنند. 2- ANN ها ذاتاً موازی هستند و از معماری پردازشی توزیعی پشتیبانی می‌کنند. 3- ANN ها می‌توانند مقادیر وزنی فی مابین لایه‌ها را بطور تدریجی یاد بگیرند. از شبکه‌های عصبی رقابتی- Competitive - [Jain & Mao 1996] برای دسته‌بندی دادده‌های ورودی استفاده می‌کنیم. در یادگیری رقابتی، نمونه‌های مشابه هم توسط شبکه گروهبندی می شوند و با یک واحد مجزا (نرون) نمایش داده می‌شود. این گروهبندی بطور اتوماتیک بر اساس ارتباط داده‌ها انجام می‌گیرد. مثالهای شناخته شده از ANN ها که برای کلاسترینگ بکار رفته‌اند شامل Kohonen’s learning vector quantization (LVQ) و self-organizing map (SOM) و adaptive resonance theory models می‌باشد [Carpenter and Grossberg 1990]. معماری این ANN ها بسیار ساده است: آنها تک لایه‌ای هستند. نمونه‌ها در ورودی ظاهر می شوند و با نودهای خروجی پیوند خورده‌اند. وزنهایی که در میان نودهای ورودی و خروجی قرار گرفته‌اند، بطور چرخه‌ای آنقدر تغییر می‌کنند (که این عمل را یادگیری می‌نامیم) تا به یک معیار همگرایی برسیم. 4-20 روش‌های تکاملی برای خوشه‌بندی روشهای تکاملی که از روی سیر تکاملی طبیعی الگوبرداری شده‌اند، از عملگرهای تکوینی و جمعیتی از راه‌حلها استفاده می‌کند تا به یک تقسیم‌بندی سراسری بهینه‌ای از داده‌ها برسد. راه‌حلهای کاندید برای مسئله کلاسترینگ بصورت کروموزم رمزگذاری می شوند. معروفترین عملگرهای تکوینی هم شامل Selection، Recombination و Mutation می‌باشند که هر کدام یک یا چند کروموزم را بعنوان ورودی می‌گیرند و در خروجی یک یا چند کروموزم حاصل می‌شود. تابع fitness ی که برای ارزیابی یک کروموزم بکار می‌رود، بیانگر میزان اشتیاق کروموزم برای نجات یافتن به نسل بعدی می‌باشد. شرح سطح بالای یک الگوریتم تکاملی بصورت زیر می‌باشد: 1- یک جمعیت تصادفی از راه‌حلها را انتخاب کنید. منظور از راه‌حل در اینجا بمعنای یک k-پارتیشن معتبری از داده‌ها می‌باشد. حال یک مقدار fitness را برای هر راه‌حل محاسبه کنید. معمولاً fitness متناسب با عکس خطای مربعی می‌باشد. این بدین معناست که یک راه‌حل با خطای مربعی کوچک، یک مقدار fitness بالایی دارد. 2- از عملگرهای تکاملی Selection، Recombination و Mutation برای تولید نسل بعدی راه‌حلها استفاده کنید و برای هر کدام باز مقدار fitness را محاسبه کنید. 3- مرحله دوم را آنقدر تکرار کنید تا به یک شرط خاتمه برسید. از مشهورترین تکنیکهای تکاملی میتوان الگوریتهای ژنتیک (GA)، استراتژیهای تکاملی- Evolutionary Strategies - (ES) و برنامه نویسی تکاملی- Evolutionary Programming - (EP) را نام برد. در میان سه روش فوق، GA ها از اهمیت بیشتری برخوردارند. معمولاً راه‌حلها در این روش بصورت رشته‌های باینری بیان می شوند. عملگر گزینش با یک رفتار احتمالی بر روی مقدار fitness راه‌حلها، نسل بعدی از راه‌حلها را از میان راه‌حلهای موجود تولید می‌کند. انواع مختلفی از عملگرهای Recombination وجود دارند که معروفترین آنها crossover می‌باشد. در Mutation، یک کروموزم بعنوان ورودی در نظر گرفته می‌شود و کروموزم خروجی با مکمل کردن تصادفی یکی از بیتهای کروموزم اولیه حاصل می‌شود. برای مثال رشته 1111110 بعد از اعمال این عملگر بر روی بیت دوم رشته 1011110 تولید می‌شود. عملگر crossover برای اکتشاف فضای جستجو بکار میرود و این در حالیست که Mutation یک ضمانت کامل بودن می‌دهد (یعنی ضمانت می‌کند که هیچ قسمتی از فضای نمونه نیست که کشف نشده باشد). ES و EP ها در طرز نمایش راه‌حلها و همچنین عملگرهای تحولی متفاوت از GA ها میباشند. مثلاً EP از عملگر Recombination استفاده نمیکند؛ اما تمام این روشها برای حل مسئله کلاسترینگ بدنبال مینیمم کردن تابع خطای مربعی می‌باشند. مهمترین ویژگی GA ها جستجوی سراسری آنها می‌باشد. این در حالیست که روشهایی چون k-means، fuzzy clustering algorithms، شبکه‌های عصبی و جستجوهای simulated annealing و tabu search (که در ادامه معرفی خواهند شد) همگی بصورت محلی می‌باشند. این ویژگی GA از آنجا ناشی می‌شود که از عملگرهای تحولی چون crossover و mutation استفاده می‌کنند و راه‌حلهای کاملاً متفاوت را ارائه می‌دهند. فرض کنید اسکالری چون X با یک رشته باینری پنج بیتی کد شده است. S1 و S2 دو کروموزم (یا نقطه) در فضای جستجو یک بعدی می‌باشند و مقادیر دسیمال آنها بترتیب 8 و 31 می‌باشد. (S1= 01000, S2=11111). حال با اعمال crossover روی بیت پرارزش دوم و سوم می‌توان S3 و S4 را بدست آورد (S3=01111, S4=11000). بطور مشابه می‌توان Mutation را بر روی پرارزش‏ترین بیت 01111 اعمال کرد و رشته باینری 11111 که معادل 31 دسیمال است را بدست آورد. این پرشها در میان نقطه‌های مختلف فضای جستجو بسیار بزرگتر از آنهایی است که در روشهای قبل معرفی شد. در مقاله‌ای که توسط Raghavan and Birchand [1979] نوشته شده است (شاید یکی از اولین مقاله‌هایی است که درباره استفاده از GA برای کلاسترینگ وجود دارد)، هر نقطه را برای نمایش یک پارتیشنی از N شیء به K کلاستر تعریف کرده است. برای مثال 6 نمونه A,B,C,D,F را در نظر بگیرید که می‌خواهیم با دو کلاستر آنها را از هم جدا کنیم. رشته بیت 101001 که یک نقطه (کروموزم) را نشان می‌دهد، بیان می‌کند که کلاستر اول شامل نمونه‌های اولی، سومی و ششمی است و کلاستر دوم شامل بقیه نمونه‌هاست (هم ارز 010110). پس می‌توانیم کلاسترها را بفرم زیر نمایش دهیم: {A,C,F}, {B,D,E}. اگر K کلاستر داشته باشیم، K ! (فاکتوریل) کروموزمهای مختلف داریم که هر کدام به K پارتیشن از داده اشاره می‌کند. این فضای بزرگ باعث شد که محققین بدنبال طراحی بهینه‌ای از شمای نمایش و عملگرهای crossover باشند. یکی از این طرحها بکار بردن عملگر اضافی چون * می‌باشد، بدین معنی که کروموزمی چون BDE*ACF دو پارتیشن {A,C,F}, {B,D,E} را نمایش می‌دهد. حال می‌توان مسئله کلاسترینگ را به مسائلی چون فروشنده دوره گرد نگاشت کرد و آنرا ادامه داد [Bhuyan 1991]. یکی دیگر از این بهبودها که توسط Jones and Beltramo معرفی شد، بکار بردن عملگر edge-based crossover می‌باشد. در اینجا فرض می‌شود که تمام نمونه‌ها از یک کلاستر، یک گراف کاملی را تشکیل می‌دهند. کروموزمهای جدید که از والد خود بوجود می‌آیند، یالهای والد خود را نیز به ارث می برند؛ و بعد در همین پروژه ارزیابی کرده که در مواردی که تعداد کلاسترها بیش از 10 باشد پیچیدگی زمانی این نوع عملگر crossover برابر است با O(+N). 4-21 جستجو بر اساس رویکردهای تکنیکهای جستجو برای پیدا کردن مقدار بهینه‌ای از تابع ارزیابی بکار می‌روند و به دو دسته تکنیکهای قطعی و تصادفی تقسیم می شوند. در تکنیکهای قطعی با اجرای یک محاسبه کامل و زمان‌گیر، یک پارتیشن بهینه‌ای از داده‌ها را تضمین می‌کند. در طرف دیگر تکنیکهای تصادفی یک پارتیشن تقریباً بهینه را تولید می‌کنند که در نهایت به یک پارتیشن بهینه میل می‌کند. در میان تکنیکهایی که تا حال معرفی شدند همگی قطعی بودند به غیر از الگوریتمهای تکاملی. تکنیکهای قطعی معمولاً بصورت Greedy عمل می‌کنند و این در حالیست که در تکنیکهای تصادفی اجازه داده می‌شود که انحرافات راه‌حلها در سوی بهینگی غیر محلی با احتمالت غیر صفر سوق پیدا کند. تکنیکهای تصادفی می‌توانند موازی (الگوریتمهای تکاملی) و یا ترتیبی باشند. یک نمونه آشنای تکنیک تصادفی ترتیبی، جستجوی شبه تابکاری یا به اختصار SA می‌باشد. شبه تابکاری فرآیندی است که برای ایجاد تغییرات در فلزات و شیشه‌ها بکار می‌رود. در این کار آنها را تا درجه بالائی داغ کرده و آنگاه به تدریج سردشان می‌کنند تا مولکولهای مواد در یک حالت کم انرژی کریستالی به یکدیگر بچسبند. مشکل اصلی ما گیر افتادن در مینیماهای محلی است. پس احتیاج به نیرویی داریم که بتوانیم از این مینیمای محلی بیرون بیاییم؛ اما این تکان نباید به‌اندازه‌ای باشد که حتی از مینیمای سراسری هم بگذریم. بر همین اساس همانند روش شبه تابکاری، از تکانهای سخت شروع می‌کنیم (در درجه حرارت بالا) و بعد به تدریج شدت تکانها را کم می‌کنیم (با کاهش درجه حرارت). در این روش در یک حلقه تکرار بجای آنکه بهترین حرکت بعدی را برگزینیم، یک حرکت بعدی را بطور تصادفی انتخاب می‌کنیم. اگر این حرکت موقعیت ما را بهتر کرد آنرا بعنوان حرکت بعدی می‌پذیریم و در غیر اینصورت این حرکت را با احتمال p=e^(E/T) بعنوان حرکت بعدی می‌پذیریم. E اختلاف بدی وضعیت حاصل از حرکت مورد نظر با وضعیت جاری را نشان می‌دهد که دارای علامتی منفی است. این احتمال با کاهش درجه حرارت نیز کاهش می‌یابد. اثبات شده است که اگر کاهش تدریجی حرارت به اندازه کافی کند باشد، این الگوریتم بهینه سراسری را با احتمالی که به یک نزدیک می‌شود خواهد یافت (مثلاً T را هر بار در 0.98 ضرب کنیم). یک الگوریتم سطح بالای SA برای کلاسترینگ بصورت زیر خواهد بود: 1- بطور تصادفی یک پارتیشن اولیه‌ای چون P0 را انتخاب کرده و مقدار خطای مربعی EP0 را برای آن محاسبه کند. برای پارامترهای کنترلی T0 و Tf (درجه حرارت اولیه و نهایی) مقادیری را نسبت دهید. 2- همسایه‌ای از P0 چون P1 را انتخاب و EP1 را برایش محاسبه کنید. اگر این مقدار از EP0 بیشتر بود با همان احتمالی که شرح آن رفت P1 را به P0 نسبت دهید؛ و در غیر اینصورت P1 را به P0 نسبت دهید. این مرحله را برای تعداد مشخصی از تکرار انجام دهید. 3- T0 را کاهش دهید: T0=cT0. اگر T0 از Tf بزرگتر بود به مرحله دو برو و در غیر اینصورت الگوریتم خاتمه می‌یابد. 4-22 خوشه‌بندی مفهومی کلاسترینگ مفهومی از آن جهت برای ما مهم است که می‌توانیم نمونه‌هایی را که دسته‌بندی نشده‌اند در یک طبقه معنایی مشخص قرار دهیم و در یک سلسله مراتب خصوصیات عمومی طبقه بالاتر را به طبقات پایین‌تر منتقل کنیم (ارث‌بری). در حقیقت این شبیه همان کاری است که دانشمندان (بهتر است بگوییم بیولوژیست ها) سعی کرده‌اند در طی قرنها طبقه‌ای چون مهره‌داران و زیرگروه آن پستانداران و پرندگان و ... را معرفی کنند. حال اگر گفته شود که اسب یک پستاندار است، ما به سرعت متوجه خواهیم شد که آیا چنین حیوانی تخم می‌گذارد و یا اینکه پرواز می‌کند یا خیر؟!... در تکنیکهای آماری قدیمی هم کاری مشابه انجام می‌شود. مثلاً شکل زیر را در نظر بگیرید که نمونه‌ها را با دو ویژگی عددی x و y نمایش داده است. پر واضح است که با یک الگوریتم ساده کلاسترینگ که از similarity (میزان تشابه) بهره میبرد، میتوان نمونه‌ها را بدو گروه تقسیم کرد؛ و از آنجائیکه ویژگیهای مذکور عددی میباشند، براحتی از فاصله اقلیدسی بعنوان معیار تشابه می‌توان استفاده کرد (جزئیات این روش را در قبل مشاهده کردیم)؛ اما مسئله‌ای که وجود دارد اینست که تشابه هر نمونه‌ای را نمیتوان با ارزیابی‌های عددی انجام داد. برای مثال فاصله بین سگ و زرافه را با گربه و فیل بدست آورید؟!... حتی اگر بتوان این فاصله‌ها را به فرم عددی تبدیل کرد، خود این تبدیلات کاری سخت و دشوار خواهد بود. کلاسترینگ مفهومی را بعنوان یک فرم Novel (داستانی و حکایت) از عمل کلاسترینگ معرفی کرده‌اند که تنها کلکسیونی از اشیاء نمی‌باشد که دارای میزانی از تشابهات باشد (Michalski and Stepp 1983). با این تعریف می‌توان نتیجه گرفت که کلاسترینگ مفهومی نه تنها کلاسترها را تولید می‌کند، بلکه شرحی از مفاهیم مرتبط با آن را تولید می‌کند. در یک سطح انتزاعی بالا می‌توان مراحل الگوریتم کلاسترینگ معنایی را بفرم زیر خلاصه کرد: (R.S. Michalski, I. Bratko, M. Kubat 1998) 1- انتخاب k هسته که توسط کاربر تعریف می‌شود. 2- تعداد k ستاره بسازید. هر ستاره مجموعه‌ای از شرح عمومی‌ترین توصیفات یک هسته می‌باشد که این عمومی‌سازی آنقدر افزایش می‌یابد تا در مقابل هسته‌های دیگر محدود شود. 3- برای هر ستاره یک و تنها یک قانون (Rule) تولید کنید که اولاً حداقل تداخل منطقی را با دیگر قوانین مربوط به ستاره‌های دیگر داشته باشد و ثانیاً اجتماع منطقی تمام قوانین، بیشترین تعداد نمونه‌ها را پوشش دهد. 4- اگر هنوز نمونه‌ای باقی مانده‌اند که پوشش داده نشده است، مناسبترین (Fine) قوانین را برای آنها پیدا کنید. در تخصیص قوانین می‌بایست بازنگری بعمل بیاید (Refine) تا قوانین حاصل تمام نمونه‌های باقیمانده را پوشش دهد و بطور منطقی جدا از هم باشند. نمونه‌هائی که متعلق به اشتراک چند قانون هستند را دوباره توزیع کنید تا هر نمونه دقیقاً به یک قانون نسبت داده شود. در این لحظه هر قانون مجموعه‌ای از نمونه‌ها را نمایش می‌دهد. حال برای هر کدام از این مجموعه‌ها هسته جدید را انتخاب کنید. 5- رویه فوق را با هسته‌های جدید تکرار کنید. این چرخه تا زمانی که نتایج جدید بهبودی در نتیجه قبلی حاصل می‌کند، ادامه دهید. در آخر می‌توانید نتیجه‌ای که بالاترین کیفیت را دارد مشخص کنید. کیفیت بالاتر بر اساس معیارهای مختلفی تعیین می‌شود. مثلاً سادگی قوانین و یا میزان پراکندگی کلاسترها (اندازه‌گیری درجه عمومی‌سازی قوانین روی نمونه‌های پوشش داده شده توسط آن قانون) برای آنکه الگوریتم فوق را متوجه شویم، جدول زیر را در نظر بگیرید که متشکل از سه ویژگی می‌باشد. ویژگی اول سمبلیک، ویژگی دوم مقادیر صحیح و ویژگی سوم مقادیر صحیحی می‌باشد که می‌توان آنرا با سه سمبل Small،Medium و Large گسسته وار نمایش داد. این الگوریتم را با K=2 آغاز می‌کنیم؛ بنابراین بطور تصادفی دو هسته را انتخاب می‌کنیم. مثلاً e1 و e5؛ و داریم: ExampleAttribute1Attribute2Attribute3 e1 a 2 110 e2 b 4 100 e3 b 2 9 e4 b 3 10 e5 c 5 20 e6 c 4 15 e7 b 5 200 e8 b 4 50 dest (e1): (at1=a) & (at2=2) & (at3=Large) dest (e5): (at1=c) & (at2=5) & (at3=Small) و ستاره‌های اولیه عبارتند از: star (e1): (at1≠c) & (at2≠5) & (at3≠Small) star (e5): (at1≠a) & (at2≠4) & (at3≠Large) هر ستاره سه قانون تک شرطی دارد و قوانین متعلق به ستاره‌های مختلف با هم متقاطع می‌باشند. از هر ستاره یک قانون انتخاب می‌شود و بنحوی اصلاح می‌شود که قوانین داخل مجموعه_قوانین (Rule-Set) بدست آمده بطور منطقی از هم جدا باشند و اجتماع آنها تمامی نمونه‌ها را پوشش دهد (این عمل با رویه‌های NID و PRO انجام می‌گیرد و در Michalski and Stepp 1983 آمده است). نتیجه حاصل از عملیات فوق، راه‌حل زیر می‌باشد: CLUSTER 1: (at1=ab) & (at2=23) instances: e1,e3,e4 CLUSTER 2: (at1=bc) & (at2=45) instances: e2,e5,e6,e7,e8 این راه‌حل را می‌توان بعنوان بهترین جواب برای K=2 در نظر گرفت؛ زیرا انتخاب هسته‌های دیگر از قوانین فوق، ارتقایی در جواب بوجود نمی‌آورد. حتی تکرار الگوریتم برای مقادیر دیگر K هم بهبودی حاصل نمی‌کند. پس می‌توان نتیجه گرفت که راه‌حل فوق بهترین کلاسترینگ معنایی است که می‌توان بر روی داده‌های آموزشی مذکور بوجود آورد. 4-23 نتیجه‌گیری خوشه‌بندی یکی از شاخه‌های یادگیری بدون نظارت می‌باشد و فرآیند خودکاری است که در طی آن، نمونه‌ها به دسته‌هایی که اعضای آن مشابه یکدیگر می‌باشند تقسیم می شوند که به این دسته‌ها خوشه گفته میشود؛ بنابراین خوشه مجموعه‌ای از اشیاء می‌باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه‌های دیگر غیر مشابه می‌باشند. برای مشابه بودن می‌توان معیارهای مختلفی را در نظر گرفت مثلاً می‌توان معیار فاصله را برای خوشه‌بندی مورد استفاده قرار داد و اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفت که به این نوع خوشه‌بندی، خوشه‌بندی مبتنی بر فاصله نیز گفته می‌شود. خوشه‌بندی به عمل تقسیم جمعیت ناهمگن به تعدادی از زیر مجموعه‌ها یا خوشه‌های همگن گفته میشود. وجه تمایز خوشهبندی از دستهبندی این است که خوشهبندی به دستههای از پیش تعیین شده تکیه ندارد. در دستهبندی بر اساس یک مدل هر کدام از دادهها به دستهای از پیش تعیین شده اختصاص مییابد؛ این دستهها یا از ابتدا در طبیعت وجود داشتهاند(مثل جنسیت، رنگ پوست و مثالهایی از این قبیل) یا از طریق یافتههای پژوهشهای پیشین تعیین گردیدهاند. در خوشهبندی هیچ دستۀ از پیش تعیین شدهای وجود ندارد و دادهها صرفاً بر اساس تشابه گروهبندی میشوند و عناوین هر گروه نیز توسط کاربر تعیین میگردد. به طور مثال خوشههای علائم بیماریها ممکن است بیماریهای مختلفی را نشان دهند و خوشههای ویژگیهای مشتریان ممکن است حاکی از بخشهای مختلف بازار باشد. خوشهبندی معمولاً به عنوان پیش درآمدی برای بکارگیری سایر تحلیلهای دادهکاوی یا مدلسازی به کار میرود. به عنوان مثال، خوشهبندی ممکن است اولین گام در تلاش برای تقسیمبندی بازار باشد؛ برای ایجاد یک قانون که در همۀ موارد کاربرد داشته باشد و به این سؤال پاسخ دهد که مشتریان به چه نوع تبلیغاتی به بهترین نحو پاسخ میدهند اول باید مشتریان را به خوشه‌های متشکل از افرادی با عادات مشابه خرید تقسیم نمود و سپس پرسید که چه نوع تبلیغاتی برای هر خوشه به بهترین نحو عمل می‌کند. فصل پنجم نتایج و پیشنهادات 5-1 نتیجه‌گیری روش‌ها و تکنیک‌های خوشه‌بندی اطلاعات به عنوان روشهای مطلوب و مؤثر طبقه‌بندی اطلاعات که دارای پیچیدگی‌ها و ظرافتهای خاص خودشان هستند مورد توجه قرار می‌گیرند. عملکرد هر یک از الگوریتم‌های خوشه‌بندی ممکن است در مورد هر یک از سری‌های اطلاعاتی متنوع، به طور قابل‌توجهی متفاوت باشد. همچنین الگوریتم مطلق و محضی در این الگوریتم‌های خوشه‌بندی وجود ندارد که به نتایج محض و مطلق منجر شود. اشکال قابل‌توجه الگوریتم‌های خوشه‌بندی، در واقع، تفاوت زمانی است که در محاسبات مورد توجه قرار نمی‌گیرد. تفاوتهای موجود در شدت تراکم اطلاعات در فضای اطلاعاتی به تداخل خوشه‌ها، بروز ویژگی‌های غیرمرتبط، افزایش اطلاعات صوتی، عدم دانش و اطلاعات قبلی و کافی، منجر می‌شود. برای غلبه بر این مشکلات همراه با تحلیل خوشه‌ها، علاوه بر استفاده از این الگوریتمهای معمول و رایج استفاده از روشهای جدید و پیشرفته می‌تواند برای تشخیص و شناسائی ساختارهای شبکه‌های ژنتیکی، ضروری و الزامی باشد. از این رو استفاده از الگوریتم‌هایی خوشه‌بندی دو بعدی و سه بعدی برای از بین بردن نقاط ضعف و ارتقاء و بهبود نقاط قوت و بازدهی بیشتر الگوریتم‌های خوشه‌بندی مورد توجه قرار می‌گیرد، اما در اغلب موارد پیشرفتهایی در این زمینه ایجاد می شوند. 5-2 پیشنهادات در این پروژه سعی شد مروری روی فیلد گسترده داده‌کاوی انجام شود. در این مقاله تعاریف رسمی از واژگان حوزه داده‌کاوی، کاربردهای اصلی و همچنین مرور مختصری روی مهمترین روشهای داده‌کاوی موجود به همراه مزایا و معایب آنها، عرضه شد. اگرچه بیان همه روشها و کاربردها در این زمینه ممکن نیست اما این مقاله میتواند دید کلی از داده‌کاوی در ذهن خواننده ایجاد کند و در صورت علاقه برای مطالعه بیشتر آن را به منابعی هدایت میکند. طيف وسيعي از كاربردها براي اين تكنولوژي قابل تصور است. درعين حال اين تكنولوژي يك زمینه‌ی جوان و درحال رشد است كه به ما كمك می‌کند از دانش موجود در متون غير ساخت يافته بهره ببريم. تحقیق در زمینه دادهکاوی و کشف دانش هنوز ادامه دارد توجه داشته باشید به این جمله و در برخورد با داده‌کاوی این موضوع را سرلوحه کار خود قرار دهید که داده‌کاوی یک ابزار است. ما در برخورد با هر ابزاری باید توجه داشته باشیم که شناخت اینکه آن ابزار چگونه کار می‌کند، کافی نیست. بلکه ضرورت دارد که بدانیم چگونه می‌توانیم از آن ابزار استفاده کنیم. پس در برخورد با داده‌کاوی و انجام پروژه‏ها و پایان‌نامه‌ها با این موضوع توجه داشته باشید که چگونه می‌توان از داده‌کاوی بهره برد اگر این موضوع را مدنظر قرار دهید می‌بینید که چه کارهایی می‌توان با داده‌کاوی انجام داد. مراجع 1 – داده‌کاوی و کشف دانش، مهدی غضنفری و سمیه علیزاده و بابک تیمورپور، انتشارات دانشگاه علم و صنعت. 2 - داده‌کاوی کاربردی، محمد صنیعی آباده سینا محمودی، انتشارات نیاز دانش.