DBSCAN and BIRCH clustring

صفحه 1:
DBSCAN & BIRCH Clustering صبا حصارکی رما دانشكاه آزاد اسلامى واحد علوم و تحقيقات بهار ۱۴۰۱ 

صفحه 2:
DBSCAN Clustering 

صفحه 3:
رویکردهای مبتنی بر چگالی چرا روش های خوشه بندی مبننی بر چگالی؟ خوشه هایی با شکل دلخوا را کشف کنید. خوشه ها -تواحی متراکم از اجسام که توسط مناطق با چگالی کم از هم جدا شده اند 01 اولین خوشه بندی مبتنی بر چگالی :02 _ ترتیب خوشه ای مبتنی بر چگالی ‎ DENCLUE‏ کت وصیفک لیسبتنیسر چگالاز خوشه و خوشه ‎@your company 

صفحه 4:
:852 2]خوشه بندی فضایی مبتنی بر چگالی برنامه ها با نویز 0 چرا روش های خوشه بندی مبتنی بر جكالى؟ Xu (KDD96) , Ester. Kriegel. Sander 1.5 ‏پیشنهاد شده‎ 0 0 متكى بر مفهوم مبتنی بر چگالی از خوشه: یک خوشه به عنوان مجموعه حداکثری از نقاط متصل به چگالی تعریف می شود. 0 _خوشه هایی از شکل دلخواه را در پایگاه داده های فضایی با نویز کشف می کند @your company 

صفحه 5:
© خوشه بندی مبتنی بر چگالی یه ای خوشه ها نواحی متراکم در فضای داده هستند که با نواحی با چگالی جسم كمتر از هم جدا شده اند روش هاى خوشه بندى مبتنى بر ‎SMES‏ بر چگالی متفاوت وجود دارد (به کتاب و مقالات مراجعه کنید) اینجا ما ايده های زیربتایی الگوریتم ‎DBSCAN‏ را مورد بحث قرار می دهیم Results of a k-medoid algorithm for k=4 @your com 

صفحه 6:
خوشه بندی مبتنی بر چگالی: مفهوم اساسی شهود برای رسمی کردن ایده اصلی برای هر نقطه در یک خوشه. چگالی نقطه محلی در اطراف آن نقطه بايد از يك آستانه فراتر رود مجموعه ای از نقاط از یک خوشه به صورت فضایی به هم متصل است چگالی نقطه محلی در یک نقطه ۵ که توسط دو پارامتر تحریف شده است. شعاعبرای همسایگی نقطه ۵ }8 < ‎N,(p) := {q in data set D | dist(p, q)‏ ‎MinPts:‏ حداقل تعداد تقاط در محله داده ‎N(p) sa‏ - همسایگی - اشیاء در شعاع از یک شی ( > (:) ۰:۱۱ () ,۸۷ "چگالی بالا" - -همسایگی یک شی شامل حدافل 11۳۳05 از اجسام است @your company 

صفحه 7:
با توجه به و ۷/10۴5 اشیاء را به سه گروه انحصاری دسته پندی نید یک نقطه اگر بیش از تعداد نقاط مشخصی داشته باشد. ‎als (MinPts)‏ اصلی است. درون 05] اينها نقاطی هستند که در داخل یک خوشه قرار دارند. یک نقطه مرزی کمتر از ۷1/015 در 05] دارد. اما در همسایگی یک نقطه مرکزی است. نقطه نوبز به هر نقطه ای گفته می شوة که یک نقطه مرکزی و نه نقطه مرزی باشد. Outlier Border Core € = lunit, MinPts = 5 @your company 

صفحه 8:
© مثال 5 Minpts = 3 37 9 oO ۱ ‘el e Eps=radius ۰ ] ‏رم ارس‎ of the ° 1 CCR circles ۵ و ] لشیاء اصلی‌هستند زیرا هر کئلم در یبکهمسایگی۴05 هستند که حدلقادارلی۲ نقطه لست 8 eo 

صفحه 9:
چگالی خابلیت دسترسی 0 _ دسترسی مستقیم به چگالی 0 یک شی 0 مستقیماً از شی 0 قابل دسترسی است. اگر 0 یک شی هسته و 0 در همسایگی 0*5 - همسایگی باشد 0 بسه طور مستقیم‌از 8 قابل‌دسترسیبه چگامللست 0 0 مستقیماً چگالی قابل دسترسی از 0 نیست؟ 8 تراک دسترسی تاستفارن آنستء MinPts = 4 @your company 

