مرجع دانلود پاورپوینت های درسی

حجم فایل : 224.6 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 65
بنام خدا بررسی روشهای خوشه بندی پايگاههای داده بزرگ فهرست مطالب بررسی الگوريتم 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 بزرگ تر باعث مي شود که درخت کوچک تري داشته باشيم.
درج مدخل Ent در درخت CF شناسايي برگ مناسب
اصلاح برگ
اصلاح مسير برگ
اصلاح ادغام الگوريتم خوشه بندي BIRCH خواص فازهای دوم به بعد در الگوريتم BIRCH سريع: زيرا I/O لازم نمي باشد و خوشه بندي داده ها به مساله خوشه بندي کوچکتر زيرخوشه ها در مداخل برگ کاهش مي يابد.
دقيق: زيرا تعداد زيادي از نقاط دور افتاده حذف مي شوند.
نسبت به ترتيب ورود داده ها داراي حساسيت کمتري مي باشد. زيرا مدخل هاي برگ درخت اوليه ترتيبي مناسب تر براي داده ها شکل مي دهند.
مديريت نقاط دور افتاده هنگاميکه درخت CF را از طريق درج مجدد مدخل هاي برگ قديمي مجددا مي سازيم، سايز درخت جديد...