مقاله بررسی داده کاوی توزیع شده با الگوریتم k - means

بخشی از مقاله

بررسي داده کاوي توزيع شده با الگوريتم k-means
چکيده
اکثر الگوريتم هاي خوشه بندي نياز به داده هاي متمرکز دارند ، اما اين الگوريتم ها با توسعه اينترنت و در برخورد با داده هاي توزيع شده ، با دو چالش روبرو شدند. اول ، حجم داده هاي توليد شده حتي براي ابرکامپيوترها هم خيلي زياد شده است . دوم ، داده ها در چندين مکان ذخيره شده اند و متمرکز کردن آنها در يک جا بسيار پرهزينه خواهد بود، هم چنين محدوديت پهناي باند و حريم شخصي نيز از نگراني ها و موانع متمرکز سازي داده ها مي باشد. به همين دليل براي حل اين مشکلات ، داده کاوي توزيع شده يک حوزه تحقيقاتي پرطرفدار شده است . يکي از الگوريتم هاي خوشه بندي، الگوريتم کامينز است که به عنوان يکي ازبا نفودترين الگوريتم هاي داده کاوي مورد استفاده قرار مي گيرد و بسيار ساده و مقياس پذير است . در سال هاي اخير نسخه هايي از اين الگوريتم انتشار يافته است که مي تواند در برخورد با داده هاي توزيع شده ، به خوبي عمل کرده و نتايج خوبي را ارائه دهد. در اين الگوريتم ها ، نيازي به جمع آوري کردن اطلاعات و داده ها در يک مجموعه متمرکز نيست . در اين مقاله قصد داريم که اين الگوريتم ها را معرفي و بررسي کنيم .
واژه هاي کليدي: داده کاوي توزيع شده ، خوشه بندي،الگوريتم کامنيز،الگوريتم کامينز توزيع شده ،نرمال سازي
مقدمه
حجم داده هاي توليد شده در سال هاي اخير در حال رشد است . مجموعه اسناد، عکس ها، بيوانفورماتيک و ديگر داده ها با تکنولوژي هاي جديد، در حال افزايش هستند. در بسياري از موارد، داده ها در سايت هايمختلف داده ، به طور طبيعي توزيع ، توليد و ذخيره شده اند. در اين زمينه ، الگوريتم ها بايد قادر به استخراج اطلاعات مناسب از داده هاي توزيع شده با عملکرد خوب محاسباتي باشند.با اين حال ، اکثر تکنيک هاي داده کاوي که پيشنهاد مي شوند داده هاي متمرکز را مورد توجه قرار مي دهند ، اما متمرکز کردن آنها در يک جا بسيار پرهزينه خواهد بود ، هم چنين محدوديت پهناي باند و حريم شخصي نيز از نگراني ها و موانع متمرکز سازي داده ها مي باشد.
خوشه بندي يکي از تکنيک هاي پر کاربرد داده کاوي است که در آن ، مجموعه اي از اشيا که معمولا به صورت چند بعدي هستند به گروه ها يا کلاس هايي تقسيم بندي مي شوند که در هر گروه ، اشيا بر اساس معيارهاي از پيش تعيين شده ، به هم شبيه هستند. به طور کلي، فاصله اقليدسي از مراکز خوشه ها به عنوان معيار شباهت يا تفاوت در نظر گرفته مي شود.الگوريتم هاي خوشه بندي در زمينه هاي مختلفي مثل داده کاوي، تشخيص الگو ، تئوري يادگيري و ديگر زمينه ها کاربرد دارد.
يکي از متداول ترين الگوريتم هاي خوشه بندي ، الگوريتم کامينز است . اين الگوريتم ، بيش از نيم قرن است که مورد بررسي قرار گرفته است .اخيرا الگوريتم کامينز به خاطر سادگي، مقياس پذيري و کاربرد در نرم افزارهاي مختلف ، به عنوان يکي از ٠١ الگوريتم موثر و بانفوذ داده کاوي انتخاب شده است .با اين حال ،الگوريتم کامينز،به انتخاب نمونه خوشه هاي اوليه حساس است ،پس اگر خوشه هاي اوليه بدرستي انتخاب نشوند نتايج خوب و بهينه بدست نمي آيد. هم چنين در اين الگوريتم بايد تعداد خوشه هاي مورد نظر (k) را مشخص کرد و اين کار (مشخص کردن تعداد خوشه ها) مي تواند کاملا محدود کننده باشد. در سال هاي اخير نسخه هايي از اين الگوريتم انتشار يافته است که مي تواند در برخورد با داده هاي توزيع شده به خوبي عمل کند.
در قسمت دوم مقاله ، به بررسي داده کاوي توزيع شده (DDM) مي پردازيم . در قسمت سوم الگوريتم استاندارد کامينز و نسخه بهبود يافته آن را بررسي مي کنيم . در قسمت چهارم مقاله ،الگوريتم هاي کامينز توزيع شده را مرور مي کنيم .
داده کاوي توزيع شده
داده کاوي توزيع شده ، تکنيک کشف الگو ها يا توليد مدل هايي از داده هاي توزيع شده است که به صورت متمرکز نه امکان پذير است و نه مطلوب . داده کاوي توزيع شده مي تواند در ابر کامپيوترهاي موازي، شبکه هاي نظير به نظير و شبکه هاي حسگر مورد استفاده قرار گيرد. اما، محيط هاي مختلف مسائل و نگراني هاي مختلفي دارند. DDM به دسته هاي زير تقسيم مي شود.[٠]
خوشه هاي متمرکز در مقابل نظير به نظير
خوشه متمرکز يک هماهنگ کننده دارد. هماهنگ کننده کار را به کامپيوترهاي مختلف تقسيم مي کند. خوشه متمرکز به کارگيري و هماهنگي ساده تري دارد. و کاررا عادلانه تقسيم مي کند و مشکل نقطه شکست (single point of failure)دارد. الگوريتم هاي نظير به نظير به يک سرور مرکزي بستگي ندارند، و هر سايت داده را مي گيرد و کار خودش را انجام مي دهد.
مدل تکي در مقابل فرا-يادگيري
مدل تکي يک الگوريتم داده کاوي داده ها را به بخش هاي کوچکتر که در هر سايت توزيع شده اند تقسيم مي کند. الگوريتم ميتواند داده ، نتايج مياني، مدل هاي پيشگو، و نتايج نهايي يک الگوريتم داده کاوي را انتخاب کند و منتقل کند. از طرف ديگر، فرا-يادگيري، به صورت يادگيري از دانش يادگرفته شده تعريف شده است ، تکنيک ديگري است که سر و کارش با مشکل محاسبه يک مدل سراسري از پايگاه هاي داده ايي ذاتا توزيع شده و بزرگ است . هدف فرا-يادگيري محاسبه تعدادي مدل مستقل (classifier) با اعمال برنامه هاي يادگيري به طور موازي بدون انتقال يا دسترسي مستقيم به سايت است .
داده همگن در مقابل داده ناهمگن
در يک سيستم ديتابيس رابطه اي توزيع شده ، اطلاعات بايد در سايت هاي مختلف ذخيره شود. هر سايت جداول رابطه اي کامل دارد، داده همگن براي هر سايت ذخيره مي شود. که هر سايت اطلاعات جداول مختلف را ذخيره مي کند، در اين حالت مسئله داده ناهمگن داريم . اکثر داده کاوي موجود، داده همگن را در سايت هاي مختلف در نظر مي گيرد. در حالت داده توزيع شده ناهمگن ، ما فقط دانش ناقص را درباره ديتاست کامل مشاهده مي کنيم . مدل هاي محلي مختلف ديد محلي از کل مسئله دارند داده کاوي توزيع شده بايد يک مدل سراسري از آن مدل هاي محلي مختلف ايجاد کند. پس ، کاوش دادگان ناهمگن ، چالش برانگيز است .
داده کاوي توزيع شده و داده کاوي موازي
هم داده کاوي توزيع شده و هم داده کاوي موازي فرآيند داده کاوي را سرعت مي بخشند اما از جهاتي متفاوت هستند. DDM اغلب الگوريتم هاي کاوش متفاوت يا يکساني را اعمال مي کنند براي داده محلي و بين واحدهاي پردازش ارتباط برقرار مي کند و کشف الگوي محلي را ترکيب مي کند با الگوريتم هاي داده کاوي محلي از پايگاه هاي داده ايي محلي به يک راه حل دانش جهاني. در اين حالت ، دانش کشف شده اغلب با دانش کشف شده توسط اعمال الگوريتم هاي داده کاوي به کل ديتاست فرق دارد. دقت يا کارايي DDM تقريبا پيشگويي اش سخت است چون بستگي دارد به افراز داده ، زمان بندي کار، و سنتز جهاني. در مقابل با DDM ، يک الگوريتم داده کاوي موازي همان دانشي را پيدا مي کند که با الگوريتم ترتيبي اش يافت شده به علت اعمال الگوريتم موازي جهاني روي کل ديتاست . دقت آن نسبت به DDM بيشتر ضمانت شده است .
الگوريتم کامينز
الگوريتم کامينز استاندارد
در اين الگوريتم ، داده ها را به k خوشه مجزا تقسيم کنيم .اين الگوريتم به دو فاز مجزا تقسيم مي شود: در فاز اول براي هر خوشه يک نقطه را به عنوان نقطه ثقل خوشه (centroid) يا نقطه مرکزي خوشه بدست مي آوريم .و درفاز بعدي بدست مي آوريم که هر نقطه از مجموعه داده به کدام مرکز خوشه (centriod)نزديک تر است و آن نقطه را به خوشه مربوطه نسبت مي دهيم .در حالت کلي براي بدست آوردن فاصله بين نقاط داده و مراکز خوشه ها، از فاصله اقليدسي استفاده مي شود. زماني که تمام نقاط در خوشه ها قرار گرفتند مرحله اول به اتمامرسيده و خوشه بندي اوليه انجام شده است .سپس دوباره براي خوشه ها مراکز جديدي را بدست مي آوريم و فاصله هر نقطه را نسبت به اين نقاط مرکزي اندازه مي گيريم تا خوشه ها به روز شوند و اين کار تا زماني ادامه پيدا مي کند که خوشه ها همگرا شوند.[٢]
Algorithm 1: The k-means clustering algorithm
Input:
D = {d1, d2,......,dn} //set of n data items.k// Number of desired clusters
Output:
A set of k clusters.
Steps:
1. Arbitrarily choose k data-items from D as initialcentroids;
2. Repeat
Assign each item di to the cluster whichhas the closest centroid;
Calculate new mean for each cluster;
Until convergence criteria is met.
اما اشکال عمده اين الگوريتم اين است که با توجه به مقدار مراکز اوليه ، خوشه هاي متفاوتي توليد مي شودو در نتيجه کيفيت خوشه هاي نهايي شديدا به انتخاب مراکز اوليه خوشه ها وابسته است . اين الگوريتم از لحاظ محاسباتي گران و متناسب با تعداد نقاط ، تعداد خوشه ها و تعداد تکرارها نياز به زمان دارد.در قسمت بعد الگوريتم اصلاح شده کامينز را بررسي مي کنيم که اين اشکالات را رفع کرده است .