صفحه 10:
تراکم فابل دسترسی (مستقیم و غیر مستقیم) یک نقطه ۵ مستقيماً از 02 قابل دسترسی به چگالی است. 2 مستقيماً از 01 قابل دسترسی به چگالی است. ام مستقیماً از ۵ قابل دستیایی به چگالی است. ‎٩‏ 01 * ۵۳02 يكينجيره را تتشکیلمی‌دهند 8 است (غیر مستقیم) چگالی فابل دستیابی از ( ‏0 از ۵ چگ وق ابلهسترسیننیسگ ‎ ‎@your company 

صفحه 11:
تراکم-اتصال 0 چگالی قابل دسترسی متقار 0 _ برای توصیف خوشه ها به اندازه کافی خوب نیست مس ان 0 جفت از نقاط 0 و به چگالی متصل هستند اگر معمولً از نقطه 0 قابل دسترسی به چگالیباشند 0 _ چگالی اتصال متقارن است @your company 

صفحه 12:
شرح رسمی خوشه با توجه به مجموعه داده ©, بارامتر © و 1110865 آستانه ‎el gl angen rade‏ أس قسموصووه زاب رمي ققد شاخص: متصل: ۵,۵ ۵ : © و 0 به جكالى متصل هستند. حداكثر: 8,0 : اكر © 6 و © جكالى قابل دستيابى از 9 باشد. آنكاه © 0. (جلوكيرى از اضافه کاری) ‎cxf 3B‏ @your company 

صفحه 13:
> Are p and q density- reachable by some object 0? Indirectly density- reachable through a chain Is an object o in a cluster ls o a core object? Is o density-reachable by mee | or an outlier? | some core object? comp @your c 

صفحه 14:
eo DBSCAN 258! Input: The data set D Parameter: c, MinPts For each object p in D if p is a core object and not processed then C = retrieve all objects density-reachable from p mark all objects in C as processed report C as a cluster else mark p as outlier end if End For 

صفحه 15:
DBSCAN ‏الگوریتم‎ خودسرانه یک نقطه (] را انتخاب كنيد تمام نقاط تراكم قابل دسترسى را از 285 ۷۷۳ 0 و 1/61۳5 بازیابی کنید. اگر ۵ یک نقطه هسته باشد. يك خوشه تشكيل مى شود. اكر 6 يك نقطه مرزى باشد هیچ نقطه ای از 0 قابل دسترسى نيست و 0850810 از نقطه بعدى بايكاه داده بازديد مى كند. روند را تا زمانى كه تمام نكات بردازش شود ادامه دهيد. من 2 <عء ‎MinPts = .‏ @your company 

صفحه 16:
e 6 2522٠. * ©) 6۳/0 @ o-e 5 "=e, 0 ۰ 1. Check the unprocessed objects in C 2. If no core object, return C 3. Otherwise, randomly pick up one core object p,, mark p, as processed, and put all unprocessed neighbors of p, in cluster 0 MinPts = 5 ° 9 ۰ ۵ ٩م‎ © © © © ۰ 0 © e ® 1. Check the e- neighborhood of p; 2. If p has less than MinPts neighbors then mark p as outlier and continue with the next object 3. Otherwise mark p as processed and put all the neighbors in cluster CS @your com 

صفحه 17:
5 6 

صفحه 18:
Original Points Point types: core, border and outliers @ your comps = 10. MinPts = 4 aie 

صفحه 19:
‎DBSCAN 53, ©‏ خوب کار مى کند ‎ ‎Original Points Clusters ‏0 مقاوم در برایر نویز ‏0 _می تواند خوشه هایی با شکل و اندازه های مختلف را اداره کند ‎@your company ‏اج مه‎ 

صفحه 20:
وقتی 0856۷ خوب کار نمی کند (MinPts=4, Eps=9.92). Original Points + Cannot handle Varying densities + sensitive to parameters (MinPts=4, Eps=9.75) @your company 

صفحه 21:
تعیین پارامترهای ۶ و ۷۱۱۳/5 Text Goes Here MinPts ,€ long 5 oo dyna 5 3) ML, abs gLite Cluster ايده عريض: از چگالی نقطه ای کمترین چگالی خوشه در مجموعه داده به عنوان پارامتر استفاده کنید - اما چگونه می توان ‎Col‏ )| تعيين كرد؟ اکتشافی: به فواصل تا >-نزدیکترین همسايه نكاه كنيد تابع ‎jl alo -k-distance(p)‏ ۵ نا -تزدیک ترین آن همسایه نمودار 1 :1503۳66 فاصله همه اشیاء به ترئیب کاهشی مرتب شده اند ‎3-distance(p) :: ———+‏ 9 3-distance(q): —» @your company 

