الگوریتم LBG

لگوریتم LBG یا Linde–Buzo–Gray یک الگوریتم رقمی سازی برداری (vector quantization) است که با استفاده از آن می توان یک codebook مناسب بدست آورد. codebook  در حقیقت مجموعه مراکز بازه های رقمی سازی است. این روش مشابه روش k-means در خوشه بندی (data clustering) است.

  

بطور کلی الگوریتم LBG، یک الگوریتم نوع پیمایشی است. در ادامه به جزئیات این الگوریتم می پردازیم:
مشکل الگوریتم خوشه بندی  LBGپیشنهاد شد که به الگوریتم لوید تعمیم یافته  نیز مشهور
است این الگوریتم که توسط لیند و همکاران (1982)  ارائه شد قادر است به مقدار قابل قبولی بر این مشکل غلبه کند. در شکل (3-14)فلوچارت الگوریتمLBG نشان داده شده است. در این روش ابتدا الگوریتم تمام داده ها را به صورت یک خوشه در نظر میگیرد و سپس برای این خوشه یک بردار مرکز محاسبه میکند.)اجرای الگوریتم k-means با تعداد خوشه 1 K= (. سپس این بردار را به 2 بردار می شکند و داده ها را با توجه به این دو بردار خوشه بندی میکند )اجرای الگوریتم k-means با تعداد خوشه K=2 که مراکز اولیه خوشه ها همان دو بردار هستند(. در مرحلة بعد این دو نقطه به چهار نقطه شکسته میشوند و الگوریتم ادامه پیدا می کند تا تعداد خوشة مورد نظر تولید شوند. مراحل الگوریتم LBG را میتوان به صورت زیر بیان
کرد:
i0 شروع: مقدار M )تعداد خوشه ها( با عدد 1 مقدار دهی اولیه میشود. سپس برای تمام داده ها بردار مرکز
محاسبه میشود.

ii. شکست: هر یک از M بردار مرکز به 2 بردار جدید شکسته میشوند تا 2M بردار مرکز تولید شود. هر بردار
جدید بایستی درون همان خوشه قرار داشته باشد و به اندازة کافی از هم دور باشند.
K-Means: با اجرای الگوریتم K-Means با تعداد خوشة 2M و مراکز اولیه خوشه های محاسبه شده در
مرحلة ii خوشههای جدیدی با مراکز جدید تولید می شود.
شرط خاتمه: در صورتی که M برابر تعداد خوشه مورد نظر الگوریتم LBG بود الگوریتم خاتمه می یابد
و در غیر این صورت به مرحلة ii رفته و الگوریتم تکرار می شود.
 

در اینجا الگوریتم LBG برای موارد دو بعدی مطرح شده است. در این الگوریتم، مرکز ثقل به دو بردار - عنوان نخستین بردار کد برای مجموعه آموزشی محاسبه می شود. در شکل(2) v1 و v2 تولید شده اند. فواصل اقلیدوسی تمام بردارهای آموزشی با بردارهای v1 و v2 محاسبه شده، لذا دو خوشه براساس نزدیکی بردارهای آموزشی به هر یک از دو بردار کد v1 یا v2 شکل می گیرند. این رویه برای هر خوشه تکرار می شود. عیب اصلی این الگوریتم کشیدگی +1350 خوشه مورد نظر نسبت به محور افقی در موارد دو بعدی است. این امر منجر به خوشه بندی ناکارآمد می شود

 

شکل 2: LBG برای مورد دو بعدی

نمادهای مورد استفاده در این جا به شرح زیر تعریف می شوند.
m اندازه کد بوک.
k اندازه ی بردار کد
t تعداد بردارها در ترتیب آموزش.
n: تعداد تکرارهای مورد نیاز برای مواجه شدن با معیار توقف.
  ηLBG زمان محاسبه برای پیدا کردن فاصله بین دو بردار.
Tcom زمان واحد برای مقایسه دو مقدار اعوجاج()تحریف
دوم الگوریتم LBG: زمان محاسبه
الگوریتم LBG یک روش تکرار است که در هر تکرار هر بردار در ترتیب آموزش با تمام بردار های کد در نسخه فعلی کتاب کدبندی مقایسه شده و به همان خوشه به عنوان بردار کد مشابه تقسیم شده است.. به طور معمول، معیار شباهت، میانگین خطای مربع (MSE) یا MSE وزنی است. پس از هر تکرار، توالی کدوکتور ها با استفاده از مرکز لحظه هر خوشه به روز می شود. پس از هر تکرار، توالی بردار ها ی کد با استفاده از مرکز لحظه هر خوشه به روز می شود. معیار متوقف شدن زمانی که نسبت بهبود کلی تحریف به اعوجاج در تکرار قبلی کمتر از یک مقدار از پیش تعیین شده است، محقق می شود.
نشان دادن  کل محاسبه زمان برای الگوریتم LBG کار آسانی است.
(1)TLBG = ALBG + BLBG
در صورتی که:
 
ALBG زمان محاسبه تحریفات است و زمان BLBG برای مقایسه تحریف شده ها است. اثبات (1) به شرح زیر است: در ترتیب تمرین t بردار وجود دارد، هر یک از آن ها باید با تمام کد بردار ها مقایسه می شود. تعداد تکرارها n است،  و در هر تکرار باید حداقل در میان  mارزش تحریف ها محاسبه شود؛ این نیاز به مقایسه (1m - ) دارد. بنابراین، ALBG = nmtηLBG و BLBG = n (m - 1) tTcom . اگر MSE به عنوان اندازه ی فاصله در نظر گرفته شود، سپس عملیات مورد نیاز برای محاسبه ηLBG، اضافه کردن (2 k - 1) و ضریب k می باشد. گر بیشتر فرض کنیم که زمان پردازش مورد نیاز برای ضرب α برابر بیشتر از مقدار اضافی (tadd) است؛ ما می توانیم بنویسیم:
(2)ηLGB = ((2 + α)k - 1)tadd