درباره خوشه بندی در داده کاوی چه می‌دانید؟

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

منظور از خوشه‌بندی چیست؟

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

به طور کلی خوشه بندی در داده کاوی کاربردهای متنوعی در صنایع مختلف دارد که به طور مفصل در بخش ” کاربردهای خوشه‌بندی در عمل ”  در مورد آنها صحبت می‌شود. اما برای درک بهتر این مفهوم تنها به ذکر چند مورد در این قسمت بسنده می‌کنیم:

– طراحی یک برنامه اقتصادی ممکن است علاقه‌مند به یافتن کشورهایی باشیم که اقتصاد آنها مشابه است.

– در یک برنامه بازاریابی ممکن است بخواهیم گروه‌هایی از مشتریان با رفتارهای خرید مشابه را پیدا کنیم.

– در یک برنامه پزشکی ممکن است بخواهیم گروه‌هایی از بیماران با علائم مشابه را پیدا کنیم.

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

چه تفاوتی بین خوشه‌بندی (Clustering) و دسته‌بندی (Classification) وجود دارد؟

خوشه‌بندی و دسته‌بندی هر دو از تکنیک‌های داده‌کاوی به شمار می‌روند که جهت استخراج دانش به گروه‌بندی و تقسیم‌بندی داده‌ها می‌پردازند، به همین دلیل معمولا در کنار هم مطرح می‌شوند. با وجود شباهت‌های فراوان، این دو تکنیک تفاوت‌های بنیادینی دارند که نباید آنها را نادیده گرفت. رویکرد دسته‌بندی و یا Classification از گروه‌های از پیش تعریف شده‌ای استفاده می‌کند و اشیا را به این گروه‌ها تخصیص می‌دهد، در حالیکه خوشه‌بندی و یا Clustering شباهت‌های بین اشیاء را شناسایی و بر اساس ویژگی‌های مشترک گروه‌بندی می‌کند. به بیانی دیگر، در دسته‌بندی، برچسب داده‌ها و گروه‌ها مشخص است و با ارائه یک داده جدید با توجه به مشخصاتش، در گروه مناسب قرار می‌گیرد اما در خوشه‌بندی، داده‌ها بر اساس الگوهای ذاتی بین خود دسته‌بندی می‌شوند بدون اینکه در مورد برچسب آنها اطلاعاتی موجود باشد .به زبان هوش مصنوعی، “دسته‌بندی” مرتبط با یادگیری با نظارت است و “خوشه‌بندی” مرتبط با یادگیری بدون نظارت است. عدم نیاز به داده‌های برچسب‌گذاری شده، مزیتی برای خوشه‌بندی نسبت به طبقه‌بندی به همراه داشته که آنرا با تغییرات سازگار کرده و ویژگی‌های مفیدی که گروه‌های مختلف را از یکدیگر متمایز می‌کند، شناسایی می‌نماید.

با انواع روش‌های خوشه بندی در داده کاوی آشنا شوید

چندین روش برای انجام تجزیه و تحلیل خوشه‌ای وجود دارد. جهت دسترسی به یک فهرست جامع می‌توانید به مطالعه Ezugwu و همکاران تحت عنوان«A Comprehensive Survey of Clustering Algorithms» مراجعه نمایید. بر اساس این مطالعه، روش‌های خوشه‌بندی به دو دسته کلی خوشه‌بندی سلسله مراتبی و خوشه‌بندی پارتیشن‌بندی مطابق با شکل زیر دسته‌بندی می‌شوند. که در ادامه هر یک را به طور خلاصه شرح می‌دهیم.

خوشه‌بندی سلسله‌مراتبی (Hierarchical Clustering)

در روش خوشه‌بندی سلسله مراتبی، مجموعه داده‌ها به صورت سلسله مراتبی تقسیم‌بندی می‌شوند. روند انجام این نوع از خوشه‌بندی توسط نموداری تحت عنوان درختواره (Dendrogram) نشان داده می‌شود. جهت درک بهتر مفهوم سلسله‌مراتبی در خوشه‌بندی، مثال زیر را در نظر بگیرید.