صفحه 22:
> خوشه بندی بر اساس چگالی:بحث مزايا خوشه ها می تونند شکل و اندازهدلخولهداشته باشتد. ا تعداد خوشه ها به طور خودکار تميين م شود می تواند خوشه ها را از تویزهای اطراف جدا کند مى تواند توسط ساختارهای شاخص فضایی پشتیبانی شود معایب تعیین پارامترهای ورودی ممکن است دشوار باشد در برخی شرایط یه تنظیمات پارامتر ورودی بسیار حساس است @your company 

صفحه 23:
DBSCAN Python 

صفحه 24:
> DBSCAN Python 0 در نمودار بالاء نقاطی که به خوشه‌ها تخصیص داده شده‌اند سخت هستند. نقاط «نویز» (10156) در تصویر به رنگ سفید و نمونه‌های مرکزی به صورت نشانگرهای بزرگی نمایش داده شده‌اند. این در حالی است که نقاط مرزی به صورت نشانگرهای کوچک‌تری نشان داده شده‌اند. افزایش 605 (حرکت از چپ به راست در تصویر) بدین معنا است که نقاط بیشتری در خوشه‌ها قرار داده خواهند شد. این کار موجب می‌شود که خوشه‌ها رشد کنند. در عين حال ممکن ااست منجر به آن بشود که جندين خوشه به يك خوشه ببيوندند. افزایش ۲۱1_58۳0۳165 (حرکت از بالا به پایین تصویر)؛ به معنای آن است که نقاط کمتری نقاط مرکزی خواهند بود و نقاط بیشتری به عنوان نویز در نظر گرفته خواهند شد. 0_پرامتر 605 مهم‌تر است. زیرا مشخص می‌کند كه براى نقاط. نزدیک بودن چه معنایی دارد.تنظیم 6/05 روی یک مقدار خیلی کوچک بدان معنا است که هیچ نقطه‌ای, نقطه مرکزی نیست و امکان دارد منجر به آن شود که همه نقاط به عنوان نویز برچسب‌گذاری شوند. تنظیم 605 روی یک مقدار خیلی بزرگ ممکن است منجر به آن شود که همه نقاط در یک خوشه قرار بگیرند. اکنون به مثال بازگشته و بررسی می‌شود که 28502۸0] چگونه با داده‌های تولید شده در بالا که شکل خاصی داشتند مواجه خواهد شد. @your company 

صفحه 25:
‎eae et ete)‏ «ممما ‎aler ‎te‏ ل ا ‎re mples = 2)‏ ‎vce)‏ اند ‎Stree raat est‏ ‎paca matte fats 1 ‏ل‎ tea at iar ‎ 

صفحه 26:
> DBSCAN Python پس از ‎«sae gly min_samples ,eps ax‏ خوشه‌های نسبتا سازگاری حاصل شد که هنوز هم شامل نقاط نویز هستند. در حالیکه 85020 2] نیازی به آن ندارد که تعداد خوشه‌ها صراحتا به آن داده شوند. نتظیم 605 موجب می‌شود که به طور ضمنی تعداد خوشه‌هایی که باید پیدا شوند توسط الگوریتم کنترل شود. یافتن یک تنظیمات خوب برای 605 گاهی پس از مقیاس دادن داده‌ها آسان‌تر است. زیرا استفاده از روش‌های مقیاس‌دهی این اطمینان را به وجود می‌آورد که همه ویژگی‌ها دارای طیف مشابهی هستند. در نهایت. با در نظر داشتن این موضوع که داده‌ها یه نوعی ساخته شده‌لند که پنج خوشه را صراحتا تعریف کنند. می‌توان کارایی را با استفاده ‎adjusted_rand_score j‏ اندزهگیری کرد. لین کار در مسائل واقعی انجام‌پذیر نیست. زيرا در آنها برچسب‌های خوشه برای آغاز کار موجود نیستند اصلا به دلیل موجود نبودن داده‌های برچسب‌دار نیاز به اعمال روش‌های خوشه‌بندی به جای دسته‌بندی است) با توجه به اینکه در اين مثال ‏برچسب‌ها موجود هستند. می‌توان کارایی را اندزه‌گیری کرد ‎@your company 

صفحه 27:
bee dle DBSCAN ‏الگوریتم‎ 0 DBSCAN Python متیزکارایی ۰.۹۹ را به دست آورد. در حاليكه 1/18305©)! امتياز كارايى ۷۶ دا 

