الگوریتم LBG

LBG (Linde–Buzo–Gray)

این الگوریتم توسط Linde،BuzoوGray در سال 1980 معرفی شد. و به منظور برطرف شدن چالشهای الگوریتم K-mean  (تعیین تعداد خوشه ها در ابتدا )که از روشهای پایه خوشه بندی است ، از الگوریتم LBG  استفاده میشود.

الگوریتم LBG یکی از الگوریتم های اکتشافی است . روند اجرایی LBG به این صورت است که در ابتدا یک خوشه در نظر گرفته می شود ، به عبارتی تمام دیتاها  در قالب یک خوشه (K=1) قرار می گیرند.

سپس برای این خوشه یک بردار مرکز محاسبه می‌کند.(اجرای الگوریتم K-Means با تعداد خوشة (K=1) سپس این بردار را به 2 بردار می‌شکند و داده‌ها را با توجه به این دو بردار خوشه‌بندی می‌کند (اجرای الگوریتم K-Means با تعداد خوشة K=2 که مراکز اولیه خوشه‌ها همان دو بردار هستند). در مرحلة بعد این دو نقطه به چهار نقطه شکسته می‌شوند و الگوریتم ادامه پیدا می‌کند تا تعداد خوشة مورد نظر تولید شوند .

عملکرد LBG را می توان به صورت دیگری نیز بیان کرد:

1-    LBG در ابتدا  با 2 کلاستر (خوشه) شروع می شود (اجرای K-Means با 2 کلاستر تا رسیدن به همگرایی).

2-    تعیین واریانس خوشه ها .کلاستری که بیشترین واریانس را دارد به دو کلاستر تقسیم می شود(به طور کلی ،3 خوشه).

3-     K-Means مجددا اجرا می شود تا به  همگرایی برسد(در حال حاضر با 3 خوشه).

4-    مرحله 2 و3 الگوریتم تکرار می شود تا زمانیکه تمام کلاسترها یافت شوند.

این الگوریتم به ما بهترین خوشه ها را می دهد بجای اینکه ، با K-Means در ابتدا کار با تعداد مشخصی از کلاستر (K) شروع کنیم. ما میتوانیم بجای اضافه کردن یک کلاستر در هربار (زمان) ،  در هر جایی که کلاستر تفکیک شده ، تقسیم کننده باینری انجام دهیم. با تفکیک و جدا سازی یک کلاستر، فقط یک وکتور جزئی (بردار) به عنوان  وکتورپارازیت اضافه شده  و از کلاستر اصلی که  بزرگتر است  با کلاستری که اختلال-نویز اندکی دارد کارا آغاز میکنیم برای دور بعدی(مرحله ) K-Means.