عنوان پایان‌نامه
یادگیری برای رده بندی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 66..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 65213
- تاریخ دفاع
- ۱۲ شهریور ۱۳۹۳
- دانشجو
- مهیار پاسارزنگنه
- استاد راهنما
- علی معینی
- چکیده
- مسئله ی توزیع کالا یا منابع بین مقاصد مختلف یکی از مهمترین مسائل علم روز علوم مهندسی می باشد. یکی از روش های سنتی حل مسئله ی توزیع خوشه بندی است. در این روش به منظور توزیع بهتر مراکزی تعریف می شوند و توزیع از آن مراکز صورت می پذیرد. یکی از الگوریتم های معروف خوشه بندی K-means می باشد. در این الگوریتم n عنصر در k خوشه تقسیم می شوند به طوری که عناصری که به یک مرکز نزدیک تر هستند در یک خوشه قرار می گیرند. از مشکلات الگوریتم خوشه بندی K-means می توان به خوشه های با تعداد اعضای بسیار زیاد یا بسیار کم یا حتی خالی اشاره کرد. نیاز به توزیع متعادل در مسائل توزیع کالا یا منابع باعث می شود به الگوریتمی نیاز داشته باشیم که عملیات خوشه بندی را از لحاظ تعداد عناصر در هر خوشه متعادل کند. در این پایان نامه روشی ارائه کرده ایم که این عملیات متعادل سازی را با تغییراتی در الگوریتم K-means ارائه می دهد. این الگوریتم که آنرا Balanced K-means نام گذاری کرده ایم قادر است که با دریافت تعداد حداکثر نود در هر خوشه، تضمین کند که بیش از تعداد خاصی نود در هر خوشه قرار نگیرد. از طرفی دیگر تلاش برای ممانعت از بیشتر شدن تعداد نود ها در یک خوشه از یک مقدارِ حداکثر باعث می شود که خوشه ها در وضعیت متعادلی از لحاظ تعداد نود قرار بگیرند. از دیگر کاربرد های این الگوریتم می توان به بهینه سازی مصرف انرژی در شبکه های سنسوری و تقسیم متعادل کار ها بین چند پردازنده اشاره کرد.
- Abstract
- Goods or resources distribution among different targets is one of most important problems of Engineering. One traditional way to solve this problem is clustering. In clustering many centroids defined in order to distribute more efficiently. K-means is one solution to clustering problem. In K-means n data elements divided into k cluster so that elements that has shorter distance to centroids get into same cluster, but K-means has problems so that some clusters can have many elements but some may has little or zero at the same time. The need to balance cluster sizes for better distribution leads to this need that there should be a Balancing Algorithm that can do clustering more balanced. In this thesis we introduced a novel algorithm named Balanced K-means that can get Maximum Load of a cluster as input and ensure that no cluster has elements more than this limit, in other way the effort to keep nodes number in each cluster under the limit it can lead to keep all clusters more balanced by size. This solution can also be used in Sensor Networks power usage problem and divide jobs between many processors alongside distribution problem.