صفحه 28:
DBSCAN Example © ۵ یکی از تفاوت‌های اصلی این الگوریم با 460/15 اين است كه الكوريتم 0850:4380 نياز به تعيين تعداد خوشه توسط كارير ندارد و خود الكوريتم مىتواند خوشدها را مبتنى ابر لظت آنها شناسایی کند.اجازه بدهید در اين درس ببينيم که این الكوريتم جكونه مىتوائد غلظت را شناسایی کند و خوشه‌ها را در میا دادههای مختلف از یکدیگر تفکیک داده و شناسایی کند مختلف در حال گفتگو با یکدیگر هستند.منند شکل زیر 0 تصور كنيد در بالای یک پرج چند طبقه هستید و پایین بُرج انسانهابى قرار دارتد. اين آدم ها د, © حال به شما مىكويند اينها را كروهبتدى كنيد. احتمالا یکی از روش‌هایی که به .2 ذهنتان می‌رسد گروه بندي اين افراد بر حسب تراکمی است که که در آن قرار دارند: عمکن اسنتة گوو‌پندي شما مانند؛ شکل تزیر باشده ۲ sure @your company 

صفحه 29:
DBSCAN Python در واقع شما با استفاده تراکم و غلظتی که از بالا می‌دیدید. اين افراد را خوشه‌بندی کرده‌اید. همین کار توسط الگوریتم 285)2۸0] انجام می شود. در الگوریتم 0856/0(۷] دو پارامتر وجود دارد. یکی از آن‌ها شعاع است که به آن ۳511080] نیز می‌گویند و دومی حداقل نقاط موجود در یک خوشه است که به آن 11889801865 می‌گویند. نحوه‌ی کار الگوریتم ساده است. این الگوریتم ایتدا یک نمونه (که همان یک نقطه در فضای برداری می‌شود) را انتخاب می‌کند و با توجه به شعاع 05/1010 به دنبال همسابه برای این نقطه در فضا می‌گردد). اگر الگوریتم در آن شعاع مشخص ۴05110۳ حداقل توانست به تعداد 1110158011 نقطه بيدا كند. آنكاه همدى آن نقطدها با هم به يك خوشه تعلق مىكيرند. الكوريتم سيس به دنبال يكى از نقطه‌های همجوار نقطه فعلی می‌رود تا دوباره با شعاع ۴0511010 در آن نقطه به دنبالٍ نقاط همسايه ديكر بگردد و اگر تعداد نقاط همسایه‌ی جدید بازهم پیدا شوند. این الگوریتم دوباره همه آن نقاط جدید راب نقاط قبلی به یک خوشه متعلق می‌کند و اگر نقطه‌ی جدیدی در همسایگی پیدا نکرد این خوشه تمام شده است و براى بيدا كردن خوشه‌های دیگر در نقاط دیگر, به صورت تصادفی یک نقطه دیگر را انتخاب کرده و شروع به یافتن همسایه و تشکیل خوشه‌ی جدید یرای آن نقطه می‌کند. این کار آنقدر ادامه پیدا می کند تا تمامی نقاط بررسی شوند. @your company 

صفحه 30:
DBSCAN © © مىخوافيم اين هارا توسظ الكوريتم ‎DBSCAN‏ به خوشدهاى مختلف تقکیک کنیم: 0 همان طور که گفتیم یک نقطه را به صورت تصادفي در فضا انتخاب ميكنيم. ما از نقطه بالا سمت راست شروع ميكنيم. در ضمن در این فرآیند. مقدار 00۳75 را رایر ۲ @your company 

صفحه 31:
DBSCAN 0 همان طور که می‌بینید. در یک شعاع مشخص, حداقل انمونه در شعاع تموندى مركزى قرار دارند. بس اين نمونه مى تواند به عنوان يك خوشه انتخاب شود. مثلا رنك قرمز را براى اين خوشه انتخاب مى كنيم. حال به سراغ نمونه همسایه ای نقطه مى رويم و آن را مانئد شكل زير بررسى مىكنيم: © همان طور كه نموندى قبلى فرمز رف شده يود. با توجه به اينكه اين نمونه هم حداقل * نقطه در شعاع دور خود ذارده بس اين نمونه هم به خوشه قبلى ما (خوشه‌ی قرمز رنگ) می‌پیوندند و قرمز رنگ می‌شود. حال برای نقطه‌ی همسایه نیز این کار را انجام مىدهيم: @your company «o> 

