دانلود پایان نامه ارشد درمورد سلسله مراتبی و سلسله مراتب

الگوریتم‌های سلسله مراتبی با استفاده از گروه‌هایی که قبلا تشکیل شده‌اند گروه‌های جدیدی را پیدا می‌کنند. این الگوریتم‌ها غالبا یا تراکمی (از بالا به پایین) هستند، یا انشعابی (از پایین به بالا). الگوریتم‌های تراکمی با هر عنصر که به عنوان یک خوشه‌ی مجزا درنظر گرفته شده است شروع می‌شوند و آنها را به گروه‌های بزرگتر تبدیل می‌کنند[21] . الگوریتم‌های انشعابی با تمامی سری داده شروع می‌شوند و با تقسیم کردن آنها به گروه‌ها یا خوشه‌های کوچکتر ادامه می یابند (شکل 2-1 را ببینید). الگوریتم‌های تفکیکی معمولا تمامی خوشه‌ها را به صورت یکباره تعیین می‌کنند اما می‌توانند بعنوان الگوریتم‌های انشعابی در خوشه‌بندی سلسله‌ای نیز بکار روند. الگوریتم‌های خوشه‌بندی چگالی مبنا، به منظور کشف گروه‌هایی با شکل دلخواه ابداع شده‌اند. در این رویکرد یک خوشه بصورت منطقه‌ای درنظر گرفته می‌شود که چگالی یا تراکم اشیاء در آن از حد آستانه بیشتر باشد. الگوریتم‌های خوشه‌ای فضایی ، به دنبال خوشه‌هایی می‌گردند که فقط بتوان انها را دریک تجسم خاص از داده‌ها (خمیده، بخشی از فضا) مشاهده کرد[22] .
شکل2-1) طرحی ساده از خوشه بندی سلسله‌ای
2-1-1-3) اندازه‌گیری فاصله
یکی از مراحل خوشه‌بندی انتخاب مقیاس اندازه‌گیری فاصله ‌است که نحوه‌ی محاسبه‌ی میزان شباهت دوعنصر را تعیین می‌کند. این انتخاب می تواند بر شکل خوشه‌ها تاثیرگذار باشد بنابراین یک عنصر می تواند براساس نوع فاصله‌ی انتخابی مربوط به یک خوشه‌ی خاص باشد که با تغییر نوع فاصله، این عنصر به خوشه‌ی دیگری تعلق گیرد. توابع فاصله‌ای که متداولترند شامل موارد زیر می شوند: فاصله اقلیدسی، فاصله‌ی منهتن، فاصله ماهالانوبیس، زاویه‌ی بین دو بردار نیز می‌تواند به عنوان مقیاس فاصله در نظر گرفته شود[23] . مورد دیگری که در خوشه‌بندی از اهمیت بالایی برخوردار است این است که آیا از فواصل متقارن استفاه می‌شود یا فواصل نامتقارن. بسیاری از توابع فاصله که در بالا به آنها اشاره شد دارای خصوصیت متقارن بودن فواصل‌اند. این تقارن به این معنی است که فاصله‌ی شیء A از B دقیقا با فاصله‌ی شیء B از A یکسان است. درعین حال باید دقت شود که یک مقیاس مناسب، اندازه‌های متقارن ارائه می‌دهد.
2-1-1-4) دسته‌بندی تفکیکی
انواع زیادی از این نوع دسته‌بندی وجود دارد که در ادامه به تعدادی از آنها اشاره شده است.
2-1-1-4-2) دسته بندی مبهم C- میانگین
(2-1)
دردسته بندی مبهم یا نامشخص[22] ، هرنقطه به جای اینکه کاملا به یک دسته‌ی مشخص نسبت داده شود بادرجه‌ای از میزان تعلق به یک دسته تعیین می‌گردد. بناباین نقاط روی مرز یک دسته می‌توانند متعلق به آن دسته در نظر گرفته شوند اما با درجه‌ی تعلق کمتری نسبت به نقاط مرکزی دسته. برای هرنقطه‌ی x ضریبی تعریف می‌شود که میزان تعلق آن نقطه رابه دسته‌ی K‌ ام نشان می‌دهد . معمولا مجموع ضرایب برای هر نقطه‌ای یک تعریف می شود. مرکز یک دسته، مرکز تمامی نقاطی است که میزان تعلق آنها به دسته در فرمول زیر در نظر گرفته می‌شود:
x= نقطه
k= دسته
m= پارامتر واقعی
(2-2)
درجه‌ی تعلق با معکوس فاصله تا مرکز دسته ارتباط دارد:
d= فاصله
‌سپس ضرایب نرمال شده با یک پارامتر واقعی m >1 به نحوی که مجموع آنها یک شود، مبهم سازی می‌گردند.
(2-3)
برای 2= m به راحتی می توان به نحوی نرمال سازی راانجام داد که مجموع مقادیر آنها به صورت خطی یک شود. این الگوریتم با الگوریتم k- میانگین بسیار مشابهت دارد.
2-1-1-4-3) الگوریتم دسته‌بندی QT
دسته بندی QT (آستانه کیفیت)[21] روش جایگزین برای تفکیک داده‌ها در دسته بندی‌های ژنی است. این الگوریتم درمقایسه با الگوریتم K- میانگین به نیروی محاسباتی بیشتری نیازمند است، اما به تعیین تعداد دسته‌ها پیش از اجرای الگوریتم نیاز ندارد وهمیشه نتایج یکسانی را پس از هر مرتبه اجرا بدست می‌دهد. در این روش فاصله‌ی بین یک نقطه ویک گروه از نقاط با استفاده از روش اتصال کامل (در نظر گرفتن بیشترین فاصله از نقطه‌ی مورد نظر تا هر نقطه از اعضای گروه )‌ محاسبه می شود.
2-1-1-4-1) خوشه بندی K- میانگین
این نوشته در علمی ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.