پاورپوینت بررسی روشهای خوشه بندی پايگاههای داده بزرگ (pptx) 66 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 66 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
بررسی روشهای خوشه بندی پايگاههای داده بزرگ
فهرست مطالب
بررسی الگوريتم BIRTCH [ZRL96]
بررسی الگوريتم CURE [GRS98]
بررسی الگوريتم DBCLASD [XEK98]
بررسی الگوريتم موازی PFDC [M02]
خلاصه و نتايج
فهرست منابع
الگوريتم BIRCH
تعاريف پايه در مورد خوشه {Xi}
تعاريف پايه در مورد دو خوشه {Xi} و {Xj}
ويژگي خوشه بندي (CF)
N داده d بعدي در خوشه {Xi} داده شده است، بردار CF خوشه بصورت سه تايي CF=(N,LS,SS) تعريف مي شود که در آن N تعداد نقاط خوشه، LS جمع خطي N داده و SS مجموع مربعات N داده مي باشد.
قضيه افزايشي CF :
فرض کنيد که CF1=(N1,LS1,SS1) و CF2=(N2,LS2,SS2) بردارهاي CF دو خوشه مجزا باشند، در اين صورت بردار CF خوشه اي که از طريق ادغام دو خوشه مجزا شکل مي گيرد به صورت زير تعريف مي شود:
اطلاعات ذخيره شده در مورد هر خوشه در BIRCH
يک خوشه مجموعه اي از نقاط مي باشد اما فقط بردار CF براي آن ذخيره مي شود.
CF کافي نمي باشد زيرا اطلاعات کمتري را ذخيره مي کند.
اما دقيق مي باشد زيرا براي محاسبه مقياسهاي لازم براي خوشه بندي در الگوريتم BIRCH کافي مي باشند.
درخت CF
درخت CF، درخت بالانس شده ارتفاعيي است که دو پارامتر دارد: فاکتور شاخه بندي B و ترشولد T.
هرنود غير برگ شامل بيشترين مدخل هاي B به صورت [CFi,childi] مي باشد که در آن i=1,2,…,B و childi اشاره گري به I امين نود فرزند مي باشد و CFi، CF زيرخوشه ارائه شده از طريق اين فرزند مي باشد. بنابراين نود غيربرگي که خوشه را نمايش مي دهد، از تمام زيرخوشه هايي که از طريق مدخل هايشان ارائه مي شوند، ساخته مي شود.
نود برگ شامل بيشترين مدخل L مي باشد که هر يک به فرم [CFi] هستند که i=1,2,…,L. در مجموع هر نود برگ دو اشاره گر دارد: prev و next که براي زنجير کردن تمام نودهاي برگ (براي بررسي کاراتر آنها) استفاده مي شود. نود برگ همچنين، خوشهاي ساخته شده از تمام زيرخوشه هاي ارائه شده از طريق مدخل هايشان را نمايش مي دهد. تمام مدخلها در نود برگ بايد ترشولد را در جهت ارزش T (شعاع يا قطر بايد کمتر از T باشد) ارضا کنند.
سايز درخت تابعي از T مي باشد. T بزرگ تر باعث مي شود که درخت کوچک تري داشته باشيم.