خوشه بندی سلسله مراتبی
خوشه بندی سلسله مراتبی یکی از پرکاربردترین روش های خوشه بندی است.
خوشه بندی سلسله مراتبی تکنیکی است که در گروه بندی یا دسته بندی داده ها به کار می رود. نقاط داده ها در این روش در دسته ها و زیر دسته هایی بر اساس معیار شباهت قرار می گیرند.
در این روش به خوشه ی نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی، معمولا به صورت درختی نسبت داده می شود. به این درخت سلسله مراتبی دندوگرام می گویند. تکنیک کار این نوع خوشه بندی معمولا بر اساس الگوریتم های حریصانه است. از مزیت های خوشه بندی سلسله مراتبی، سادگی و قابلیت درک برای تمامی پژوهشگران است. این روش شامل مد لهای متنوعی است که میتواند نیازهای متعددی را رفع کند.
برای خوشه بندی مشاهدات با توجه به متغیرهای اندازه گیری شده برای هر مشاهده، فاصله ی بین مشاهدات را با متری که معمولا متر اقلیدسی است اندازه گیری می کنند. فاصله اقلیدسی فاصله ی بین دو مشاهده i و j را محاسبه می کند. روش محاسبه ی فاصله ی دو مشاهده با استفاده از فاصله اقلیدسی به صورت زیر است:
با استفاده از این روش فاصله ی بین مشاهدات را به صورت دو به دو محاسبه می کنیم و فاصله های بدست آمده را در ماتریس فاصله قرار می دهیم. بعد از تشکیل ماتریس فاصله، کوچکترین عدد در ماتریس فاصله را پیدا می کنیم. این عدد نشان دهند هی ایناست که دو مشاهده ی فوق کم ترین فاصله ی بین مشاهدات را از یکدیگر دارند، لذا می توان دو مشاهده را در قالب یک خوشه قرار داد. سپس از یکی از روش های ادغام استفاده می کنیم و آنها را ترکیب می کنیم. و در نهایت در درخت دندوگرام نمایش می دهیم.
دندوگرام یک نمودار دو بعدی است که هم به صورت عمودی هم افقی می توان آنرا رسم کرد نتایج در هر دو صورت یکسان است.
برای تعیین تعدادخوشه می توان دندوگرام را در یک نقطه مناسب برش داد. در این نمودار آنچه که اهمیت دارد ارتفاع است. هر چه خوشه های تشکیل شده در ارتفاع پایینتری ایجاد شده باشند خوشه ها یا مشاهدات به یکدیگر شبیه تر و بالعکس هستند.
خوشه بندی سلسله مراتبی در داد با بُعد بالا، به دلیل زمان زیادی که صرف محاسبات می نماید، مقرون به صرفه و گاهی نیز قابل محاسبه نیست. البته این مشکل را با خوشه بندی K-MEANS رفع می کنند.
مزیت این روش این است که به اطلاعات قبلی راجع به تعدادخوشه ها نیازی ندارد و عیبش، عدم وجود انتصاب مجدد در آن است.
این نوع خوشه بندی خود دارای دو روش بالا به پایین (تقسیم کننده) و پایین به بالا (تجمعی) می باشد که در پستهای بعدی به شرح آنها میپردازیم.
منبع:
دانلود خوشه بندی و روشهای آن
دانلود خوشه بندی K-means و سلسله در نرم افزارها
دانلود تحلیل خوشه بندی(ppt)
خوشه بندی k-means
این روش علی رغم سادگی آن یک روش پایه برای بسیاری از روش های خوشه بندی دیگر محسوب می شود. این روش برای مواقعی که تعداد محاسبات و تعداد مشاهدات بسیار زیاد است مفید می باشد.
این روش روشی انحصاری و مسطح محسوب می شود.
برای این الگوریتم شکل های مختلفی بیان شده است. ولی همه ی آنها دارای روال تکراری هستند که برای تعدادی ثابت از خوشه ها سعی در تخمین موارد زیر دارند:
- به دست آوردن نقاطی به عنوان مراکز خوشه ها که این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.
- نسبت دادن هر نمونه به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
- در نوع ساده ای از این روش ابتدا به تعداد خوشه های مورد نیاز نقاطی به صورت تصادفی انتخاب می شود. سپس در داده ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه ها نسبت داده می شوند و بدین ترتیب خوشه های جدیدی حاصل می شود. این روند تا زمانی ادامه پیدا می کند که دیگر تغییری در داده ها حاصل نشود.
در اولین انتخاب K نقطه، به عنوان مراکز هر خوشه تعیین میشود. سپس فاصله ی ، مشاهدات تا هر یک از مراکزی که مشخص شده، محاسبه میشود. مشاهداتی که کم ترین فاصله را تا هر یک از مراکز دارند، با هم تشکیل خوشه می دهند.
در خوشه بندی K-MEANS بر خلاف شیوه های سلسله مراتبی امکان جابه جایی مشاهد ه ای از یک خوشه به خوشه دیگر وجود دارد. در دومین انتخاب، میانگین خوشه هایی که در مرحله ی قبل محاسبه شده است را به عنوان مرکز در نظر گرفته، دوباره فاصله ی مشاهدات تا هر یک از مراکز جدید را محاسبه کرده، خوشه های جدید را تشکیل می دهیم. تعداد این تکرارها را در دومین انتخاب تعیین می کنیم.
دانلود خوشه بندی و انواع روش های ان
دانلود خوشه بندی K-means و سلسله در نرم افزارها
مقاله ی یک پیشنهاد تسریع شده در تشخیص جعل کپی-انتقال
Abstract—
Image forgery detection is currently one of the interested research fields of image processing. Copy-Move (CM) forgery is one of the frequently used techniques. In this paper, we propose a method which is efficient and fast for detect copy-move regions. The proposed method accelerates block matching strategy. Firstly, the image is divided into fixed-size overlapping blocks then discrete cosine transform is applied to each block to represent its features. Fast k-means clustering technique is used to cluster the blocks into different classes. Zigzag scanning is performed to reduce the length of each block feature vector. The feature vectors of each cluster blocks are lexicographically sorted by radix sort. correlation between each nearby blocks indicates their similarity. The experimental results demonstrate that the proposed method can detect the duplicated regions efficiently, and reduce processing time up to 50% of other previous works
در این مقاله یک روش سریع و کارامد جهت تشخیص مناطق کپی-انتقال ارائه شده است. از روش خوشه بندی k-means استفاده می شود و در تطبیق بلاک دارای سرعت و قوی است.
منبع
مقاله ی کشف جعل کپی-انتقال به روش خوشه بندی
Abstract
. Due to rapid advancement of powerful image processing software, digital images are easy to manipulate and modify by ordinary people. Lots of digital image are edited for a specific purpose and more difficult to distinguish form their originality. We propose a clustering method to detect a copy-move image forgery of JPEG, BMP and TIFF. The process starts with reducing the color of the photos. Then we use the clustering technique to divide information of measuring data by Hausdorff Distance. The result shows that the purposed methods is capable of inspecting the image file and correctly identify the forgery
با توجه به پیشرفت سریع نرم افزار پردازش تصویر دستکاری تصاویر دیجیتال خیلی آسان شده است. در این مقاله روش خوشه بندی برای کشف جعل کپی-انتقال تصویر bmp، jpeg، TIFF پیشنهاد شده است. این فرآیند با کاهش رنگ از عکس شروع می شود.
منبع
تکنیک خوشه بندی
ما در جهانی پر از داده زندگی می کنیم و هر روز با حجم وسیعی از اطلاعات که باید آنها را ذخیره کنیم و یا نمایش دهیم روبرو هستیم. پردازش داده ها یکی از شاخصهای بسیار مهم در دنیای اطلاعات است.
خوشه بندی یکی از بهترین روش هایی است که برای کار با داده ها ارائه شده است. خوشه بندی قابلیت ورود به فضای داده و تشخیص ساختارش را امکان پذیر می نماید. لذا به عنوان یکی از ایده آل ترین مکانیزم ها برای کار با دنیای عظیم داده ها محسوب می شود.
اولین بار ایده ی خوشه بندی در دهه ی 1935 ارائه شد و امروزه با پیشرفت عظیمی که در آن پدید امده مورد توجه بسیاری از محققان قرار گرفته است.
با توجه به گسترش علوم مختلف، برخی از تکنیک های یک علم به دلیل توانایی در برطرف کردن نیازهای علوم مختلف، کاربرد وسیع و گسترده ای، پیدا کرد هاند. یکی از این تکنیک ها خوشه بندی ۱ است. خوشه بندی به دلیل توانایی و قابلی تهای بالایی که در تلخیص اطلاعات و دسته بندی آن ها دارد مورد توجه محققان و پژوهشگران علوم مختلف قرار گرفته است.
تکنیک خوشه بندی یکی دیگر از تکنیک ها در رابطه با کشف جعل کپی-انتقال است که این تکنیک هم دارای روش های مختلفی است. اما در ابتدا به مفهوم خوشه بندی می پردازیم.
خوشه بندی، فرآیند دسته بندی مجموعه ای از اشیاء به خوشه هایی است که اعضا درونی هر خوشه بیشترین شباهت را به یکدیگر و کمترین شباهت را نسبت به اعضا سایر خوشه ها داشته باشند. در هر خوشه داده هایی قرار می گیرند که به نظر می رسد شباهت بیشتری به یکدیگر دارند و داده هایی که به نظر می رسد شباهت کمتری نسبت به یکدیگر دارند در خوشه های مختلف قرار می گیرند.
خوشه بندی یافتن ساختاری در مجموعه ای از داده هاست که طبقه بندی نشده اند. دلیل اصلی استفاده از روش های خوشه بندی نیاز به کشف ساختارهای جدیدی است که به طور طبیعی در داده ها وجود دارد بدون اینکه هیچگونه اطلاعات قبلی از ساختار کلااسها وجود داشته باشد.
بنابراین تجزیه و تحلیل خوشه ای روشی برای برای گروه بندی داده ها یا مشاهدات با توجه به شباهت یا درجه نزدیکی آنهاست. تحلیل خوشه ای مشاهدات را به گونه ای در خوشه ها ترکیب می کند که :
- هر گروه یا خوشه با توجه به یک خصوصیت ویژه همگن است.
- هر گروه یا خوشه با توجه به همان خصوصیت با گروه هی دیگر متفاوت است.
آلدندرفر و بلشفید در سال 1984 اهداف به کارگیری خوشه بندی را به طور خلاصه اینگونه بیان کردند:
- توسعه و کشف رده های جدیدی در داده ها
- بررسی طرح ها با الگوهای مفهومی با استفاده از خوشه بندی
- تولید فرضیات در حین بررسی داده ها با استفاده از روش های خوشه بندی
- بررسی صحت فرضیات و گروه های ایجاد شده با استفاده از اطلاعات جانبی
خوشه بندی در علوم مهندسی، پزشکی، کامپیوتر، ستاره شناسی و زمین شناسی کاربرد دارد.
جهت تجزیه و تحلیل خوشه ها، اشیا با نقاطی در فضای N بعدی نمایش داده می شود که بردارها نشان دهنده ی خصیصه ی اشیا بوده و هدف مساله نیز دسته بندی N داده به K خوشه هست که اشیا هر خوشه بیشترین شباهت را به یکدیگر داشته باشند.
خوشه بندی هم مانند هر روشی دارای نقاط قوت و ضعف است:
-نقاط قوت:
- روش خوشه بندی یک روش غیرمستقیم است: بدین معنی که این روش را می توان حتی هنگامیکه هیچ نوع اطلاعاتی از ساختار داخلی پایگاه داده ها نداریم استفاده نمود.
- خوشه بندی را می توان برای داده های گوناگون استفاده نمود: با انتخاب درست اندازه فاصله های گوناگون خوشه بندی را می توان برای بیشتر انواع داده ها استفاده نمود.
- خوشه بندی مناسب امکان جستجوی ساده تر و دسترسی مناسب تری را برای استفاده از اطلاعات فراهم می کند.
-نقاط ضعف:
- انتخاب اندازه های دقیق فواصل و وزن ها کار اسانی نیست.
- این روش به پارامترهای اولیه نظیر تعدادخوشه ها، حداقل نزدیکی، خوشه های اولیه حساس است.
- تفسیر نتایج این روش می تواند مشکل باشد.
به طور کل برای همه ی روش های خوشه بندی دو گام اساسی وجود دارد:
گام اول: محاسبه میزان شباهت یا درجه نزدیکی
گام دوم: چگونگی ادغام داده ها بر اساس میزان شباهتشان
گام اول:
معیار شباهت در اینجا فاصله بوده یعنی هر قدر فاصله بین دو مشاهده کمتر باشد آن دو شبیه تر هستند و در یک خوشه قرار می گیرند.
توابع ریاضی مختلفی برای محاسبه فاصله وجود دارد مانند: فاصله اقلیدسی، فاصله بلوک شهری، فاصله همینگ، فاصله همبستگی ... .
گام دوم:
پس از اندازه گیری میزان شباهت باید شیوه ای برای پیوند داده هایی که بالاترین شباهت را نشان داده اند بکار برد. شیوه های مختلفی برای پیوند داده ها معرفی شده اند از جمله:
پیوند تکی، پیوند کامل، پیوند میانگین، پیوند میانگین وزنی، پیوند مرکز ثقل، پیوند میانه، پیوند وارد.
- پیوند تکی ( کمترین فاصله یا نزدیکترین همسایه):
فاصله بین دو خوشه= کمترین فاصله بین یک داده از یک خوشه با یک داده از خوشه ی دیگر
این پیوند در شکل زیر مشخص شده است:
- پیوند کامل ( بیشترین فاصله یا دورترین همسایه):
فاصله ی بین دو خوشه= بیشترین فاصله بین یک داده از یک خوشه با یک داده از خوشه ی دیگر
پیوند کامل در مقابل پیوند تکی کمتر در معرض اثر خطا قرار می گیرد.
این نوع پیوند در شکل زیر مشخص شده است:
خوشه بندی روش های مختلفی دارد اما روش های مورد بحث ما روش K-means و روش سلسله مراتبی است که در پستهای بعدی به توضیحات آن می پردازیم.
منبع
دانلود خوشه بندی و روش های آن
دانلود خوشه بندی K-means و سلسله در نرم افزارها
دانلود تحلیل خوشه بندی(ppt)