بخشی از مقاله
چکیده - با آغاز عصر جدید سرعت تغییر حجم و تنوع داده ها تفاوت چشمگیری نسبت به دهه های قبل داشته است. مشکلی که در راستای این پیشرفت وجود دارد ، آنالیز و تجزیه و تحلیل داده های بزرگ است. با استفاده از تکنیک های داده کاوی می توان اطلاعات مفید و روابط پنهان میان داده ها را استخراج کرد. روش های سنتی داده کاوی به علت سرعت پایین ، نمی توانند بطور مستقیم برروی داده های بزرگ اجرا شوند و ما باید به دنبال راه حلی باشیم که بتوانیم با آنها داده های بزرگ را مورد تجزیه و تحلیل قرار دهیم. یکی از تکنیک های داده کاوی خوشه بندی است که داده های مشابه را در یک خوشه جای می دهد. در این مقاله ما برخی تکنیک های خوشه بندی داده های بزرگ را مورد بررسی قرار خواهیم داد.
-1 مقدمه
ادامه به بررسی تکنیک های خوشه بندی برای داده های بزرگ می پردازیم.
· خوشه بندی با استفاده از تکنیک های پارتیشن بندی
· تکنیک های خوشه بندی سلسله مراتبی
· تکنیک های خوشه بندی متراکم
· تکنیک های خوشه بندی عمومی
-1-2 خوشه بندی با استفاده از تکنیک پارتیشن بندی
یکی از تکنیک های دسته بندی داده های بزرگ پارتیشن بندی آن ها است که دارای حالات مختلفی می باشد. تی کینگ هی[4] 5 یادگیری ماشین حداکثر 6 - فاکتور گیری ماتریس غیر منفی - را برای شبکه عصبی پیشرو7 پیشنهاد کرده اند. آنها از تکنیک های ELM برای مشکلات خوشه بندی استفاده کرده اند که نتایج بهتری نسبت به الگوریتم های قدیمی و غیر مبتنی بر Mercer-kernel تولید می کنند. آنها از سه پایگاه داده ی مختلف استفاده می کنند. دو پایگاه داده ماشین دانشگاه و سوم متن اسناد می باشد.
elm nmf و ELM k-mean، هر دو برای مجموعه داده های بزرگ پایدار هستند و پیاده سازی آنها ساده و کارآمد است. در [5]، دو الگوریتم برای خوشه بندی مورد بحث قرار گرفته است. نویسنده k-MEANS افزایشی را بررسی کرده است که داده های عددی را خوشه بندی می کند. الگوریتم K- MEANS اصلاح شده، داده های قطعی را دسته بندی می کند در حالیکه برای داده های قطعی و عددی ترکیبی، k نمونه اولیه تعریف شده است. هر سه الگوریتم کارآمد هستند و هزینه ی تابع دسته بندی را کاهش می دهند.
این الگوریتم ها در کمترین تکرار همگرا می شوند و پیچیدگی آن ها کاهش می یابد.[6] گروه گارش کریشنا سامی8 هوش گروهی اصلاح شده با پیاده سازی عملگر جهش در هوش گروهی - CI - را ارائه کرده اند تا بر موضوع کیفیت و سرعت همگرایی غلبه کنند. آنها الگوریتم K-MCL ترکیبی را برای خوشه بندی داده پیشنهاد کرده اند که ترکیبی از K-means و MCI است و مزایای هر دو را دارد. الگوریتم ارائه شده قابل اطمینان و کارآمد است و کیفیت خوبی برای راه حل ها فراهم کرده است و سرعت همگرایی بهتری نسبت به سایر تکنیک های خوشه بندی دارد. تست کارایی روی شش مجموعه ی داده استاندارد از انبار داده یادگیری ماشین UCI انجام شده است.[7]
-2-1 -2 تکنیک های دیگر پارتیشن بندی
ایشاک سیدا و همکاران9 یک روش فرا ابتکاری جدید برای خوشه بندی داده پیشنهاد کرده اند که مبتنی بر بهینه سازی جستجوی تپه نوردی10 است تا از ناسازگاری K-mean اجتناب کند. ویژگی های اصلی جستجوی تپه نوردی این است که پیاده سازی آن آسان است و کارایی بهره وری محاسباتی خوبی دارد. الگوریتم پیشنهادی توان متد جدید را بهبود می بخشد تا بهترین مقادیر را تعیین کند. آزمایش روی چهار مجموعه از انبار داده یادگیری ماشین UCI انجام شده است. یو جی آگ11 و همکاران یک الگوریتم بهینه سازی سراسری برای مشکلات محاسباتی مقیاس بزرگ ارائه کرده است.[5] این الگوریتم یک نوع خوشه بندی مبتنی بر بهینه سازی ازدحام ذرات به صورت موازی می باشد. یک الگوریتم جدید مبتنی بر متد گروهی است و برای مشکل متغیر پیوسته بسیار مفید است.
این الگوریتم هم چنین قابلیت موازی شدن را دارد. الگوریتم بهینه سازی ازدحام ذرات موازی زمان محاسباتی کمتری دارد و کیفیت خوشه بندی بهتری را ارائه می کند.[8] اثر بخشی قویتر این الگوریتم روی مجموعه داده های بزرگ، ارزیابی شده است. گروه تحقیقاتی موساوو12 الگوریتم خوشه بندی PFClust برای یافتن تعداد بهینه ی خوشه ها به صورت خودکار بدون هیچ دانش قبلی از تعداد خوشه، ارائه کرده اند. PFClust به ماتریس شباهت وابسته است و نسبت به مشکلات تولید شده چند بعدی ایمن می باشد.[9] زمان اجرای PFClust بهتر است و خوشه بندی حاصل کیفیت خوبی دارد. کارایی PFClust روی مجموعه داده با ابعاد بالا ارزیابی شده است.
-2-2 تکنیک های خوشه بندی سلسله مراتبی
هانگ یو و همکاران 13 یک متد خودکار کارآمد برای برخورد با مشکلات تعیین تعداد خوشه، ارائه کرده اند. این متد تعمیم مدل مجموعه بزرگ تئوری- تصمیم می باشد و براساس محاسبه خطر توسط توابع خسارت و قابلیت امکانپذیری طراحی شده است.[7] نویسنده یک الگوریتم خوشه بندی سلسله مراتبی ارائه کرده است که ACA-DTRS نامیده می شود. - الگوریتم خوشه بندی خودکار مبتنی بر - DTRS که بعد از یافتن تعداد کامل خوشه ها، به صورت خودکار متوقف می شود. آنها هم چنین FACA-DTRS را پیشنهاد کرده اند که نسخه ی سریعتر ACA-DTRS از نظر پیچیدگی می باشد. هر دو الگوریتم از نظر ارزش زمانی کارآمد هستند.[10] کارایی روی مجموعه داده ی واقعی و ترکیبی ارزیابی شده است.
بوزا ناگی و همکاران یک روش برای کاهش فضای ذخیره سازی برای داده های tick که به سرعت در حال افزایش هستند، پیشنهاد کرده اند. داده های tick توسط ویژگی های خوشه بندی به ماتریس داده کوچکتر تجزیه شده است که از الگوریتم خوشه بندی جدید، خوشه بندی متراکم سلسله مراتبی بهینه14 برای ذخیره سازی استفاده می کند. با استفاده از این تکنیک، پرس و جوها می توانند به صورت کارآمد اجرا شوند. آنها همچنین SOHAC سریع را برای بالا بردن زمان اجرا ارائه کرده اند. این الگوریتم براساس تکنیک محدوده پایین تر می باشد، بنابراین می تواند روی داده های tick با ابعاد بالا اعمال شود.[11]
کارایی این الگوریتم روی سه مجموعه داده ی واقعی که توسط بانک سرمایه گذاری تهیه شده، ارزیابی شده است. گروه وانگ شا15 یک الگوریتم خوشه بندی جدید ارائه کرده که خوشه بندی مشبک سلسله مراتبی با استفاده از فیلد داده 16نامیده می شود. در این روش، مشبک های سلسله مراتبی تقسیم می شوند و مجموعه داده های بزرگ را در زیرمجموعه های سلسله مراتبی شان محدود می کنند تقسیم، محدوده ی جستجو را به مراکز خوشه بندی ها محدود می کند و فضای داده برای تولید فیلد داده به حداقل می رسد.[10] خوشه بندی مشبک سلسله مراتبی با استفاده از فیلد داده پایدار است و با بهترین سرعت اجرا می شود که کارایی خوشه بندی روی مجموعه داده های کامپیوتری وسیع بهبود می دهد.
گروه نیم 17 یک متد خوشه بندی مبتنی بر مدل ارائه کرده است که SWIFT - تکنیک خوشه بندی وزن دار مقیاس پذیر - برای مجموعه داده با سایز بزرگ و ابعاد بالا نامیده می شوند. این متد در سه فاز شامل نمونه برداری وزن دار تکرار شونده، تقسیم چند کیفیتی، ادغام حفظ کننده تک کیفیتی برای مقیاس کردن خوشه بندی مبتنی بر مدل مربوط به مجموعه داده بزرگ با ابعاد بالا، می باشد. این الگوریتم اساساً برای جریان سایتومتری می باشد و جمعیت سلولی نادر را می یابد و مجموعه داده های بزرگ را به صورت کارآمدتر در مقایسه با روش های قدیمی مقیاس می کند. این متد برای وظیفه ی پاسخگویی ایمن و مقیاس مجموعه داده های FC خیلی بزرگ، مفید می باشد و همچنین قابلیت تعیین جمعیت نادر خیلی زیاد دارد.[9]
-3-2 تکنیک های خوشه بندی مبتنی بر تراکم
امینه امینی و هادی صبوحی[9]18 الگوریتم خوشه بندی ارائه کرده است که جریان DMM برای جریان داده ی بلادرنگ نامیده می شود.