صفحه 32:
DBSCAN © © اين كار ادامه بيدا مىكند تا زمانى كه ديكر نقطداى در ميان خوشدهاى نزديك همسايدها نباشد. مانند شكل زيرء كه تمامي نمونههاى بالاى شكل را به خوشههاى رمز نسيت فادها قرمز یم 0 _همان‌طور که می‌بینید. با پیشروی در میان همسایه‌های یک تمونه. توانستیم تمامی قبوه‌های غوشه‌ی بالاین رأ شناساین کنیم.وعحه آن:ها را هیک خوفه نیت دمیه الب ممکن است تمامي نمونه‌ها در همسایگی, دارای حداقل ۳همسایه نباشند. به این نمونه‌هاء نقطه های مرزی یا حاشیه (00۳616۲) گفته می‌شوند. مثلا در همان شکل بالاء در ميان خوشهى قرمز رنك. ممكن است نمونهاى كه انتهاى سمت جب قرار دارده يك نقطه مرزى باشد كه تعداد. نموندهاى داخل شماع آن» براى مثال ۲باشد. در مقاله‌ی اصلي الگوریتم. به نقاطی که حداقل میزان 11۳015 را در شعاع خود داشته باشند. نقاط هسته يا ۲۵۲6 می گویند. _الگوریتم به همین ترتیب ادامه پیدا میکند. هنگامی که یک خوشه (مانند خوشه‌ی قرمز بالا) تشکیل شد. یک نقطه‌ی تصادفی دیگر را انتخاب می‌کنيم. برای مثال ممکن است نقطه‌ی تصادفی جایی در نقاط سمت راست شکل باشد. این نقطه می‌تواند باعث شروع ایجاد یک ‎de‏ خوشه‌ی دیگر بشود. بای مثال خوشه‌ی سبز رنگ در شکل زیر ایجاد می شود ‎ ‎@your company 

صفحه 33:
DBSCAN الان دو خوشه را ساختیم. به همین ترتیب میتوان خوشه‌های دیگر را نيز ساخت. توجه کنید هنگامی که یک خوشه به صورت کامل ساخته می‌شود. الگوریتم به دنبال نقاط دیگر در فضا به صورت تصادفی می‌گردد. حال فرض کنید یک نمونه مانند شکل زیر پیدا شد که در شعاع مورد نظر الكوريتم. به تعداد کافی نمونه پیدا نکرد: همانطور كه مىينيد. اين نمونه در شعاع خود. کمتر از مورد نمونه درد.الگوریتم 28500 اين نمونه را به عنوان داده‌ی پرت یا 8۲أأنألا0) شناسایی می‌کند و به هیچ خوشه‌ای نسبت نمی‌دهد. لبته الگوریتم بایستی تمامي خوشه‌ها را بسازد و تمامي نقاط را بررسی کند تا بتاندبفهمد یک نقطه پرت است یا خیر الگوریتم همین طور ادامه پیدا می‌کند تا يتواند خوشه‌های دیگر را که حداقل ‎ay‏ اندازه‌ی آنمونه شعاع خود دارند. خوشه‌بندی کند و در آخر آن‌هایی که به هیچ خوشه‌ای نسبت داده تشده‌اند: به عنوان خاده‌ی پرت شناسایی می‌شوند. الگوریتم 085۵1 حساس به دو پارامتر ۷1۳۵165 و پارامتر شعاع است و هر چه شعاع را کوچکتر در نظر بگیرید. خوشه‌های بیشتر و کوچکتری تشکیلی می‌شود. همچنین هر چه قدر 1/0801 را بزرگ‌تر در نظر بگیرید. احتمال ایجاد خوشه‌ها. کمتر می‌شود زرا الگوریتم باید تعداد نمونه‌های بیشتری را در یک شعاع خاص ببینید تا خوشه را ‎@your company‏ 

صفحه 34:
Clustering 

صفحه 35:
اپتیک: نقاط ترتیب برای شتاسایی نساختار خوشه بندی HDBSCAN ‏بارا ورودى -حميين أن سفت أسسد‎ 8 0 _ الگوریتم بسیار حساس به پارامترهای ورودی. 0 ابتیک - آنکرست. برونیگ, کریگل و ساندر6161۸0099) ۵ براسای ‎DBSCAN‏ 0 خوشه ها را به صراحت تولید نمی کند. _ در عوض ترتیبی از اشیاء داده را که ساختار خوشه‌بندی مبتنی بر چگالی را نشان می‌دهند. ایجاد کنید. @your company 

صفحه 36:
Top 4 Benefits optics 

صفحه 37:
فاصله هسته و قابلیت دسترسی @ Parameters: “generating” distance ¢, fixed value MinPts Bicore-distance , yjinpis(O) “smallest distance such that o is a core object” (if that distance is < ¢; “?” otherwise) MinPts =5 Wreachability-distance , yinp;s(P, 0) “smallest distance such that p is directly density-reachable from o” (if that distance is <¢; “?” otherwise)|— reachability-distanceta,o) @your company --> 

صفحه 38:
OPTIC @ Order points by shortest reachability distance to guarantee that clusters w.r.t. higher density are finished first. (for a constant MinPts, higher density requires lower «) @your company =“ 