الگوريتم کامينز بهبود يافته
همانطور که بيان شد، الگوريتم خوشه بندي کامينز استاندارد از لحاظ محاسباتي سنگين و کيفيت نتايج خوشه هاي آن ، شديدا به انتخاب مراکز اوليه خوشه ها وابسته است .
يه همين دليل محققان سعي کرده اند تا با ارائه روش هايي اين نقايص را برطرف کنند و الگوريتم کامينز را بهبود ببخشند.
در روش کامينز بهبود يافته ، هر دو فاز الگوريتم کامينز براي بهبود دقت و کارايي آن اصلاح شده است . در مرحله اول ، مراکز اوليه خوشه ها براي توليد خوشه ها با دقت بالاتر از يک روش سيستماتيک به جاي انتخاب تصادفي استفاده ميکنند.
مرحله دوم با تشکيل خوشه هاي اوليه بر اساس فاصله نسبي هر نقطه (داده ) از مراکز اوليه خوشه ها شروع مي شود. اين خوشه ها متعاقبا بوسيله يک روش اکتشافي تنظيم مي شوند، بنابراين کارايي بهبود مي يابد.[٣[,]٤]
هر دو مرحله الگوريتم ، در دو الگوريتم ٢ و ٣ توضيح داده شده که مطابق زير است :
Algorithm 2: Finding the initial centroids
Input:
D = {d1, d2,......,dn} // set of n data itemsk // Number of desired clusters
Output:
Aset of k initial centroids .
Steps:
1. Set m = 1;
2. Compute the distance between each data point and allother data- points in the set D;
3. Find the closest pair of data points from the set D andform a data-point set
Am (1<=m <= k) which containsthese two data- points, Delete these two data points from
the set D;
4. Find the data point in D that is closest to the datapoint setAm, Add it to Am and deleteit from D;
5. Repeat step 4 until the number of data points in Amreaches 0.75*(n/k);
6. If m<k, then m = m+1, find another pair of datapointsfrom D between which the distance is the shortest, formanother data-point set Am
and delete them from D, Go tostep 4;
7. For each data-point set Am (1<=m<=k) find thearithmetic mean of the vectors of datapoints in Am,these means will be the initial
centroids.
Algorithm 3: Assigning data-points to clusters
Input:
D = {d1, d2,......,dn} // set of n data-points.
C = {c1, c2,.......,ck} // set of k centroids
Output:
A set of k clusters
Steps:
1. Compute the distance of each data-point di (1<=i<=n) toall the centroids cj (1<=j<=k) as d(di, cj);
2. For each data-point di, find the closest centroid cj andassign di to cluster j.
3. Set ClusterId[i]=j; // j:Id of the closest cluster
4. Set Nearest_Dist[i]= d(di, cj);
5. For each cluster j (1<=j<=k), recalculate the centroids;
6. Repeat
7. For each data-point di,
7.1 Compute its distance from the centroid of thepresent nearest cluster;
7.2 If this distance is less than or equal to the presentnearest distance, the data-point stays in the cluster;
Else
7.2.1 For every centroid cj (1<=j<=k)
Compute the distance d(di, cj);
Endfor;
7.2.2 Assign the data-point di to the cluster withthe nearest centroid cj
7.2.3 Set ClusterId[i]=j;
7.2.4 Set Nearest_Dist[i]= d(di, cj);
Endfor;
8. For each cluster j (1<=j<=k), recalculate the centroids;
Until the convergence criteria is met.

