مقایسه LBG-K-means-VQ

مقایسه LBG-K-means-VQ

خوشه بندی : در پستهای قبلی به مفهوم و کاربرد خوشه بندی اشاره شده است. خوشه بندی یک روش غیرنظارتی برای یافتن و گروهبندی داده های مشابه در یک مجموعه داده می باشد.

 در این پست سعی بر این است که به ارتباط و کاربرد سه روش LBG،K-means،VQ پرداخته شود.

  K-means :

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

 عملکرد K-means را از طریق این لینک  به صورت تصویری میتوانید مشاهده نمایید.

 با توجه به اینکه در این روش ،از ابتدا تعداد خوشه ها مشخص شده است و خوشه‌بندی K-Means به انتخاب اولیه خوشه‌ها بستگی دارد، نتایج خوشه بندی در حین تکرارالگوریتم ، متفاوت می شود ، از اینرو برای رفع این مشکل، الگوریتم خوشه‌بندی LBG پیشنهاد می شود که قادر است به مقدار قابل قبولی بر این مشکل غلبه کند.

همانطور که در شکل فوق مشاهده میکنید در هر step مرکز ثقل یا همان هسته مرکزی جابه جا می شود و به سمت مرکز خوشه ها حرکت میکند تا به بهترین نقطه یعنی میانگین خوشه ها برسد،همانطور که قبلا ذکر شد در روش K-MEANS تعداد خوشه ها از ابتدا مشخص و ثابت است اما در طول اجرا ، تعلق داده ها  به خوشه تغییر میکند، هر داده  (دایره ای کوچک )به مرکز خوشه ای (دایره های بزرگتر) که به آن نزدیکتر تعلق میگیرد.

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.

VQ( vector quantization)

کمی سازی برداری یا رقمی سازی برداری

همانطور که می دانیم  تنوع رنگ در طبیعت بسیار زیاد است.اما هنگام تصویر گرفتن از طبیعت و مشاهده تصویر گرفته شده با دوربین یا موبایل و ... میبینیم که ازبرخی از رنگها صرفنظر شده است (کاهش تعداد پیکسلهای رنگی)،

همچنین  باذخیره کردن تصویر به روی کامپیوتر،متوجه می شویم که تعداد پیکسلها کاهش یافته  است، یا پیکسلهای مشابه ادغام می شوند و یا پیکسلهای مشابه به روی سیستم  ثبت نمی شوند.

 یکی از پرکاربردترین متدها به منظور فشرده سازی تصاویر،  VQ می باشد. در پست مربوط در مورد VQ صحبت شده است. می دانیم که تصاویر به صورت باینری (دیجیتالی)،ثبت می شوند.

پیکلسلهای تصویر را میتوان در قالب  بلوکهای n*n در نظر گرفت. پیکسلها در هر بلوک به صورت سطر به سطر مرتب شده اند.   VQ  روشی است بر پایه متد خوشه بندی،یعنی گروه بندی کردن بردارهای (بلوک) مشابه در داخل یک کلاس. بردارها  از دل داده هایی که از تصویراستخراج شده اند و به شکل بلوکهای n*n   هستند بدست می آیند(مثلا 4*4).

روند فشرده سازی تصویر با VQ در سه فاز انجام می شود:

-تولید کدبوک      -کدکردن (رمز گذاری)     -دکد کردن (رمز گشایی)

در فاز اول یعنی تولید کدبوک ، از قبل مجموعه ای از کلمه هایی کد شده مبتنی بر بردارهای آموزشی تصویری تولید شده اند.

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

با فشرده سازی تصویر ،رمز گذار( encoder ) ،آدرسی از کلمه کدها ایجاد میکند که به بردار تصویر ورودی نزدیک باشد. و رمز گشا(decoder) از این درسها برای بازیابی بردار تصویر استفاده میکند.

کتاب کد ،یک عامل کلیدی تاثیر گذار به روی کارایی فرایند فشرده سازی تصویر می باشد.

برای تولید کدبوک الگوریتمهایی ارائه شده اند. یکی ازآنها LBG است. این الگوریتم بر پایه تکرار است که مجموعه ای از کلمه کدهای نماینده را تولید می کند تا میزان تحریف و اعوجاج را در طول بردارهای آموزشی کاهش دهد و به حداقل رساند. این فرایند تولید کلمه کد،محاسبات فشرده ای دارد و برحسب انتخاب اولیه کلمه کد، نرخ اعوجاج ،تحت تاثیرقرار میگیرد. و ممکن  است در انتها کدبوکی کمتر از حد مطلوب بدست آید.

تعداد وکتورهای آموزشی را با M و تعداد کلمه کدها رابا N نشان میدهیم.

مساله طراحی کدبوک می تواند به عنوان یک مساله خوشه بندی فرموله شود که M بر N تقسیم می شو د که خود یک  مساله NP-hard است.برای M و N های بزرگ، یک الگوریتم جستجوی سنتی مانند LBG  به سختی میتواند طبقه بندی  بهینه کلی  را بیابد.

منابع :

1- An Algorithm for Vector Quantizer Design
A fast Linde-Buzo-Gray algorithm in image vector quantization

2 - کاربرد روشهای خوشه بندی در ترسیم نقشه های علم: موردکاوی نقشة علم مدیریت شهری

محمد ابویی اردکان-حسن عابدی جعفری-فتاح آقازاده ده ده/ فصلنامه علمی پژوهشی پژوهشگاه علوم و فناوری اطلاعات ایران-دوره 25/شماره 3/ص ص 347-371/بهار 1389

3-الگوریتم K-Means

4-خوشه بندی k-means (آموزش تصویری)

5- الگوریتم LBG

6- پروژه خوشه‌بندی آیات قرآن