صفحه 39:
Optic Algorithm © ‎data structure: controlList‏ لا ‎CiMemorize shortest reachability distances seen so‏ ‎far ‎(“distance of a jump to that point”) Visit each point QOMake always a shortest jump Output: Qlorder of points Ocore-distance of points ‎ ‎ ‎Oreachability-distance of points ۰+ 

صفحه 40:
‎Sats‏ طرح قابلیت دسترسی نشان دهنده خوشه بندی مبتنی بر چگالی الست ساختار آسان برای تجزیه و تحلیل ‏مستقل از ابع ‎ ‏فاصله دسترسی ‎ ‎ ‎cluster ordering cluster ordei ‎ 

صفحه 41:
[إعوكه عساسيته بازاتر ۵ :نیت به عظيبات: بازامجر عساس فيسب 0 _نتیجه خوب اگر پارامترها فقط "به اندازه کافی بزرگ " باشند MinPts = 10, € = 10 MinPts = 10, €=5 MinPts = 2,¢=10 1 3 1 243 

صفحه 42:
DBSCAN VS OPTICS 085۵ | مقدار عددى (فاصله دسترسى) مقدار بولى (بلهاخير) چگالی متصل @your company o> 

صفحه 43:
عهماها_ 0۵۱۵ ل ‎ae Tae a Ce‏ ل ایا مم 35 لامسنه عمومسنا ‎Let‏ ا ار 0 - ین ‏لا ا ا 0 ‎acs Te)‏ ا ال ‏"عدا - لوطغعم_ عع وساءا ‎ep eee ee ec)‏ ‎el Gee eee ee ee ea ‏ا ا‎ ‏,6]عروط_ععذمعع)‎ asc eT el Sar ee ma Cec ‎ara ce a ee ee ae oe ee Roe od) ‏15ءمه1‎ - 00. ole ele Tee ‏(136615)ع0و1منا.مم)مع1‎ ( ‎no_noise = np.sum(np.array(labels) == -1, axis=0)print('Estimated no. of clusters: %d' % no_clusters) ‎ce Se Me em ee ae Cee ae eee Cac‏ را الا ون ‎BCE GC LT Meee 7 ic age ee Le yy Ie) ‎ce Tea}‏ اي ال ل ‎as Ceca ie tran)‏ افو فصن ‏('[0]» كتعنه' )1ءمقا»:.غاما ‏('[1]» كته تن ‏سس ‎ 

صفحه 44:


صفحه 45:
B.I.R.C.H Algorithm B alanced terative educing and 6 lustering using ierarchies @your company 

صفحه 46:
> eo0000 000000 Data Clustering &Problems یک الگوریتم داده کاوی بدون نظارت که برای انجام خوشه بندی سلسله مراتبی بر روی مجموعه داده های به خصوص بزرگ استفاده می شود. خوشه بندی داده ها خوشه - يك گروه فشرده. - مجموعه ای از اشیاءداده که مشابه یکدیگر هستند و به طور جمعی به عنوان یک گروه در نظر گرفته می شوند خوشه بندی داده ها - پارتیشن بندی یک مجموعه داده به خوشه ها. خوشه بندق داده ها - مشکلات مجموعه داده خیلی بزرگ است که در حافظه اصلی قرار نمی گیرد. # عملیات ورودی/خروجی بیشترین هزینه را دارد (زمان جستجو روی دیسک مرتبه‌ای بالات از زمان دسترسی به اله |/ ‎BIRCH‏ هزینه ورودی/خروجی را به صورت خطی در اندزه مجموعه دادهارائه می دهد. @your company 

صفحه 47:
> BIRCH advantages راه حل های دیگر الگوریتم های خوشه بندی مبتنی بر احتمال ‎(CLASSIT , COBWEB)‏ الگوریتم‌های خوشه‌بندی میتنی بر فاصله (۲/۸8۵0105 1۱۸۶۸۸۱5۰ و ‎(CLARANS‏ ‏مزایای 81861۱ محلى است كه هر تصمیم خوشه بندی بدون اسکن تمام نقاط داده و خوشه های موجود انجام می شود. از این مشاهدات استفاده می کند که فضای داده معمولا به طور یکنواخت اشفال نمی شود و هر نقطه داده به یک اندازه مهم نیست. استفادهکامل از حافظه موجود برای بدست آوردن بهترین زیرمجموعه های ممکن در حالی که هزینه های ورودی/خروجی را به حداقل می رساند. همچنین یک روش افزایشی است که از قبل به کل مجموعه داده نیاز ندارد. ‎@your company‏ 

صفحه 48:
> مفاهیم و اصطلاحات 8۱۳۳۱ pettus piney aids الگوریتم با خوشه های تک نقطه ای شروع می شود (هر نقطه در پایگاه داده یک خوشه | سپس نزدیک‌ترین نقاط را در خوشه‌های جداگانه بندی می‌کند و ادامه می‌دهد تا تنها یک خوشه باقی بماند. محاسبه خوشه ها با کمک ماتریس فاصله ((0)۳) بزرگ) و (00)117 زمان انجام می شود. ویژگی ‎BIRCH x98)‏ یک درخت ویژگی خوشه بندی (درخت 6۴) را در حین اسکن مجموعه داده ایجاد می کند. ‏هرورودی در درخث 6۴ نشان دهنده یک خوشه از اشياء است و با یک سنه (55 1۰ ‎٩۰‏ مشخص می شود ‎@your company 

صفحه 49:
ه هو هو و و و و و هو و و X, G=1, 2,3, بردار ۴ خوشه به صورت یک 2۳ سه كانه - ‎(NJLS,SS)‏ تعریف می شود > ‏ارچ‎ Buse « pau Nid gu awe oe, - ل(-تعداد نقاط داده در خوشه - 5ا -مجموع خطی لا نقطه داده - 55 -مجنوع نزیع ] نقطه داده درختی با ارتفاع متعادل با دو پارامتر - فاکتور انشعاب 8 - آستانه ۲" اهر كره غير برك حداكثر حاوى 8 از فرم [11110© ,:01):] است. كه در آن فرزند: يك اشاره كر به فرزند أ-ام آن است. گره و ۴م) :۳م) زیرخوشه ای است که این کودک نشان می دهد. بنابراین. یک گره غیر برگ نشان دهنده یک خوشه است که از همه آنها تشکیل شده است .زیرخوشه هایی که با ورودی های آن نشان داده می شوند @your company 

صفحه 50:
هه هو هو هو هو مفاهیم و اصطلاحات 8۱۳۲۱ اندازه درخت تابعی از ۲ است (هرچه ۲ بزرگتر باشد درخت کوچکتر است). ما به یک گره نیاز داریم تا در صفحه ای به اندازه ۳ قرار گیرد. 8 وا توسط8 تعييزهمى شوند (7 را مئتولنبرلئتنظيم عملكرد تغيير داد). تمايش بسیار فشرده از مجموعه داده زیرا هر ورودی در یک گره برگ یک نقطه داده واحد نیست بلکه یک خوشه فرعی ا برگ شامل خوشه های واقعی است. * اندزه هر خوشه در یک برگ بزرگتر از آ نیست @your company 

صفحه 51:
CF TREE یک گره برگ حداکثر دارای ورودی های .| است که هر یک از آنها به شکل [0۳):] است که ا,...,2 ,1 همچنین دارای دو نشانگر 0۳6۷ و 060 است که برای زنجیره زدن تمام گره های برگ به یکدیگر برای اسکن کارآمد استفاده می شود. یک گره برگ همچنین خوشه ای را نشان می دهد که از تمام زیرخوشه های نشان داده شده توسط ورودی های آن تشکیل شده است. اما همه ورودی‌های یک گره برگ باید یک شرط آستانه را یا توجه به مقدار آستانه 7 برآورده کنند: قطر (یا شعاع) باید کمتر از ۲ باشد @your company 

صفحه 52:


صفحه 53:
> نمونه‌ای از درخت 0۲ 0 _در ایتدا داده ها در یک خوشه قرار می گیرند. 0 داده ها می رسد و بررسی می شود که آیا اندازه خوشه از ۲ بیشتر نیست. 0 اگر اندازه خوشه خیلی بزرگ شود. خوشه به دو خوشه تقسیم می شود. و امتیازها دوب » درخت .) اطلاعاتی در مورد میانگین خوشه ۸۸ و ميانگي دارد. توزیع می شوند. خوشه ها به طور موثر نگه می @your company 

صفحه 54:
CF Tree Insertion ‏نمونه دیگری از‎ © 0 اگر ضریب انشعاب یک گره برگ نتواند از ۳ تجاوز کند. لااا تقسیم می شود. 3 ‏م‎ 02 2 Root ‎LN1”‏ "ثلا ‎@® LN1’ LN3 563 sc2 ‎ ‎ ‎5 ‎2 ‏& ‏0 ‏ات ‎sc8 901 502 3 504 5 506 7 ‎@your company 

صفحه 55:
الگوریتم 8۱8۷ @your company 