الگوريتم هاي کامينز توزيع شده
همانطور اشاره شد، با توجه به توزيع شدگي داده ها در مجموعه سايت هاي مختلف و عدم متمرکز کردن آنها در يک مجموعه ، نياز به الگوريتم هايي مي باشد که در محيط هاي توزيع شده به خوبي عمل کنند. الگوريتم کامينز يکي از الگوريتم هايي است که مي تواند در اين موارد نتايج مورد قبولي را ارائه دهد، اين الگوريتم به صورت استاندارد قادر خواهد بود در يک مجموعه متمرکز کار کند، لکن با کمي تغيير در ساختار اين الگوريتم و ترکيب آن با ديگر الگوريتم ها مي توان آن را به صورت توزيع شده استفاده کرد.در زير به ذکر نمونه هايي از اين الگوريتم که در محيط هاي توزيع شده کار مي کنند، مي پردازيم .
الگوريتم کامينز توزيع شده در محيط هاي موازي
اگر به الگوريتم کامينز استاندارد نگاه کنيم ميبينيم که توزيع شدگي به طور ذاتي درون آن نهفته است .فرايند با يک مجموعه داده آغاز مي شود و سپس مراکز اوليه خوشه ها انتخاب مي گردند.براي اجراي الگوريتم کامينز استاندارد به يک سيستم پردازنده واحد احتياج است .براي هر داده در هر تکرار عضويت آن در خوشه ها محاسبه مي شود. در اين وضعيت ، پردازنده همه ويژگيهاي ساختاري الگوريتم کامينز را در حافظه محلي نگهداري مي کند و تکرار گام هاي الگوريتم کامينز نقاط مرکزي نهاييZ را محاسبه مي کند.
در محيط هاي توزيع شده ما از پردازنده هاي شبکه اي براي الگوريتم کامينز استفاده ميکنيم . فرض ميکنيم که مجموعه داده ها در پردازنده هاي شبکه توزيع شده اند. اين پردازنده ها،
فرايند را در يک روش تعاملي اجرا مي کنند.شکل (a)٠ و (b)٠ توزيع داده را در يک شماي توزيع شده در قبل و بعد از اجراي الگوريتم نوزيع شده نشان مي دهد.[٥]