بخشی از مقاله
چکیده
الگوریتم K-means از پرکاربردترین الگوریتمهای خوشهبندی است اما در مواردی که برای پردازش دادههای حجیم استفاده میشود، پیچیدگی زمانی آن بیش از حد بالاست. الگوریتم Fuzzy K- means با افزودن رویکرد فازی، الگوریتم K-means را گسترش داده و عملکرد آنرا در خوشهبندی بهبود داده است. تحقیقات انجام شده نشان میدهد که الگوریتمهای خوشهبندی بر اساس پلتفرم هدوپ، پیچیدگی زمانی و فضایی کمتری دارند و همینطور دارای مقیاسپذیری خوبی میباشند. تعدادی از تحقیقات، الگوریتمهای خوشهبندی را بر اساس هدوپ طراحی و تست کردهاند. با این حال اندک تحقیقاتی بر اساس پلتفرم ماهوت اجرا و تست شده است. کتابخانه منبعبازِ ماهوت، کتابخانهی الگوریتمهای یادگیریماشین است. الگوریتمهای ماهوت بر اساس MapReduce هستند. استفاده از پلتفرم هدوپ و ماهوت پردازش مجموعهدادههای بزرگ و عظیم را بهبود میدهد و لازم است با توجه به مزایای کتابخانه ماهوت، تحقیقات بیشتری در زمینه اجرای موازی الگوریتمهای خوشهبندی صورت پذیرد. در این مقاله قصد داریم الگویی ترکیبی برای کاهش زمان اجرای الگوریتم خوشهبندی K-means مبتنی بر رویکرد فازی در چارچوب ماهوت بر اساس Hadoop - Mapreduce ارائه دهیم.
-1 مقدمه
امروزه در عصر انفجار داده در جهان، حجم داده در زمینههای مختلف بطور چشمگیری در حال افزایش است و با دادههایی بسیار حجیم مواجه هستیم. همین مسئله خوشهبندی دادههای حجیم را به مسئلهای چالش برانگیز تبدیل کرده است.[6]Hadoop بهعنوان مدل محاسباتی توزیعشده، پردازش کلانداده را برای محاسبات ابری تحقق بخشیده است.[19] تکنیک MapReduce، بهعنوان محبوبترین چارچوب موازی در محاسبات ابری، راهحلی موثر برای مدیریت دادههای عظیم است. و بهدلیل سادگی، مقیاسپذیری بالا و هزینه کم توجه زیادی را در جامعه محاسبات ابری به خود جلب کرده است.[8]Hadoop، مدل برنامه نویسی و چارچوب نرم افزاری متنباز است که با استفاده از سیستم فایل توزیع شدهاش - HDFS - ، قادر به انجام سریع پردازش دادههای حجیم روی تعداد زیادی نودهای پردازشی خوشههای بزرگ می باشد.
در واقع Hadoop محیطی برای اجرای برنامههای MapReduce ای و سیتم فایل توزیعشدهی خود - HDFS - ، سایر پروژههای فرعی و نرمافزارهای سطح بالا را فراهم می کند.[7,13]Apache Mahout،کتابخانه منبع بازِ مقیاس پذیرِ مبتنی بر MapReduce است که بر خوشهبندی، طبقهبندی و موتورهای پیشنهاددهنده تمرکز دارد. Mahout محیطی برای ایجاد الگوریتمهای یادگیریماشین به صورت توزیعشده میباشد.[1]از سویی دیگر حجم بزرگ اطلاعات خوشه بندی داده های حجیم را به مسئلهای چالش برانگیز تبدیل کرده است. الگوریتم Kmeans ازمحبوبترین الگوریتمهای خوشهبندی است اما در مواردی که برای پردازش دادههای عظیم و بزرگ استفاده میشود، پیچیدگی زمانی آن بیش از حد بالاست و بازدهی آن پائین میشود.[21] الگوریتم K-means میتواند با چارچوب MapReduce ترکیب شود و الگوریتم موازی K-means پیاده سازی شود.
الگوریتم موازی K-means بهبود یافته، میتواند سرعت پردازش بالاتر و ثبات بیشتری نسبت به الگوریتم سنتی K-means بدست آورد .[10,11]K-means سریع و ساده است . با این حال K-means خوشههای یکنواختی را اتخاذ میکند و نیاز به دانستن تعداد خوشهها از قبل دارد. یکی دیگر از ویژگیهای مهم K-means این مورد است که یک شیء - آبجکت - را به یک خوشه خاص اختصاص می دهد. با این حال، در دنیای واقعی یک شیء ممکن است نزدیک به بیش از یک خوشه باشد. خوشهبندی K-means بعنوان خوشهبندی سخت شناخته شده است. برای غلبه بر محدودیت های K-means، الگوریتم Fuzzy K- meansکه بعنوان رویکرد خوشهبندی نرم نیز شناخته شده، معرفی شده است.
اگر چه هر دو از الگوریتمهای یادگیری بدون نظارت می باشند، تفاوت قابل توجه این است که Fuzzy K- means به اندازه کافی انعطاف پذیر است و می تواند اجازه دهد که یک شیء متعلق به بیش از یک خوشه باشد. با توجه به کیفیت خوشهها Fuzzy K-means در برنامه های کاربردی دنیای واقعی بهتر از Kmeans کاربرد دارد.[22]با توجه به محدودیت ها و زمانبر بودن خوشه بندی دادههای بزرگ، اگر بخواهیم الگوریتم K-means را بهمنظور خوشهبندی دادههای کلان بکار بریم دچار چالشها و مشکلاتی خواهیم شد. در این مقاله سعی نمودهایم به منظور کاهش زمان خوشهبندی الگوریتم خوشهبندی K-means در پردازش دادههای بزرگ، الگویی ترکیبی مبتنی بر رویکرد فازی Fuzzy K- means در چارچوب Mahout بر اساس MapReduce ارائه دهیم.
-2 الگوریتم خوشهبندی K-means
الگوریتم K-means کاربردهای بسیاری در حیطههای مختلف علمی و صنعتی دارد. الگوریتم K-means با وجود برخورداری از مزایایی همچون سادگی، آسان بودن قابلیت پیادهسازی، سرعت بالا و مناسب بودن برای مجموعه دادههای بزرگ، چالشهایی نیز دارد. از معایب آن میتوان نیاز داشتن به تعیین تعداد خوشهها - - K از ابتدا، حساس بودن به دادههای پرت، وابستگی نتایج نهایی به مقداردهی مراکز اولیه و تعداد خوشهها، گیرکردن الگوریتم در بهینه محلی و همگرایی زودرس را نام برد. الگوریتم K-means از سادهترین الگوریتمهای یادگیری بدون نظارت است که در زمینههای مختلفی از جمله پردازش تصویر، شناسایی الگو، بازیابی اطلاعات، تشخیص گفتار و دادهکاوی بهکار میرود.
خوشهبندی در دادهکاوی برای کشف اطلاعات و ساختار جدید از دادههای موجود بهکار میرود.[12,14]الگوریتم K-means از یک شیوهی ساده برای بخشبندی یک مجموعهداده به یک تعداد از پیش تعیین شده، - - K، خوشه استفاده میکند. ایده اصلی، تعریف K مرکز برای هر یک از خوشهها است. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلفی را در پی دارد. بنابراین بهترین انتخاب قراردادن مراکز در فاصله هرچه بیشتر از یکدیگر است. مرحلهی بعد اختصاص هر نمونه به نزدیکترین مرکز است. وقتی همه نقاط به مرکزی که داریم اختصاص داده شوند، مرحله اول تمام شده و یک خوشهبندی اولیه انجام شده است.
در این مرحله نیاز است که K مرکز جدید برای خوشههای مرحلهی قبل محاسبه شود. بعد از تعیین K مرکز جدید، مجدداً دادهها به مراکز مناسب جدید تخصیص داده میشود. این مرحله تا حدی تکرار میشود تا مراکز K دیگر تغییر نکند.این الگوریتم همواره به دنبال کمینه کردن تابع هدف است. الگوریتم K-means با وجود سادگی یک روش پایه برای بسیاری از الگوریتمهای خوشهبندی دیگر مانند خوشهبندی فازی است.[12]برای اندازهگیری مشابهت و نزدیکی نقاط از فاصلهی اقلیدسی ، از رابطه - 1 - بهعنوان تابع هدف K-means استفاده میشود:[12]که در آن K تعداد خوشهها، n تعداد آبجکتها، - Xi - j داده -iام در خوشه -jام و Cj مرکز خوشه -jام میباشد.
-1-2 مشکلات الگوریتم K-means
علیرغم اینکه الگوریتم K-means در مسائل مختلف، بسیار استفاده میشود اما دارای مشکلاتی است. به برخی از این موارد در ذیل اشاره میکنیم:
. نتیجه یکسانی با هر یک از اجراها حاصل نمیشود، چرا که جواب نهایی به انتخاب خوشههای اولیه وابستگی دارد.
. روالی مشخص برای محاسبه اولیهی مراکز خوشهها وجود ندارد.
. اگر در تکرار از الگوریتم تعداد دادهها متعلق به خوشهای صفر شد، راهی برای تغییر و بهبود ادامهی روش وجود ندارد.
. این الگوریتم نیاز دارد تعداد خوشها از ابتدا مشخص باشد. امّا معمولاً در مسائل و کاربردهای زیادی تعداد خوشهها مشخصنمیباشد.
. در مواردی که برای پردازش دادههای عظیم و بزرگ استفاده میشود پیچیدگی زمانی آن بالاست و بازدهی آن پائین میشود.[15]
برخی از دادهها به خوشههای متعدد وابستگی دارند و تنها متعلق به یک خوشه نیستند. بر اساس همین ایده نسخه فازی الگوریتم K-means ارائه شده است.الگوریتم Fuzzy k- means، ابرهای کروی از نقاط دادهها را در یک فضای nبُعدی شناسایی میکند. این خوشهها بهطور مفروض هم اندازه هستند. هر خوشه با مرکزش نمایش داده میشود. در انتخاب مرکز خوشه از مقدار میانگین استفاده میشود. برای محاسبه مرکز خوشه، مجموع درجات عضویت هر نقطه داده به توان m در خودش به حاصلضرب توان m درجه عضویتها تقسیم میشود. در تعیین فاصله، بهعنوان مثال از فاصله اقلیدسی بین یک نقطه و یک نمونه داده میتوان استفاده نمود.[22]
-4 کلانداده - Big Data -
امروزه اصطلاح "کلانداده" برای توصیف دادههای حجیم و بسیار بزرگ استفاده میشود. در سال2011، حجم داده ی تولید شده و کپی شده در جهان 1,8 زتا بایت بوده است.[5] در واقع، بهدلیل افزایش چشمگیر تکنولوژی اشیاء - IoT - ، تکنولوژیهای عملیات - OT - ، ماشینها، ابزار و وسایل نقلیه که با استفاده از سنسورها قادر به ایجاد ارتباط و صحبت با یکدیگر شدند، همگی حجم بسیار بزرگی از دادهها را بهطور خودکار تولید میکنند. بر اساس مطالعات شرکت بینالمللی داده - IDC - ، پیش بینی کرده است که تا سال 2020 بیشتر از 40 زتابایت داده خواهیم داشت.[16]کلانداده، مفهومی است که به مجموعه دادههایی اطلاق میشود که مدیریت، کنترل و پردازش آنها فراتر از توانایی ابزارها و تکنولوژی معمول کنونی حوزه فناوری اطلاعات و کامپیوتر است. مقیاس کلان داده، به طور مداوم در حال رشد از محدوده چندین ترابایت به چندین پتابایت، اگزابایت و زتابایت است و نرخ رشد آن نمایی است. دادههای تولیدی از شبکههای حسگر، شبکههای اجتماعی، متون و اسناد اینترنتی، مدارک پزشکی، آرشیو عکس و ویدئو و غیره که در مقیاسی بسیار بزرگ هستند، نمونههایی از منابع تولید کلانداده میباشند.[17,18]
MapReduce در اصل توسط گوگل بهعنوان یک مدل برنامهنویسی توزیعشده که خوشههای سرورهای عظیم از آن برای پردازش مجموعهدادههای بسیار بزرگ استفاده میکنند، معرفی شد.[23] این مدل ویژگیهایی از جمله موازیسازی اتوماتیک، توازن بار، هزینهسازی انتقال دیسک و شبکه و ادارهی قدرتمند در هنگام شکست ماشین را دارد. MapReduce با شکستن یک برنامه بزرگ به بخشهای کوچکتر، پردازش هر بخش را به صورت موازی و سپس ترکیب نتایج برای تولید، نتیجهی نهایی کار میکند.[20]MapReduce در بالای یک سیستم فایل خاص مانند سیستم فایل گوگل - GFS - یا سیستم فایل هدوپ - HDFS - اجرا میشود. ابتدا داده بارگذاریو معمولاً به بخشهای 64MB بخشبندی میشود. یکی از ویژگیهای کلیدی MapReduce این است که ترتیب ذخیرهی دادهها متناسب با پردازش داده است و بهعنوان یک مدل برنامهنویسی توزیعشده مزایایی در مقایسه با رویکردهای سنتی انتقال داده برای محاسبات دارد.
گسترشپذیری، قابلیت اطمینان، تحملپذیری خطا، سادگی و کارایی از جمله مزایای آن میباشد.تمامی این مزایامشخصاً مرتبط با محاسبات ابری میباشند که در آن پردازش مقادیر کلانداده با استفاده از منابع توزیعشده وظیفهی اصلی است. در واقع MapReduce مدل برنامهنویسی که در محیطهای محاسبات ابری برای پردازش موازی مجموعهدادههای بزرگ بسیار کاربرد دارد. MapReduce از توابع Map و Reduce تشکیل شده است که برگرفته از زبانهای برنامهنویسی چون لیسپ است. تابع Map برای تولید لیستی از جفتهای کلید/مقدار میانی استفاده میشود و تابع Reduce تمام مقادیر میانی مرتبط با یک کلید میانی را ترکیب میکند.[20]
هدوپ توسط داگ کاتینگ خلق شده است. در خصوص نام هدوپ باید گفت که مخفف عبارت خاصی نیست و این نامی است که پسرش بر روی عروسک فیل خود که زرد رنگ بود، گذاشته بود.[2] هدوپ امروزه توسط بسیاری از شرکتها از جمله فیسبوک، توییتر ، آمازون و مایکروسافت و غیره استفاده میشود.[6] از جمله مزایای Hadoop میتوان به دسترسپذیری، استحکام، مقیاسپذیری و سادگی آن اشاره کرد.[20]چندین چارچوب متنباز برای در دسترس قراردادن پارادایم MapReduce منتشر شدهاند. Apache Hadoop برترین چارچوب متنباز مدل MapReduce است که امکان پردازش توزیع شده بر روی مجموعههای بزرگ روی خوشههایی از کامپیوترهای تجاری را فراهم میکند.[20]