صفحه 56:
فاز ۴ اختیاری) 0 _ ارسال‌های اضافی روی داده‌ها برای تصحیح نادرستی‌ها و اصلاح بیشتر خوشه‌ها 0 از مرکز خوشه های تولید شده توسط فاز ۳ به عنوان دانه استفاده می کند و نقاط داده را به نزدیک ترین دانه خود براى به دست آوردن مجموعه ای از خوشه های جدید دوباره توزیع می کند. © به حداقل همكرا مى شود (مهم ‎gh ig Cosi‏ 185 وف ‏0 كزينه دور انداختن خطوط کلی. ‎> ‎° ‏ه ه ه ه ‏شرح فاز ها ‏غاز ۳ مشکلات بعد از فاز ۱: ‏- ترتیب ورودی بر نتایجتأثیر می كذارد. ‏- تقسیم توسط اندازه گره ایجاد می شود. ‏فاز ۲ ‏از ‏- از يك الكوريتم سراسرى يا نيمه جهانى براى خوشه بندى تمام ورودى هاى برك استفاده مى کند. ‏- الگوریتم خوشه‌بندی سلسله مراتبی تجمعی تطبیقی مستقیماً به زیر خوشه‌هایی که توسط بردارهای 6۴ نشان داده شده‌اند اعمال می‌شود. ‏فاز ۲ (اختیاری) آماده سازی برای فاز ۳ ‏به طور بالقوه. فاصله ای بین اندزه فاز1] وجود درد نیج و محدوده ورودی فاز ۳ ‏ورودی‌های برگ در درخت ‎CF‏ ‏اولیه را اسکن می‌کند تا یک درخت م) کوچک‌تر را بازسازی کند. در حالی که خطوط ‎AS‏ ‏بیشتری را حذف می‌کند و زیرخوشه‌های شلوغ را به خوشه‌های بزرگ‌تر گروه‌بندی می‌کند. ‏فاز 1 تن آلید شرع شود قاده ها را اسکن می کند و تقاط ‎al,‏ درخ وار می کند ‏اكر قبل إز اتمام اسکن داده ها حافظه أن تمام شود مقدار آستانه را افزايش مى دهد ويك ‎CF ess‏ جدید و کوچکتر را بازسازی می کند. ‏با درج مجدد ورودی های برگ از دزخت هن تر و ‏سپس انسکن داده ها از نقطه ای که در آن قطع شده است از سر گرفته می شود. ‏آستاهالیه خوب مهم است اما تشخیص آن سخت است. ‏حذف پوت (هنگام بازسازى ‎@your company cae 

صفحه 57:
Pros & Cons 0 Pros Cons از آنجایی که هر گره در یک درخت 6 بهدلیل ندزه می ‎Birch Pe a ae ee Sees 2‏ سریعتر از نگوییتمهاوموجود (1۵/۵(15) و خوشه طبيعت در نظر بكيرد مطابقت ندارد. ‎KMEANS‏ رییم جبعه دادم های رکه ملم ‎oS‏ ‏علاوه بر اين. اكر خوشدها به شكل كروى نباشئد. عملكرد اناده :هارا فعا يك بر مسق ميقل خوبی ندارند زر از منهوم شعاع یا قطر برای کنترل موز یک با موارد برت بهتربرخورد می کند. .خوشه استفاده می‌کنند در پایداری و مقیاس پذیری نسبت به ساير الكوريتم ها برتری دارد. @your company 

صفحه 58:
‎SCT)‏ ا ‏۴ 5و 0۷۵۱۵۶ 1000۳6 0۵10101110 ۱۲۲۵۲۱ ‎import seaborn as sns ‎sns.set() ‏الت 968۴6۲۵۲۵۲ 58000۵165 , 5۱۱۵۵۲۵۰0۵۲۵5615 ۱۲۲۵۲ ‎import Birch‏ ات رت نينا ‎centers=6,‏ را ا ا که ‎cluster‏ ‎plt.scatter(X[ X[:,1], alpha=0.7, edgecolors='b') ‎ 

صفحه 59:
BIRCH Python bre = Birch(branching_factor=50, n_clusters=None, threshold=1.5) 9۳6۰۶1۲) labels = brc.predict(X) plt.scatter(X[:,0], X[:,1], c=labels, cmap='rainbow', alpha=0.7, edgecolors='b 

صفحه 60:
References & Resources °o Articles 6 BIRCH: an efficient data clustering method for very large databases by Tian Zhang ۵ BIRCH: A New Data _~ Clustering Algorithm and (S)itsi@ypplications © Density Based Approaches .University Of websites © https://blog.faradars.org/dbscan-algorithm- in-python/. © https://towardsdatascience.com/machine-learning-birch- clustering-algorithm-clearly-explained-fb9838cbeed9 © https://chii © https://dhavalthakur.medium.com/machine-learning-all-about-optics- clustering-implementation-in-python-85d7¢76a23d5, ir @your company 

صفحه 61:
oo HOW ? ATT ed Any Questions ??? WHERE ?