1. در ابتدا هر داده به عنوان یک خوشه جداگانه در نظر گرفته می‌شود.
2. سپس نزدیکترین خوشه‌‌ها (بر اساس مرکز ثقل و یا فاصله اقلیدسی) در هم ادغام می‌شوند و تشکیل یک خوشه را می‌دهند.
3. مرحله دو تا زمانی ادامه خواهد داشت که در نهایت یک خوشه باقی بماند. به عبارت دیگر، وجود یک خوشه نشاندهنده مرحله پایانی این روش می‌باشد.

البته لازم است به این نکته اشاره گردد که مراحل بالا معرف رویکرد خوشه‌بندی سلسله مراتبی از نوع تجمعی Agglomerative است. در مقابل رویکردی تحت عنوان «خوشه‌بندی سلسله‌مراتبی تقسیمی Divisive» قرار دارد که در ابتدا تمامی داده‌ها را در یک خوشه‌ در نظر می‌گیرد و سپس به مرور هر خوشه را به خوشه‌های کوچکتر تقسیم می‌نماید تا زمانیکه هر داده در یک خوشه جای بگیرد. جهت تعیین تعداد خوشه‌ها در هر مرحله می‌توان خط افقی‌ای رسم نمود، بر اساس تعداد دفعاتی که خط افقی ترسیم شده، نمودارها را قطع می‌نماید، تعداد خوشه‌ها مشخص می‌گردد.

خوشه‌بندی پارتیشن‌بندی (Partitioning Clustering)

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

خوشه‌بندی مرکز محور (Centroid–based clustering)

خوشه‌بندی مبتنی بر مرکز، برخلاف خوشه‌بندی سلسله مراتبی، داده‌ها را در خوشه‌های غیر سلسله مراتبی سازمان‌دهی می‌کند. ایده اصلی این روش، یافتن k مرکز و به دنبال آن یافتن k مجموعه داده است که بر اساس نزدیکی به مرکزها گروه‌بندی می‌شوند به طوری که مجذور فاصله نقاط در خوشه تا مرکز به حداقل برسد. k-means پرکاربردترین الگوریتم خوشه‌بندی مبتنی بر مرکز است که در این بخش در مورد این روش صحبت می‌کنیم. این الگوریتم خوشه‌بندی تکراری است که در ۵ مرحله کلی انجام می‌شود:

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

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

خوشه‌بندی چگالی‌محور (Density-based Method)

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

خوشه‌بندی مدل‌محور

در این نوع خوشه‌بندی فرض شده است که داده‌ها از توزیع‌هایی مانند توزیع‌های گاوسی تشکیل شده‌اند. در شکل زیر، الگوریتم مبتنی بر توزیع داده‌ها را در سه توزیع گاوسی خوشه بندی می‌کند. با افزایش فاصله از مرکز توزیع، احتمال تعلق یک نقطه به توزیع کاهش می‌یابد. این روش با هدف تعیین یک مدل (یک توزیع) برای هر خوشه‌ به نوعی که بیشترین همخوانی را با داده‌ها داشته باشد، مطرح می‌شود. البته لازم است به این نکته اشاره گردد، که این روش برای زمانی که نوع توزیع در داده‌های خود را نمی دانید، مناسب نخواهد بود.

ارزیابی مدل‌های خوشه بندی

قبل از ارزیابی عملکرد خوشه‌بندی، لازم است از تمایل به خوشه‌بندی مجموعه داده‌ای که در حال کار با آن هستیم اطمینان حاصل کنیم. به بیانی دیگر، اطمینان ازینکه نقاط دارای توزیع یکنواخت نباشند، بسیار مهم است. اگر داده‌ها شامل گرایش خوشه‌بندی نباشند، خوشه‌هایی که توسط هر الگوریتم خوشه‌بندی شناسایی می‌شوند ممکن است نامربوط باشند. بنابراین، توزیع غیر یکنواخت نقاط در مجموعه داده‌ها در خوشه‌بندی یکی از فرضیات اصلی برای اجرای این فرایند است. در این راستا، آزمون هاپکینز (Hopkins Test)، یک آزمون آماری جهت بررسی تمایل داده‌ها برای خوشه‌بندی، مطرح می‌شود. این آزمون آماری به صورت زیر تعریف می‌شود:

فرضیه صفر: نقاط داده با توزیع یکنواخت تولید می‌شوند (به معنای عدم وجود خوشه‌های معنی دار)

فرضیه جایگزین: نقاط داده توسط نقاط داده تصادفی تولید می‌شوند (وجود خوشه ها)

اگر H>0.5 باشد، فرضیه صفر را می توان رد کرد و به احتمال زیاد داده ها دارای خوشه هستند. اگر H نزدیک‌تر به ۰ باشد، مجموعه داده‌ها تمایل به خوشه‌بندی ندارند.

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

نمی‌توان به طور قطعی راهکار مناسبی برای یافتن تعداد درست خوشه پیشنهاد داد زیرا عواملی نظیر شکل توزیع، مقیاس در مجموعه داده‌ها و  وضوح خوشه بندی مورد نیاز کاربر می‌تواند در انتخاب درست این روش تأثیر گذارد. اگرچه یافتن تعداد خوشه‌ها معمولا یک فرایند ذهنی است، اما می‌توان برای این منظور از دو رویکرد دانش دامنه Domain knowledge
 و رویکرد داده‌محور برای یافتن تعداد بهینه خوشه‌ها استفاده کرد.

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

(۱) معیارهای بیرونی که به برچسب‌های مبنا (Ground truth labels) نیاز دارند. به عنوان مثال می‌توان به شاخص رند اطلاح شده (Adjusted Rand index)، امتیازات فاولکس-مالوز (Fowlkes-Mallows scores)، امتیازات مبتنی بر اطلاعات متقابل (Mutual information based scores)، همگنی (Homogeneity)، کامل بودن و اندازه گیری V (V-measure) اشاره کرد.

(۲) معیارهای ذاتی که نیازی به برچسب مبنا ندارد. برخی از معیارهای عملکرد خوشه‌بندی که در این دسته جای می‌گیرند، عبارتند از ضریب سیلوئت (Silhouette Coefficient)، شاخص کالینسکی-هاراباسز (Calinski-Harabasz Index)، شاخص دیویس-بولدین (Davies-Bouldin Index) و غیره.

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

شناسایی اخبار جعلی

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

فیلترکردن ایمیل‌های هرزنامه

ایمیل‌های هرزنامه در بهترین حالت بخشی آزاردهنده از تکنیک‌های بازاریابی مدرن هستند و در بدترین حالت، جهت دریافت اطلاعات شخصی شما و کلاهبرداری ارسال می‌شوند. برای جلوگیری از دریافت این ایمیل ها در صندوق ورودی اصلی شما، شرکت‌های ایمیل از الگوریتم‌هایی به منظور علامت‌گذاری ایمیل‌ها به‌عنوان هرزنامه استفاده می‌کنند. تکنیک‌های خوشه‌بندی K-Means راهی مؤثر برای شناسایی هرزنامه‌ها هستند. روش کار با بررسی بخش‌های مختلف ایمیل (سرصفحه، فرستنده و محتوا) آغاز می‌شود. سپس داده‌ها با هم گروه‌بندی می‌گردند. در نهایت، این گروه‌ها برای شناسایی اسپم‌ها طبقه‌بندی می‌شوند. ترکیب خوشه‌بندی با دسته‌بندی توانسته دقت فیلتر را تا ۹۷ درصد بهبود بخشد. این یک خبر عالی برای افرادی است که می‌خواهند مطمئن شوند خبرنامه‌ها و پیشنهادات مورد علاقه خود را دریافت می‌کنند.

بازاریابی و فروش

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

شناسایی ترافیک شبکه

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

خوشه‌بندی K-means برای گروه‌بندی ویژگی‌های منابع ترافیکی مختلف استفاده می‌شود. هنگامی که خوشه‌ها ایجاد می شوند، می‌توانید انواع ترافیک را طبقه بندی کنید. با داشتن اطلاعات دقیق در مورد منابع ترافیک، می‌توانید سایت خود را رشد داده و ظرفیت‌های برنامه‌ریزی موثرتری ایجاد نمایید.

تجزیه و تحلیل اسناد

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