بخشی از مقاله
چکیده
خوشهبندی، یکی از روشهای معمول کار با دنیای کلانداده است. از الگوریتمهای خوشهبندی که به صورت گستره نیز بهکار میرود، الگوریتم K-means است اما در مواردی که برای پردازش دادههای ابعادبالا استفاده میشود، پیچیدگی زمانی آن بیش از حد بالاست. الگوریتمهای خوشهبندی بر اساس پلتفرم هدوپ، پیچیدگی زمانی و فضایی کمتری دارند و همینطور دارای مقیاسپذیری خوبی در پردازش دادههای حجیم میباشند. کتابخانه منبعبازِ ماهوت، کتابخانهی الگوریتمهای یادگیری ماشین است.
در این مقاله قصد داریم به منظور کاهش زمان پردازش خوشهبندی دادههای ابعادبالا، الگویی ترکیبی در چارچوب ماهوت بر اساس مدل Hadoop- MapReduce و با استفاده از آنتروپی ارائه دهیم. این الگوی ترکیبی جدید با افزودن آنتروپیِ وزن، الگوریتم K-means را گسترش داده و عملکرد آنرا در خوشهبندیِ دادههای ابعاد بالا در زیر فضاها بهبود داده است. الگوی ترکیبی با مدل پردازشی MapReduce طراحی شده، و بر روی اکو سیستم هدوپ با استفاده از ماهوت بر روی مجموعهداده Reuters-21578 پیادهسازی و اجرا شده است.
-1 مقدمه
در دادههای ابعادبالا - High -Dimensional Data - ، خوشههای اشیاء اغلب در زیرفضاهاو نَه در کل فضا وجود دارند. خوشهبندی دادههای ابعادبالا با مشکل پراکندگی مواجه است. خوشهبندی دادههای پراکنده و ابعادبالا - High-Dimensional Sparse Data - ، این نوع خوشهبندی به خوشهبندی نرم زیرفضا - Soft Subspace - Clustering اشاره دارد. هدف خوشهبندی زیرفضا این است که خوشهها را از زیرفضاهای داده به جای کل فضای داده پیدا کند. در خوشهبندی زیرفضا، هر خوشه مجموعهای است از اشیا که توسط زیرمجموعهای از ابعاد مشخص شده است و خوشههای مختلف در زیرمجموعههای مختلفی از ابعاد شکل گرفته اند.[5]
چالش اصلی خوشهبندی زیرفضا، معین نمودن همزمان هم عضویت اشیاء در خوشه و همینطور تعیین زیرفضاهای هر خوشه است. عضویت اشیاء در خوشهها توسط شباهت بین اشیاء که با توجه به زیرفضاها اندازهگیری میشود، تعیین میگردد.[5] با توجه به محدودیتها و زمانبر بودن خوشهبندی دادههای ابعادبالا، اگر بخواهیم الگوریتم K-means را بهمنظور خوشهبندی دادههای ابعادبالا و کلان بکار بریم دچار چالشها و مشکلاتی خواهیم شد.[7]
الگوریتم [6] EWKM - Entropy Weighting K-means - ، الگوریتمی از خانوادهی K-means ، برای خوشهبندی نرم دادههای ابعادبالا در زیرفضاها پیشنهاد شده است. در این الگوریتم، برایهر بُعد در هر خوشه وزنی محاسبه شده و مقادیر وزنها برای شناسایی زیرمجموعههای ابعاد مهم که خوشههای مختلف را دسته بندی کردهاند، استفاده شده است. این مورد با اضافه نمودن آنتروپیِ وزن به فرآیند خوشهبندی الگوریتم K-means بدست آمده است. در مقایسه با الگوریتم K-means، الگوریتم EWKM در خوشهبندی دادههای ابعادبالا نتایج رضایت بخشی را دارد.[6]
امروزه اصطلاح "کلانداده" برای توصیف دادههای حجیم و بسیار بزرگ استفاده میشود. در سال2011، حجم دادهی تولید شده و کپی شده در جهان 1,8 زتا بایت بوده است که در 5 سال پیش رو این مقدار نُه برابر می شود. مفهوم کلانداده - BigData - به طور عمده برای توصیف مجموعهدادههای بسیار حجیم اطلاق می شود که توسط نرمافزارها، سختافزارها و ابزارهای معمول حوزه فناوری اطلاعات قابل پردازش، مدیریت، اشتراکگذاری، جستجو، ذخیره، تجزیه و تحلیل، تجسم و درک نیست. مقیاس کلانداده، به طور مداوم در حال رشد از محدوده چندین ترابایت به چندین پتابایت، اگزابایت و زتابایت است و نرخ رشد آن نمایی است .[8]
در سالهای اخیر، فنآوری محاسبات ابری توجه زیادی از محققان در حوزه فناوری اطلاعات، صنعت و آکادمیک را برای حل مسائل گوناگون مرتبط با کلان داده، به خود جلب کرده است. یکی از فنآوریهای محاسبات ابری که امروزه در مسائل مختلف کاربرد دارد، تکنیک MapReduce شرکت گوگل است که با سیستم فایل گوگل - GFS - معرفی شد. پارادایم MapReduce به دلیل ویژگیهایی چون سادگی، مقیاسپذیری و تحملپذیری خطا به مدل برنامهنویسی محبوب در جامعه محاسبات ابری تبدیل شده است.[9]
چندین چارچوب متنباز برای در دسترس قراردادن پارادایم MapReduce منتشر شدهاند. آپاچی هدوپ [19]، برترین چارچوب متنباز مدل MapReduce است که امکان پردازش توزیع شده بر روی مجموعههای بزرگ روی خوشههایی از کامپیوترهای تجاری را فراهم میکند. اجزای اصلی اکو سیستم هدوپ از هدوپ مشترک ، سیستم فایل توزیع شدهی هدوپ - - Hadoop Distributed File System ، هدوپ یارن و Hadoop-MapReduce تشکیل شده است.[10] آپاچی ماهوت [20] - Apache Mahout - ، کتابخانه منبع بازِ مقیاس پذیرِ مبتنی بر MapReduce است که بر خوشهبندی، طبقهبندی و موتورهای پیشنهاددهنده تمرکز دارد. ماهوت محیطی برای ایجاد الگوریتمهای یادگیری ماشین به صورت توزیع شده میباشد.[1]
مطالعات و تحقیقات انجام شده نشان میدهد که الگوریتمهای خوشهبندی بر اساس پلتفرم هدوپ، پیچیدگی زمانی و فضایی کمتری دارند و همینطور دارای مقیاسپذیری خوبی میباشند. در مقاله [11]، زاولیسو - Xiaoli Cui - و همکارانش روش جدیدی برای بهینهسازی الگوریتم خوشهبندی Kmeans با استفاده از مدل MapReduce ارائه دادهاند. الگوریتم ترکیبی پیشنهادی وابستگی به تکرار را حذف میکند و هزینه محاسباتی الگوریتم سنتی K-means را کاهش میدهد. در این مقاله، بر بهبود سرعت خوشهبندی مجموعه دادههای بزرگ با استفاده از MapReduce تمرکز شده است. نتایج تجربی بر روی مجموعه دادههای واقعی و غیر واقعی که با حجم بسیار بزرگ نیز بودند، نشان میدهد که الگوریتم بهینهای که ارائه شده، کارآمد میباشد و در مقایسه با الگوریتمهای Kmeans، Kmean و K-means++ بهتر اجرا می شود.[11]
یوجیژو - Yujie Xu - و همکارانش [12]، در مقاله خود الگوریتم Mapreduce Scalable Kmeans++ ONR را پیشنهاد دادهاند. روش OnR موجب صرفه جویی در هزینه I/O می شود و به شدت زمان اجرا را کاهش میدهد. نتایج تجربی نشان میدهد که OnR موجب بهبود Mapreduce Scalable Kmeans++ در جنبههای هزینه I/O و زمان اجرا میشود. در این مقاله روش Oversampling و Refing پیشنهاد شده است که روشی کارآمد برای الگوریتم با MapReduce می باشد. در این روش برای تکمیل task انتخاب مراکز و محاسبه هزینه خوشه در هر دور تنها از یک MR job استفاده کرده و موجب کاهش هزینه I/O شده است. و همچنین در مقایسه با Scalable Kmeans++ نتایج تجربی نشان میدهد که بدون افزایش هزینه شبکه، روش OnR هزینه I/O را تا حد زیادی کاهش میدهد.[12]
در مقاله[13]، آمرش کومار - - Amresh Kumar و همکارانش، تجزیه و تحلیل برنامههای MapReduce و الگوریتم خوشهبندی موازی K-means در خوشه هدوپ با استفاده از مدل MapReduce را ارائه نمودهاند. نویسندگان بیان داشتهاند که اگر تعداد نودها افزایش یابد زمان اجرا کاهش مییابد. در اینمقاله اساساً مطالعه تحقیقاتی از برنامههای کاربردی MapReduce صورت پذیرفته است و همچنین به منظور بررسی و اعتبارسنجی مدل برنامه نویسی MapReduce برای الگوریتم موازی Kmeans بر خوشه هدوپ آزمایشاتی انجام شده است. عملکرد مدل MapReduce با توجه به زمان اجرا و تعداد نودها نشان داده شده است. همچنین تأیید شده و معتبر است که در مدل MapReduce اگر تعداد نودها افزایش یابد زمان اجرا کاهش می یابد. به این ترتیب، نشان داده شده است که PKmeans به خوبی و موثر عمل می کند و نتایجکاملاً به اندازه خوشه Hadoop بستگی دارد.[13]
محققان الگوریتمهای بهبودیافتهای را برای غلبه بر معایب الگوریتم K-means با استفاده از مدل MapReduce طراحی و ارائه دادهاند، که مختصر مروری بر تعدادی از این مطالعات داشتیم. اندک تحقیقاتی بر بهبود عملکرد الگوریتم K-means در خوشهبندی دادههای ابعادبالا براساس مدل MapReduce در اکو سیستم هدوپ انجام شده است. در این پژوهش با استفاده از مدل MapReduce و ایده الگوریتم EWKM ، الگوی ترکیبی جدیدی برای خوشهبندی دادههای ابعاد بالا و حجیم ارائه شده و بر روی اکو سیستم هدوپ - ماهوت طراحی و پیادهسازی شده است.
-2 الگوریتم K-means
الگوریتم K-means با وجود برخورداری از مزایایی همچون سادگی، آسان بودن قابلیت پیادهسازی، سرعت بالا و مناسب بودن برای مجموعه دادههای بزرگ، چالشهایی نیز دارد. از معایب آن میتوان نیاز داشتن به تعیین تعداد خوشهها - - K از ابتدا، حساس بودن به دادههای پرت، وابستگی نتایج نهایی به مقداردهی مراکز اولیه و تعداد خوشهها، گیرکردن الگوریتم در بهینه محلی و همگرایی زودرس را نام برد. الگوریتم K-means از سادهترین الگوریتمهای یادگیری بدون نظارت است که در زمینههای مختلفی از جمله پردازش تصویر، شناسایی الگو، بازیابی اطلاعات، تشخیص گفتار و دادهکاوی بهکار میرود .[14]
الگوریتم K-means از یک شیوهی ساده برای بخشبندی یک مجموعهداده به یک تعداد از پیش تعیین شده، - - K خوشه استفاده میکند. ایده اصلی، تعریف K مرکز برای هر یک از خوشهها است. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلفی را در پی دارد. مرحلهی بعد اختصاص هر نمونه به نزدیکترین مرکز است. وقتی همه نقاط به مرکزی که داریم اختصاص داده شوند، مرحله اول تمام شده و یک خوشهبندی اولیه انجام شده است. در این مرحله نیاز است که K مرکز جدید برای خوشههای مرحلهی قبل محاسبه شود. بعد از تعیین K مرکز جدید،مجدداً دادهها به مراکز مناسب جدید تخصیص داده میشود. این مرحله تا حدی تکرار میشود تا مراکز K دیگر تغییر نکند. برای اندازهگیری مشابهت و نزدیکی نقاط از فاصلهی اقلیدسی ، از رابطه - 1 - بهعنوان تابع هدف K-means استفاده میشود:[15] که در رابطه - 1 - ، K تعداد خوشهها، n تعداد آبجکتها، X i - j - داده -iام در خوشه -jام و Cj مرکز خوشه -jام میباشد.
-1-2 چالشهای الگوریتم K-means
برخی از چالشهای الگوریتم K-means به شرح ذیل میباشد:
. نتیجه یکسانی با هر یک از اجراها حاصل نمیشود چرا که جواب نهایی به انتخاب خوشههای اولیه وابستگی دارد.
. اگر در تکرار از الگوریتم تعداد دادهها متعلق به خوشهای صفر شد، راهی برای تغییر و بهبود ادامهی روش وجود ندارد.
. این الگوریتم نیاز دارد تعداد خوشها از ابتدا مشخص باشد. امّا در مسائل تعداد خوشهها مشخص نمیباشد.[14]
. در مواردی که برای پردازش دادههای عظیم و بزرگ استفاده میشود پیچیدگی زمانی آن بالاست و بازدهی آن پائین میشود.[11]
. در مواردی که برای خوشهبندی زیرفضاهای دادههای ابعادبالا استفاده میشود، عملکرد این الگوریتم با تنگنا مواجه میشود. شایان ذکر است که معمولاً این دادهها دارای مشکل پراکندگی میباشند.[6]
در بخش مشکلات الگوریتم K-means، به مشکل خوشه بندی در زیرفضاهای دادههای بزرگ و ابعاد بالا با الگوریتم K-means اشاره داشتیم. الگوریتمی از خانواده K-means که خوشهبندی در زیرفضاهای دادههای بزرگ با ابعادبالا که دارای مشکل پراکندگی نیز هستند، را تا حد ممکن حل کرده است، الگوریتم EWKM میباشد.[6] در این الگوریتم تابع ارزیابی الگوریتم K-means با اضافه کردن آنتروپی وزن تغییر داده شده است، بهطوری که همزمان با به حداقل رساندن پراکندگی در داخل خوشه و در عین حال به حداکثر رساندن وزن آنتروپی منفی بتوان ابعاد بیشتری را برای شرکت در شناسایی خوشه ها برانگیخت .
با این مورد می توان از مشکل شناسایی خوشه ها توسط تعداد ابعاد کمتر در داده های پراکنده جلوگیری نمود.در مقایسه با الگوریتم K-means ، الگوریتم EWKM در خوشه بندی داده های ابعاد بالا نتایج رضایت بخشی را دارد.[6] در الگوریتم EWKM، در فرآیند خوشه بندی، به طور همزمان برای تحریک ابعاد بیشتر در تعیین خوشهها پراکندگی داخلی خوشه کاهش داده شده و نیز آنتروپیِ منفیِ وزن افزایش داده شده است. این مورد میتواند از مشکل شناسایی خوشه ها با ابعاد کمتر در دادههای پراکنده جلوگیری کند. تابع هدف الگوریتم EWKM به صورت رابطه - - 2 میباشد:[6] در رابطه 2 - - ، k تعداد خوشهها، n تعداد آبجکتها، m تعداد بُعدها، lj درجه عضویت آبجکتj -ام عضویی از خوشه lمُ-ا، li وزن برایامُiینبُعد در l امُ-ین خوشه،x jiمقدار بُعدi -ام آبجکت j -ام، liمقدار i -امین مؤلفه از مرکز L -امین خوشه میباشند. الگوریتم EWKM دارای سه فاز اصلی میباشد: فاز اول بخشبندی دادهها و محاسبه Partition Matrix، فاز دوم محاسبه وزن بُعدها و فاز سوم محاسبه مراکز خوشهها. به منظور بخشبندی دادهها محاسبه، W ، از رابطه - 3 - استفاده میکند:
