کاهش و خوشه بندی ترازمند و بازکردی با بهره گیری از رده بندی ( balanced iterative reducing and clustering using hierarchies ) که در زبان انگلیسی به شکل مخفف به آن BIRCH گفته می شود، یک الگوریتم خوشه بندی سلسله مراتبی می باشد. این روش یکی از روش های یادگیری خودران می باشد که از آن جهت داده کاوی روی دادگان بزرگ و حجیم استفاده می شود.
از این الگوریتم برای سرعت بخشی به الگوریتم خوشه بندی کی - میانگین نیز استفاده می شود. مبتکران این الگوریتم از آن به عنوان اولین الگوریتم در حوزه دیتابیس که به شکل مؤثر نویز در داده را مدیریت می کند یاد می کنند. [ ۱] توانایی این الگوریتم در خوشه بندی داده هایی که به شکلی افزایشی و پویا به دست می آیند، آن را برجسته و از دیگر الگوریتم ها متمایز می کند.
الگوریتم های خوشه بندی ارائه شده پیش از این الگوریتم، عملکرد ضعیفی روی داده های بزرگ و حجیم داشتند. همچنین آن ها نیاز داشتند که کل داده های در حافظه برای دسترسی موجود باشد و این برای مجموعه داده هایی که در حافظه اصلی کامپیوتر جا نمی شدند مشکل ساز بود. این الگوریتم با توانایی به کارگیری داده ها به شکل پویا، مشکلات موجود در الگوریتم های قبلی را برطرف کرد.
ورودی های این الگوریتم مجموعه ای از بردارهای حقیق به اندازه N و عدد K که به نشان دهنده تعداد خوشه ها است، هستند. الگوریتم شامل ۴ مرحله می باشد:
• مرحله اول: درخت ویژگی خوشه بندی روی داده ها تشکیل می شود. نحوهٔ تشکیل این درخت به شرح زیر است:
• ویژگی خوشه بندی داده ها به شکل یک سه تایی C F = ( N , L S → , S S ) {\displaystyle CF= ( N, {\overrightarrow {LS}}, SS ) } تعریف می شود که در آن L S → = ∑ i = 1 N X i → {\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}} جمع خطی بردارها و S S = ∑ i = 1 N ( X i → ) 2 {\displaystyle SS=\sum _{i=1}^{N} ( {\overrightarrow {X_{i}}} ) ^{2}} جمع مربع بردارها می باشد.
• ویژگی های خوشه بندی در یک درخت ویژگی خوشه بندی چیده می شوند. این درخت، درختی با ارتفاع متعادل. این درخت شامل دو پارامتر B {\displaystyle B} و T {\displaystyle T} می باشد که به ترتیب ضریب انشعاب درخت و یک متغیر آستانه می باشند. هر راس غیر برگ در این درخت حداکثر شامل B {\displaystyle B} عضو مانند {\displaystyle } می باشد که در آن c h i l d i {\displaystyle child_{i}} یک اشاره گر به به فرزند i {\displaystyle i} ام آن راس و C F i {\displaystyle CF_{i}} ویژگی خوشه متناظر با زیرخوشهٔ مربوط به آن فرزند می باشد. همچنین برگ های درخت شامل حداکثر L {\displaystyle L} عضو هرکدام به شکل C F i {\displaystyle CF_{i}} می شود. همچنین در برگ ها اشاره گرهایی به برگ ها قبلی و بعدی نیز وجود دارد که تمامی برگ های درخت را به یکدیگر متصل می کنند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاز این الگوریتم برای سرعت بخشی به الگوریتم خوشه بندی کی - میانگین نیز استفاده می شود. مبتکران این الگوریتم از آن به عنوان اولین الگوریتم در حوزه دیتابیس که به شکل مؤثر نویز در داده را مدیریت می کند یاد می کنند. [ ۱] توانایی این الگوریتم در خوشه بندی داده هایی که به شکلی افزایشی و پویا به دست می آیند، آن را برجسته و از دیگر الگوریتم ها متمایز می کند.
الگوریتم های خوشه بندی ارائه شده پیش از این الگوریتم، عملکرد ضعیفی روی داده های بزرگ و حجیم داشتند. همچنین آن ها نیاز داشتند که کل داده های در حافظه برای دسترسی موجود باشد و این برای مجموعه داده هایی که در حافظه اصلی کامپیوتر جا نمی شدند مشکل ساز بود. این الگوریتم با توانایی به کارگیری داده ها به شکل پویا، مشکلات موجود در الگوریتم های قبلی را برطرف کرد.
ورودی های این الگوریتم مجموعه ای از بردارهای حقیق به اندازه N و عدد K که به نشان دهنده تعداد خوشه ها است، هستند. الگوریتم شامل ۴ مرحله می باشد:
• مرحله اول: درخت ویژگی خوشه بندی روی داده ها تشکیل می شود. نحوهٔ تشکیل این درخت به شرح زیر است:
• ویژگی خوشه بندی داده ها به شکل یک سه تایی C F = ( N , L S → , S S ) {\displaystyle CF= ( N, {\overrightarrow {LS}}, SS ) } تعریف می شود که در آن L S → = ∑ i = 1 N X i → {\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}} جمع خطی بردارها و S S = ∑ i = 1 N ( X i → ) 2 {\displaystyle SS=\sum _{i=1}^{N} ( {\overrightarrow {X_{i}}} ) ^{2}} جمع مربع بردارها می باشد.
• ویژگی های خوشه بندی در یک درخت ویژگی خوشه بندی چیده می شوند. این درخت، درختی با ارتفاع متعادل. این درخت شامل دو پارامتر B {\displaystyle B} و T {\displaystyle T} می باشد که به ترتیب ضریب انشعاب درخت و یک متغیر آستانه می باشند. هر راس غیر برگ در این درخت حداکثر شامل B {\displaystyle B} عضو مانند {\displaystyle } می باشد که در آن c h i l d i {\displaystyle child_{i}} یک اشاره گر به به فرزند i {\displaystyle i} ام آن راس و C F i {\displaystyle CF_{i}} ویژگی خوشه متناظر با زیرخوشهٔ مربوط به آن فرزند می باشد. همچنین برگ های درخت شامل حداکثر L {\displaystyle L} عضو هرکدام به شکل C F i {\displaystyle CF_{i}} می شود. همچنین در برگ ها اشاره گرهایی به برگ ها قبلی و بعدی نیز وجود دارد که تمامی برگ های درخت را به یکدیگر متصل می کنند.
