پایان نامه بررسی چهار روش مختلف براي خوشه بندي پايگاههاي داده بزرگ و مقایسه آنها
مقدمه
امروزه، يافتن الگوهاي مفيد در مجموعه هاي داده بزرگ بسيار مورد توجه مي باشد و يکي از مسائل مهم و بسيار مورد توجه در آن شناسايي خوشه ها يا نواحي داراي جمعيت متراکم در مجموعه داده چند بعدي مي باشد. خوشه بند ي در داده کاوي براي کشف گروهها و شناسايي توزيع ها بسيار مفيد مي باشد.
در اين گزارش چهار روش مختلف براي خوشه بندي پايگاههاي داده بزرگ معرفي شده و با يکديگر و ديگر روشهاي موجود مقايسه مي شوند. به اين منظور در بخش دوم روش BIRCH شرح داده مي شود [ZRL96] و با روش پيش از خود (CLARANS [NH94]) مقايسه مي شود. اين روش، اولين الگوريتم خوشه بنديي است که نويز را نيز مديريت مي کند. سپس CURE معرفي شده [GRS98] و با الگوريتمهاي پيش از خود و BIRCH مقايسه مي شود. در بخش چهارم DBCLASD معرفي شده [XEK98] و با CLARANS و DBSCAN مقايسه مي شود. در بخش پنجم الگوريتمي موازي براي خوشه بندي سريع پايگاههاي داده بزرگ معرفي مي شود. اين الگوريتم PFDC ناميده مي شود [M02] و نسخه موازي الگوريتم FDC مي باشد. در نهايت نتايج کلي اين روشها بررسي مي شوند.
2- BIRCH
در اين بخش، روش خوشه بندي BIRCH بررسي شده و ثابت مي شود که اين روش خصوصا براي پايگاههاي داده خيلي بزرگ مناسب مي باشد.اين روش داراي هزينه I/O خطي است. اين هزينه متناسب با سايز مجموعه داده مي باشد. در اين روش با تنها يک بار بررسي مجموعه داده ها مي توان به نتيجه خوشه بندي نسبتا خوبي دست يافت و به منظور افزايش کيفيت خوشه ها مي توان اين عمل را چندين بار تکرار نمود.
با ارزيابي کارايي زماني و فضايي (حافظه مصرفي) BIRCH و بررسي تاثير حساسيت آن نسبت به ترتيب ورود دادهها و بررسي کيفيت خوشه هاي توليد شده و مقايسه اينها با الگوريتم هاي موجود (از طريق آزايشات انجام شده) در مي يابيم که BIRCH بهترين روش خوشه بندي موجود در زمان خود براي پايگاههاي داده بزرگ مي باشد. معماري BIRCH به گونه اي است که در آن موازي سازي نيز امکانپذير است و اولين الگوريتم خوشه بنديي است که به نويز نيز توجه کرده است.
در اين بخش ابتدا کارهاي انجام شده قبلي بررسي شده و با BIRCH مقايسه مي شوند. سپس مغاهيم پايه و مفهوم ويژگي خوشه بندي و درخت آن که از مفاهيم اصلي در اين الگوريتم مي باشند بررسي مي شوند. سپس جزئيات الگوريتم BIRCH به تفصيل بيان شده و کارايي آن و نتايج بدست آمده بررسي مي شود.
2-1- خلاصه کارهاي انجام شده قبلي
خوشه بندي داده، در فيلدهاي آمار، يادگيري ماشين و پايگاه داده با روشها و ديدگاههاي متفاوت مطالعه مي شود. روشهاي قبلي ارائه شده، بر پايه احتمال (بيشتر روشها در يادگيري ماشين) يا بر پايه فاصله (بيشتر روشها در آمار) مي باشند و به مساله بزرگ بودن مجموعه داده ها اهميت نداده اند. به ويژه در اين روشها مساله محدود بودن منابع (حافظه) و هزينه I/O مورد توجه نبوده است.
روشهاي برپايه احتمال: در اين روشها غالبا فرض بر اين است که توزيع احتمال بر روي ويژگيهاي مجزا بطور آماري و مستقل از هم مي باشد. البته اين فرض بسيار دور از واقعيت مي باشد. همبستگي بين ويژگيها وجود دارد و احتمال بهنگام سازي و ذخيره خوشه ها را بخصوص اگر ويژگيها داراي ارزشهاي متعدد باشند بسيار پرهزينه مي سازد. زيرا در اين حالت پيچيدگي، نه تنها بستگي به تعداد ويژگيها پيدا مي کند، بلکه به تعدد ارزش هر ويژگي نيز وابسته مي شود. از مسائل مورد توجه در اين روشها، درخت برپايه احتمال مي باشد که براي شناسايي خوشه هايي که high balanced نيستند ساخته مي شود و براي وروديهاي نامتقارت ممکن است باعث کاهش قابل توجهي در کارکرد شود.
روشهاي بر پايه فاصله: در اين روشها فرض بر اين است که تمام نقاط داده از قبل داده شده اند و مي توانند مکررا بررسي شوند. در اين روش از مساله متفاوت بودن اهميت مجموعه داده ها و اينکه نقاط داده نزديک به هم مي توانند بصورت يک مجموعه مورد بررسي قرار گيرند صرف نظر شده است. در اين روشها همواره بايد تمام نقاط، براي خوشه بندي بررسي شوند. بنابراين داراي مقياس پذيري خطي با زمان و کيفيت ثابت نمي باشند.
به عنوان مثال، با استفاده از روش شمارش، تقريبا KN/K! راه براي بخشبندي مجموعه نقاط N تايي به K زير مجموعه وجود دارد. روش بهينه سازي تکراري (IO) بايک بخش اوليه شروع مي شود. سپس در اين روش تمام نقاط قابل معاوضه از يک گروه به گروه ديگر براي بهبود ارزش تابع اندازه گيري آزمايش مي شوند. در اين روش، يافتن مينيمم محلي امکانپذير است اما کيفيت آن بر روي بخش انتخاب شده اوليه بسيار تاثيرگذار است و پيچيدگي زماني در اين روش نمايي است. در روش خوشه بندي سلسله مراتبي، بهترين خوشه ها شناسايي نمي شوند اما به مساله ادغام نزديکترين زوجها و جداسازي دورترين نقاط توجه شده است. اما پيچيدگي آن O(N2) مي باشد. بنابراين اين روش نيز با افزايش N کارا نمي باشد.
امروزه خوشه بندي، به عنوان روشي مفيد براي داده کاوي شناخته شده است. الگوريتم CLARANS بر پايه جستجوي تصادفي بوده و براي خوشه بندي آماري استفاده مي شود. در اين الگوريتم، هر خوشه با medoid مربوطه اش که داده اي است که بيش از بقيه به مرکز خوشه نزديک است ارائه مي شود. فرايند خوشه بندي بصورت جستجوي در گراف مي باشد. در اين گراف هر نود شامل k خوشه ( در واقع k ، medoid ) است. دو نود در صورتي همسايه اند که تنها در يک medoid متفاوت باشند. الگوريتم مربوطه با انتخاب يک نود به طور تصادفي شروع مي شود. و در آن شماره بزرگترين همسايه بررسي شده و اگر همسايه بهتر يافت شد به آن اضافه مي شود. در غير اين صورت نود جاري به عنوان مينيمم محلي ثبت مي شود و الگوريتم با انتخاب نود ديگري ادامه مي يابد. CLARANS پس از اينکه مينيمم محلي را يافت خاتمه مي يابد.
CLARANS نيز مشکل روش IO را دارد. و ممکن است مينيمم محلي واقعي از طريق بيشرين همسايه يافته نشود. بعدها روشهايي براي بهبود کارايي CLARANS پيشنهاد شد اما آزمايشات نشان مي دهد که اين روشها زمان اجرا را بسيار ناچيز بهبود مي دهند.
2-1-1- مزاياي BIRCH
مزيت مهم BIRCH ، مناسب بودن آن براي مجموعه داده هاي خيلي بزرگ مي باشد. اين الگوريتم با ايجاد محدوديتهايي در زمان و حافظه، براي مجموعه داده هاي خيلي بزرگ قابل استفاده مي شود. در مجموع اين الگوريتم نسبت به روشهاي قبلي که بر مبناي فاصله بودند داراي مزاياي زير است:
- الگوريتم BIRCH بصورت محلي انجام مي شود و در آن خوشه بندي بدون بررسي تمام نقاط داده و خوشه هاي موجود انجام مي شود. و به اين منظور از مقياسهايي که نزديکي نقاط را نشان مي دهند استفاده مي کند.
- در BIRCH به اين مساله که فضاي داده غالبا به صورت يکنواخت اشغال نمي شود و درنتيجه نقاط داده در فرايند خوشه بندي ارزش يکسان ندارند توجه کرده است و در مورد ناحيه حجيم نقاط، به عنوان يک خوشه واحد رفتار مي کند. نقاط نواحي نامتراکم به عنوان نقاط دورافتاده محسوب شده و به دلخواه حذف مي شوند.
- BIRCH از حافظه موجود بطور کامل استفاده مي کند و از آن طريق بهترين خوشه هاي ممکن را ايجاد مي کند (تضمين دقت). و هزينه I/O را به منظور تضمين کارايي مينيمم مي سازد. در اين الگوريتم، خوشه بندي و فرايند کاهش از طريق ساختار درخت بالانس شده که در حافظه ايجاد مي شود انجام مي شود. و با اين خصوصيات، زمان اجرا بطور خطي مقياس پذير مي شود.
- با حذف فازهاي اختياري 4و 5 الگوريتم، BIRCH روشي افزايشي است که نيازي به کل مجموعه داده ندارد و فقط يک مجموعه داده را بررسي مي کند.
2-2- مفاهيم پايه
در اين قسمت ابتدا مرکز جرم، شعاع و قطر را در خوشه تعريف مي کنيم. اگر N داده d بعدي در خوشه داشته باشيم که بصورت {Xi} نمايش داده شوند، (i=1,2,..,N) ، X0 مرکز جرم است، R شعاع است و D قطر خوشه است و به صورت زير تعريف مي شود:
R ميانگين فاصله هر نقطه از مرکز جرم بوده و D ميانگين فاصله هر دو نقطه درون خوشه مي باشد. اين دو معيار، تراکم خوشه را حول مرکز جرم بيان مي کنند. براي بيان نزديکي دوخوشه از پنج معيار استفاده مي شود. اگر فرض کنيم که X01 و X02 مرکز جرم دو خوشه باشند، فاصله اقليدسي مرکز جرم، D0 ، و فاصله مانهاتان مرکز جرم، D1 ، بصورت زير تعريف مي شوند:
اگر خوشه {Xi}، N1 نقطه d بعدي داشته باشد (i=1,2,.., N1) و {Xj}، N2 نقطه d بعدي (j= N1+1,…, N1+ N2) ، ميانگين فاصله بين خوشه ها،D2 ، و ميانگين فاصله درون خوشه ها،D3 ، و واريانس افزايشي فاصله،D4 ، دو خوشه به صورت زير تعريف مي شود:
D3 در واقع D دو خوشه ادغام شده مي باشد . براي وضوح کار در مورد يک خوشه از X0 ، R و D استفاده مي شود و براي دو خوشه از D0 و D1 و D2 و D3 و D4 استفاده مي شود. مي توان داده ها را بطور دلخواه در بعدهاي مختلف شيفت داد يا وزن دهي کرد بدون اينکه موقعيت نسبي آنها تغيير کند.
2-3- ويژگي خوشه بندي و درخت CF
مفاهيم فوق، مفاهيم اصلي در الگوريتم افزايشي BIRCH مي باشند. ويژگي خوشه بندي (CF) سه تاييي است که اطلاعات در مورد هر خوشه را نگهداري مي کند.
تعريف 2-3-1: N داده d بعدي در خوشه {Xi} داده شده است، بردار CF خوشه بصورت سه تايي CF=(N,LS,SS) تعريف مي شود که در آن N تعداد نقاط خوشه، LS جمع خطي N داده () و SS مجموع مربعات N داده () مي باشد.
قضيه 2-3-1: (قضيه افزايشي CF) : فرض کنيد که CF1=(N1,LS1,SS1) و CF2=(N2,LS2,SS2) بردارهاي CF دو خوشه مجزا باشند، در اين صورت بردار CF خوشه اي که از طريق ادغام دو خوشه مجزا شکل مي گيرد به صورت زير تعريف مي شود:
اثبات اين قضيه از طريق جبر صريح عملي است.
از تعريف CF و قضيه افزايشي، در مي يابيم که بردارهاي CF خوشه ها ي ادغام شده، بصورت افزايشي و به دقت قابل محاسبه و ذخيره هستند. همچنين با استفاده از بردارهاي CF داده شده، X0 ، R و D، D0 و D1 و D2 و D3 و D4 به سادگي قابل محاسبه هستند.
يک خوشه مجموعه اي از نقاط مي باشد اما فقط بردار CF براي آن ذخيره مي شود. CF کافي نمي باشد زيرا اطلاعات کمتري را ذخيره مي کند اما دقيق مي باشد زيرا براي محاسبه مقياسهاي لازم براي خوشه بندي در الگوريتم BIRCH کافي مي باشند.
2-3-1- درخت CF
درخت CF، درخت بالانس شده ارتفاعيي است که دو پارامتر دارد: فاکتور شاخه بندي B و ترشولد T. هرنود غير برگ شامل بيشترين مدخل هاي B به صورت مي باشد که در آن و اشاره گري به I امين نود فرزند مي باشد و ، CF زيرخوشه ارائه شده از طريق اين فرزند مي باشد. بنابراين نود غيربرگي که خوشه را نمايش مي دهد، از تمام زيرخوشه هايي که از طريق مدخل هايشان ارائه مي شوند، ساخته مي شود. نود برگ شامل بيشترين مدخل L مي باشد که هر يک به فرم هستند که . در مجموع هر نود برگ دو اشاره گر دارد: prev و next که براي زنجير کردن تمام نودهاي برگ (براي بررسي کاراتر آنها) استفاده مي شود. نود برگ همچنين، خوشهاي ساخته شده از تمام زيرخوشه هاي ارائه شده از طريق مدخل هايشان را نمايش مي دهد. تمام مدخلها در نود برگ بايد ترشولد را در جهت ارزش T (شعاع يا قطر بايد کمتر از T باشد) ارضا کنند.
سايز درخت تابعي از T مي باشد. T بزرگ تر باعث مي شود که درخت کوچک تري داشته باشيم. ما نياز به نودي داريم که مناسب در صفحه اي به سايز P باشد. اولين بار که قطر d فضا داده مي شود، سايز مدخل هاي برگي و غيربرگي شناخته مي شوند. سپس B و L از طريق P تعيين مي شوند. بنابراين P مي تواند به منظور تنظيم کارايي تغيير کند.
چنين درخت CFي هنگاميکه داده جديد درج مي شود بصورت دايناميک ساخته خواهد شد. اين مساله به منظور درج جديد در زيرخوشه صحيح براي خوشه بندي استفاده مي شود. درخت CF، ارائه بسيار فشرده مجموعه داده مي باشد زيرا هر مدخل در نود برگ يک داده مجزا نمي باشد بلکه يک زيرخوشه مي باشد که شامل نقاط داده بسياري با قطر يا شعاع کمتر از ترشولد مشخص T مي باشد.
2-3-2- درج در درخت CF
در اين قسمت، الگوريتم درج مدخل در درخت CF ارائه مي شود. در واقع به اين منظور وقايع زير براي مدخل Ent رخ مي دهد:
- شناسايي برگ مناسب: با شروع از ريشه، درخت CF بطور بازگشتي با انتخاب نزديکترين نود فرزند مطابق باکميت فاصله انتخاب شده D0 ، D1 ، D2 ، D3 يا D4 پيمايش مي شود.
- اصلاح برگ: هنگاميکه به نود برگ مي رسيم، الگوريتم، نزديکترين مدخل برگ را که Li ناميده مي شود پيدا مي کند. سپس تست مي کند که آيا Li مي تواند Ent را بدون نقض ترشولد جذب کند يا خير. اگر بتواند بردار CF ِ Li بر اساس جذب جديد تغيير مي کند. اگر چنين نباشد مدخل جديد براي Ent به برگ اضافه مي شود. و اگر فضايي براي اين مدخل جديد در برگ موجود نباشد نود برگ را مي شکنيم. شکستن نود از طريق انتخاب دورترين زوج مدخلها به عنوان دانه انجام مي شود و مدخلهاي باقيمانده برپايه ضابطه نزديکي، دوباره توزيع مي شوند.
- اصلاح مسير برگ: پس از درج Ent در برگ، بايد اطلاعات CF را براي هر مدخل غيربرگ در مسير برگ به روز سازيم. درصورتيکه شکستن صورت نگيرد، بايد بردار CF تغيير کند و Ent اضافه را نيز شامل شود. براي شکستن برگ، مدخل غير برگي در نود پدر بايد وجود باشد تا آن برگ را شرح دهد. درصورتيکه پدر فضايي براي اين مدخل داشته باشد، در تمام سطوح بالاتر فقط بايد بردار CF براي انعکاس Ent جديد تغيير کند و اگر موجود نباشد ناچاريم پدر را بشکنيم و همينطور اين عمل را به سمت ريشه ادامه دهيم. اگر ريشه بشکند، ارتفاع درخت يک واحد افزايش مي يابد.
- اصلاح ادغام: شکستن از طريق سايز صفحه انجام مي شود که مستقل از خصوصيات خوشه بندي داده مي باشد. و ممکن است کيفيت خوشه بندي تحت تاثير قرار گيرد. ادغام، باعث رفع اين مشکل مي شود. اگر برگي بشکند و شکستن آن در نود Nj که مي تواند مدخل اضافه را در خود جاي دهد متوقف شود، Nj را براي يافتن دو نزديکترين مدخل بررسي مي کنيم. اگر آنها از شکسته شدن ايجاد نشده باشند سعي مي کنيم آنها را در هم ادغام کنيماگر مجموع مدخلهاي دو نود فرزند از آنچه در يک صفحه قابل نگهداري است بيشتر باشد، دوباره آنها را مي شکنيم.و در واقع مدخلهاي اضافه تر از يک صفحه، در نود جديد قرار مي گيرند. در واقع اگر مدخل هاي ادغام شده در يک صفحه جاي گيرند، يک نود آزاد مي شود و در Nj نيز يک مدخل خالي ايجاد مي شود و در غير اين صورت توزيع دو مدخلها در دو فرزند نزديک به هم بهبود مي يابد.
2-4- الگوريتم خوشه بندي BIRCH
در شکل يک کليات الگوريتم BIRCH آمده است. در فاز اول، تمام داده ها بررسي شده و درخت CF اوليه با استفاده از حافظه داده شده و فضاي بازيابي ديسک، در حافظه ايجاد مي شود. در اين درخت سعي مي شود که اطلاعات خوشه بندي داده در حافظه محدود آورده شود. در واقع نقاط داده در زيرخوشه ها گروه بندي شده و نقاط داده پراکنده حذف مي شوند. اين فاز خلاصه اي از داده در حافظه ايجاد مي کند. جزئيات اين فاز در بخش 2-4-1 آمده است. با انجام اين فاز، محاسبات در فازهاي بعدي داراي خواص زير خواهند بود:
- سريع: زيرا I/O لازم نمي باشد و خوشه بندي داده ها به مساله خوشه بندي کوچکتر زيرخوشه ها در مداخل برگ کاهش مي يابد.
- دقيق: زيرا تعداد زيادي از نقاط دور افتاده حذف مي شوند.
- نسبت به ترتيب ورود داده ها داراي حساسيت کمتري مي باشد. زيرا مدخل هاي برگ درخت اوليه ترتيبي مناسب تر براي داده ها شکل مي دهند.
شکل1: کليات الگوريتم BIRCH
فاز دو اختياري است. مشاهده شده است که روشهاي خوشه بندي عمومي در فاز سوم دامنه سايز ورودي متفاوتي دارند. بنابراين گپي بين سايز نتايج فاز اول و ورودي فاز سوم وجود دارد. فاز دو براي رفع اين گپ است و در آن مشابه فاز يک مدخل هاي برگ درخت CF اوليه براي پاک کردن داده هاي دور افتاده باقيمانده مرور شده و درخت CF کوچکتري ايجاد مي شود و زيرشاخه هاي شلوغ نيز در زيرشاخه هاي بزرگتر دسته بندي مي شوند.
در فاز سوم با استفاده از الگوريتم عمومي خوشه بندي، تمام برگها بررسي مي شوند. الگوريتم هاي خوشه بندي موجود به اين منظور قابل استفاده مي باشند. به عنوان مثال، با داشتن بردارهاي CF،با استفاده از مرکز جرم براي نمايش زيرخوشه، مي توانيم با هر زيرخوشه به عنوان يک نقطه واحد رفتار کرده و از الگوريتم موجود بدون اصلاح استفاده کنيم يا اينکه با n نقطه داده در هر هر زيرخوشه به عنوان مرکز جرمش برخورد کرده و الگوريتم موجود را براي شمارش اطلاعات در شمارش اصلاح کنيم. يا اينکه الگوريتم موجود را مستقيما بر روي زيرخوشه ها به کار ببريم زيرا اطلاعات بردارهاي CF آنها غالبا براي محاسبه ماتريسهاي بيشترين فاصله و کيفيت کافي هستند.
در مرجع مربوطه از الگوريتم خوشه بندي سلسله مراتبي در زيرخوشه ها استفاده شده است و از ماتريسهاي D2 و D4 استفاده شده است و پيچيدگي آن O(n2) است. پس از فاز 3 مجموعه خوشه هايي بدست مي آوريم که توزيع اصلي الگو در داده را شکل مي دهند. در نتيجه حاصل، به علت جايگيري اشتباه بررسي شده در 2-3-2 و اينکه فاز 3 پاسخگو به داده هاي درشت دانه است، ممکن است بي دقتي پيش آيد. در فاز4 براي رفع اين بي دقتي داده ها بايد مجددا مرور شوند. تا انتهاي فاز3 داده ها تنها يک بار مرور شده بود. (البته درخت و اطلاعات دورافتاده ممکن است چندين بار مرور شده باشند.)
فاز4 از مرکز جرم خوشه ها که در فاز 3 توليد شده بود به عنوان دانه استفاده مي کند و نقاط داده را در نزديکترين دانه براي بدست آوردن مجموعه جديدي از خوشه ها دوباره توزيع مي کند. اين کار باعث مي شود که علاوه براين که نقاط مربوط به يک خوشه به خوشه خود بروند، کپي هاي داده نيز به همان خوشه بروند. در اين فاز هر داده مي تواند به خوشه اي که به آن متعلق است برچسب زده شود و نقاط دور افتاده حذف شوند.
2-4-1- بررسي فاز 1
شکل 2 جزئيات فاز 1 را نشان مي دهد. اين فاز با ارزش اوليه ترشولد آغاز مي شود. داده ها مرور مي شوند و نقاط در درخت درج مي شوند. اگر خارج از حافظه اجرا شود، پيش از اتمام بررسي داده، ارزش ترشولد افزايش مي يابد و درخت CF کوچکتري از طريق درج مجدد مدخل هاي برگ درخت قديمي ساخته مي شود. پس از اينکه دخل هاي برگ قديمي مجددا درج شدند، بررسي داده (و درج در درخت جديد) از نقطه اي که متوقف شده بود ادامه مي يابد.
شکل2: جريان کنترلي فاز1
2-4-1-1- کاهش
فرض کنيد که ti ، يک درخت CF با ترشولد Ti است. ارتفاع آن h است و سايز آن (تعداد نودها) Si است. Ti+1>=Ti است. مي خواهيم تمام مدخل هاي برگ ti را براي ساخت مجدد درخت CF ِ ti+1 با ترشولد Ti+1 بکار ببريم، بطوريکه سايز ti+1 بيش از Si نشود. در ادامه، الگوريتم دوباره سازي با نتيجه قضيه کاهش ارائه مي شود.
شکل3: ساخت مجدد درخت CF
فرض کنيد درون هر نود درخت CF ِ ti مدخلها از 0 تا nk-1 برچسب خورده باشند و در آن nk تعداد مدخل ها در آن نود باشدمي توان از مدخلي موجود در ريشه (سطح 1) به نود برگ (سطح h ) مسيري واحد به فرم داشت. و در آن ij برچسب j امين سطح مدخل در آن مسير است. بنابراين مسير قبل از (کوچکتر از) مسير مي باشد اگر . نود برگ از طريق يک مسير واحد به دست مي آيد و بنابراين مي توان براي نشان دادن نود برگ از مسير مربوطه اش استفاده کرد.
در شکل3 الگوريتم مربوطه نشان داده شده است. به ترتيب فوق، درخت قديمي قدم به قدم بررسي شده و در همان زمان، درخت جديد قدم به قدم ساخته مي شود. درخت جديد با NULL شروع مي شود و OldCurrentPath با بيشترين سير چپ در درخت قديمي شروع مي شود براي آن الگوريتم به صورت زير دنبال مي شود:
- NewCurrentPath مطابق با آن در درخت جديد ايجاد مي شود: نودها دقيقا همانند درخت قديمي به درخت جديد اضافه مي شوند. بنابراين درخت جديد بزرگتر از درخت قديمي نمي شود.
- مدخلهاي برگ OldCurrentPath به درخت جديد اضافه مي شوند: با ترشولد جديد، هر مدخل برگ جديد در OldCurrentPath، در درخت جديد تست مي شود که آيا مي تواند در NewClosestPath که با نزديکترين ضابطه در درخت جديد بصورت بالا به پايين يافت مي شود fit شود، اگر بتواند و NewClosestPath قبل از NewCurrentPath باشد، در NewClosestPath درج مي شود و فضا در NewCurrentPath براي استفاده بعدي در دسترس باقي مي ماند. در غير اين صورت در NewCurrentPath، بدون ايجاد نود جديد ديگري درج مي شود.
- آزاد کردن فضا در OldCurrentPath و NewCurrentPath: يک بار تمام مدخل هاي برگ در OldCurrentPath پردازش مي شوند، نودهاي غيرلازم در آن آزاد مي شوند. اين کار مشابه آن است که بعضي نودهاي NewCurrentPath خالي شوند. زيرا مدخلهاي برگي که مطابق با اين مسير هستند، به جلو هل داده مي شوند. در اين موقع، نودهاي خالي نيز مي توانند آزاد شوند.
- OldCurrentPath به مسير بعدي در درخت قديمي تنظيم مي شود و قدمهاي بالا تکرار مي شود.
از مراحل ساخت مجدد، مدخل هاي برگ قديمي مجددا درج مي شوند، اما درخت جديد هرگز بزرگتر از درخت قديمي نمي شود. با توجه به اينکه تنها نودهاي مطابق با OldCurrentPath و NewCurrentPath لازم است که بطور همزمان موجود باشند، بيشرين فضاي اضافه لازم براي تغيير درخت، h صفحه مي باشد. بنابراين با افزايش ترشولد مي توانيم درخت CF کوچکتري با حافظه اضافه محدودتر مجددا بسازيم.
قضيه 2-4-1: (قضيه کاهش) فرض کنيد درخت CF ِ ti+1 با ترشولد Ti+1 را از درخت CF ِ ti با ترشولد Ti از طريق الگوريتم فوق مجددا مي سازيم و Si و Si+1 به تر تيب سايز ti و ti+1 باشند. اگر Ti+1>=Ti باشد، Si+1=<Si خواهد بود و تغيير از ti به ti+1 نياز به بيشرين h صفحه اضافه حافظه دارد. (h ارتفاع ti مي باشد)
2-4-1-2- مديريت نقاط دور افتاده
بطور دلخواه مي توانيم از R بايت ديسک براي مديريت نقاط دور افتاده استفاده کنيم. اين نقاط مدخل هاي برگ با تراکم کم مي باشند که لازم نيست در خوشه بندي کلي بررسي شوند. هنگاميکه درخت CF را از طريق درج مجدد مدخل هاي برگ قديمي مجددا مي سازيم، سايز درخت جديد به دو روش کاهش مي يابد. اول اينکه ارزش ترشولد را افزايش مي دهيم، در نتيجه به هر مدخل برگ اجازه مي دهيم که نقاط بيشتري را جذب کند. دوم اينکه بعضي از مدخل هاي برگ، به عنوان نقاط دور افتاده شناخته مي شوند و در ديسک نوشته مي شوند. مدخل برگ قديمي در صورتيکه نقاط داده بسيار کمتري از ميانگين داشته باشد، به عنوان نقطه دورافتاده شناخته مي شود. “بسيار کمتر”، هيوريستيک مي باشد.
نقاط دور افتاده در ديسک متناوبا بررسي مي شوند تا در صورت امکان در درخت جاري، بدون افزايش سايز درخت، جذب شوند. افزايش ارزش ترشولد يا تغيير توزيع به واسطه خواندن داده جديد پس از نوشتن نقطه دور افتاده مي تواند بدان معني باشد که نقطه فوق، بيش از اين واجد شرايط به عنوان نقطه دور افتاده نمي باشد. وقتيکه تمام داده ها بررسي مي شوند، نقاط دور افتاده در ديسک بايد بررسي شوند که آيا واقعا نقطه دور افتاده مي باشند يا خير. اگر اين نقاط در اين مرحله جذب نشوند، به احتمال زياد نقطه دور افتاده واقعي بوده و مي توانند پاک شوند.
سيکل داخلي ( حافظه ناکافي که باعث ساخت مجدد درخت مي شود، ديسک ناکافي که باعث جذب مجدد نقطه دورافتاده مي شود و…) مي تواند چندين بار قبل از اينکه مجموعه داده بطور کامل بررسي شود، تکرار شود. در مجموع، اين فرايند، هزينه فاز1 مي باشد.
2-5- بررسي کارايي
در اين قسمت آناليز پيچيدگي ارائه مي شود.
2-5-1- آناليز
ابتدا هزينه CPU در فاز اول را بررسي مي کنيم. بيشترين سايز درخت M/P است. براي درج يک نقطه بايد مسيري از ريشه به برگ طي شود. و حدود نود رد شود. در هر نود بايد B مدخل براي يافتن نزديکترين، بررسي شود. هزينه هر مدخل متناسب با بعد d مي باشد. بنابراين هزينه درج تمام نقاط داده مي شود. در مواردي که بايد درخت را مجددا بسازيم، اگر فرض کنيم ES سايز مدخل CF باشد، در بيشترين حالت M/ES مدخل برگ بايد مجددا درج شوند. بنابراين هزينه درج مجدد مدخل هاي درخت، مي شود. تعداد دفعاتي که مجبور مي شويم درخت را مجددا بسازيم بستگي به هيوريستيک ترشولد ما دارد. غالبا اين تعداد حدود بار مي باشد. مبناي 2 براي اين است که ما هرگز بيش از دو برابر سايز جاري تخمين نمي زنيم. و تعداد نقاط داده لود شده در حافظه با ترشولد مي باشد. بنابراين مجموع هزينه CPU فاز اول مي شود. آناليز هزينه CPU در فاز 2 نيز مشابه فاز 1 است.
در مورد هزينه I/O : داده ها يک بار در فاز بررسي مي شوند و در فاز 2 ديگر بررسي نمي شوند. در مورد نقاط دور افتاده، هزينه نوشتن آنها در ديسک و خواندنشان براي ساخت مجدد موجود است. با در نظر گرفتن اينکه ميزان ديسک موجود براي مديريت نقاط دور افتاده بيش از M نباشد، و اينکه حدود دفعه، ساخت مجدد داريم، هزينه I/O فاز 1، با هزينه خواندن مجدد داده چندان تفاوتي ندارد و با توجه به مطالب فوق، هزينه فاز 1 و 2 بطور خطي با N افزايش مي يابد.
در فاز3، I/O نداريم. با توجه به اينکه ورودي ب فاز3 محدود است، هزينه CPU فاز3 محدود به ميزان ثابتي است که بستگي به بيشترين سايز ورودي و الگوريتم عمومي انتخاب شده براي اين فاز دارد. در فاز3 مجموعه داده ورودي مجددا بررسي مي شوند و هر داده در خوشه مناسب قرار مي گيرد. زمان صرف شده براي آطن کار متناسب با مي باشد. ( در تکنيک جديد نزديک ترين همسايه، اين زمان متناسب با N است.
2-6- بررسي نتايج بدست آمده
در مرجع بررسي شده نتايج آزمايشات نشان مي دهد که BIRCH براي خوشه بندي مجموعه داده هاي بزرگ نيز مناسب مي باشد. اين متد مسائل خوشه بندي بزرگ را با تمرکز بر بخشهاي متراکم داده کنترل مي کند. اين روش از مقياسهايي که براي بررسي ميزان نزديکي داده ها مناسب است استفاده مي کند. اين مقياسها در درخت بالانس شده ارتفاع، بطور افزايشي قابل ذخيره سازي و بروز رساني هستند. الگوريتم BIRCH مي تواند با هر ميزان حافظه اي کار کند و پيچيدگي I/O در آن کمي بيش از يک بار بررسي داده مي باشد. BIRCH مي تواند با کيفيت عالي بر روي مجموعه داده هاي بزرگ عمل کند و بطور قابل ملاحظه اي از نظر کيفيت، سرعت و حساسيت نسبت به ترتيب ورود داده، برتر از CLARANS مي باشد. تنظيم مناسب پارامترها نيز در کارايي BIRCH بسيار حائز اهميت است.
3- CURE
بطور کلي خوشه ها بر دو دسته اند: يا به صورت کروي شکل مي باشند و يا بسيار نازک بوده و داراي نقاط دورافتاده مي باشند. در اين قسمت الگوريتم CURE بررسي مي شود.در اين الگوريتم به نقاط دور افتاده و شناسايي خوشه هاي غيرکروي با پهناي زياد توجه شده است. در اين الگوريتم هر خوشه از طريق چندين نقطه ارائه مي شود. اين نقاط از بين نقاط خوشه انتخاب شده و تعدادشان کاهش داده مي شود. تا اينکه نهايتا فقط از مرکز خوشه استفاده شود. در اين الگوريتم با ارئه هر خوشه از طريق چندين نقطه مي توان اشکال غيرکروي را پوشش داد و با کاهش اين نقاط مي توان نقاط دور افتاده را کم کرد. CURE به منظور مديريت پايگاههاي داده بزرگ از نمونه برداري تصادفي به همراه قسمت بندي استفاده مي کند. هر نمونه تصادفي از مجموعه داده، ابتدا قسمت بندي مي شود. سپس هر قسمت به طور ناقص خوشه بندي مي شود. در فاز دوم، خوشه هاي ناقص براي دستيابي به خوشه هاي مطلوب مجددا خوشه بندي مي شوند. نتايج آزمايشات نشان مي دهد که کيفيت خوشه هاي توليد شده از طريق اين الگوريتم از الگوريتم هاي موجود زمان خود بهتر بوده و علاوه بر آن، مي تواند براي پايگاههاي داده بزرگ نيز بدون کاهش کيفيت کارا باشد.
3-1- بررسي کاستي هاي الگوريتمهاي خوشه بندي رايج
الگوريتم هاي خوشه بندي موجود به دو دسته قسمت بندي و سلسله مراتبي تقسيم مي شوند. در نوع اول k بخش تعيين مي شود و هدف اين است که معيار خاصي بهينه شود. اين معيار معمولا مربع خطا مي باشد و به صورت زير تعريف مي شود و در آن mi ميانگين خوشه Ci است.
بنابراين مي خواهيم k بخش بطوري انتخاب کنيم که مربع خطا مينيمم شود پس بايد اين خوشه ها تا جايي که ممکن است فشرده و مجزا باشد. هنگامي که خوشه هاي مختلف داراي اختلاف سايز و اختلاف شکل هندسي زياد هستند (مانند شکل 4) در روش مربع خطا، خوشه هاي بزرگ شکسته مي شوند در اين شکل مربع خطا در سه خوشه مشخص شده در a از b بيشتر است در شکل b خوشه بزرگ به سه بخش تقسيم مي شود و يکي از آنها با دو خوشه کوچک ادغام مي شود.
نقد و بررسیها
هنوز بررسیای ثبت نشده است.