پديد آورنده :
بيگي‌بروجني، ميلاد
عنوان :
توسعه و تركيب روش‌هاي خوشه‌بندي دادهها بر مبناي نظريه گراف و كم‌ترين درخت‌هاي پوشاي فراگير
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
بهينه‌سازي سيستم‌ها
محل تحصيل :
اصفهان : دانشگاه صنعتي اصفهان
صفحه شمار :
[ده]، 70ص.: مصور، جدول، نمودار
استاد راهنما :
علي‌زينل همداني، مهدي خاشعي
توصيفگر ها :
داده‌كاوي , گراف‌كاوي , خوشه‌بندي , گراف وزندار , كم ترين درخت پوشاي فراگير , نزديك‌ترين همسايگي‌ها , ادغام خوشهها
استاد داور :
غلامعلي رئيسي اردلي، مهدي علينقيان
تاريخ ورود اطلاعات :
1398/06/06
رشته تحصيلي :
مهندسي صنايع و برنامه ريزي سيستم
دانشكده :
مهندسي صنايع و سيستم ها
تاريخ ويرايش اطلاعات :
1398/06/06
چكيده فارسي :
1 چكيده در عصر کنونی نقش اطالعات در کاهش عدم قطعیت در فرآیند تصمیمگیری بسیار مهم جلوه مینماید دانشیابی و کسب اطالعات از دادهها موجب تصمیمگیری بهتر و منطقیتر میگردد از اینرو دانش نوینی در استخراج الگوهای معنادار از دادههای خام توسعه داده شدهاست دادهکاوی علمی است که از روشها و الگوریتمهای جدید جهت استخراج اطالعات از دادههای خام استفاده مینماید یکی از روشهای جذاب و محبوب در حوزهی دادهکاوی خوشهبندی است خوشهبندی تالش میکند دادهها را با توجه به ماهیتشان به گروههایی تقسیمبندی نماید بهطوری که دادههای درون هر گروه بیشترین شباهت را به یکدیگر داشته و همچنین بیشترین تمایز مابین گروههای مختلف وجود داشته باشد امروزه در میان الگوریتمهای خوشهبندی الگوریتمهای خوشهبندی مبتنی بر گراف در مرکز توجه محققین قرار گرفته است دقت و سرعت پردازش دادهها و تشخیص خوشهها دو فاکتور اساسی جهت ارزیابی اینگونه الگوریتمها بهشمار میآید با توجه به حجم دادهها روشهای خوشهبندی عموما از سرعت مناسب و دقت کافی جهت تشخیص خوشهها برخوردار نمیباشند همچنین این الگوریتمها در مجموعه دادههایی که به صورت نرمال در فضا پراکنده نشده باشند نتایج بهینهای را ارائه نمیدهند در این پژوهش بهمنظور افزایش دقت و سرعت الگوریتم خوشهبندی مبتنی بر روشهای خوشهبندی بر روی گرافهای وزندار توسعه داده شدهاست الگوریتم توسعه دادهشده از تئوری ریاضیاتی استخراج درخت پوشای فراگیر استفاده مینماید تشکیل درختهای پوشای فراگیر همواره بر مبنای حداقل نمودن وزن درخت بهدستآمده انجام میپذیرد همچنین هدف الگوریتمهای خوشهبندی بر مبنای فاصله تشکیل خوشهها با حداقل مجموع فواصل درون خوشهای میباشد به همین رو الگوریتم پیشنهادی در این پژوهش از تئوری استخراج کمترین درخت پوشای فراگیر به منظور خوشهبندی دادهها بهره میبرد در کلیهی الگوریتمهایی که تاکنون در زمینهی خوشهبندی برروی کمترین درختهای پوشای فراگیر انجام پذیرفتهاند ابتدا درخت پوشای فراگیر استخراج گردیده و سپس خوشهبندی بر روی درخت مذکورانجام میگردد این در حالیاست که در الگوریتم پیشنهادی جهت تسریع در سرعت پردازش فرایند خوشهبندی همزمان با تشکیل درخت پوشای فراگیر انجام میپذیرد یکی از مزایای روشهای خوشهبندی مبتنی بر کمترین درخت پوشای فراگیر استخراج خوشهها با تراکم متفاوت است به همین جهت الگوریتم پیشنهادیی عالوهبر توانایی در شناسایی خوشهها با تراکم متفاوت از زمان پردازشی کمتری نیز برخوردار میباشد در این پژوهش بهمنظور ارزیابی الگوریتم پیشنهادی از دادههای مرجع استفاده میگردد همچنین از معیارهای F Jaccard Measure و Rand نیز جهت تحلیل و ارزیابی نتایج الگوریتم بهره برده میشود نتایج ارزیابی نشان میدهد که الگوریتم ارائهشده با توجه به معیارهای ارزیابی نسبت به سایر روشهای خوشهبندی مبتنی بر کمترین درختهای پوشای فراگیر و همچنین روشهای خوشهبندی شناختهشده از عملکرد بهتری برخوردار میباشد كلمات كليدي دادهکاوی گرافکاوی خوشهبندی گراف وزندار کمترین درخت پوشای فراگیر نزدیکترین همسایگیها ادغام خوشهها
چكيده انگليسي :
71 Developing and combining data clustering methods based on graph theory and Minimal Spanning Trees MST Milad Beige Borujeni May 2019 Department of Industrial and Planning Systems Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Persian Supervisor Prof Ali Zeinal Hamadani Supervisor Prof Mehdi Khashei Abstract In the present era the role of information is extremely important in reducing uncertainty in thedecision making process Recognizing and obtaining information from the data will make decisionmaking easier and more logical Hence new knowledge has been developed in extracting meaningfulpatterns of raw data Data mining is a field uses new methods and algorithms to extract informationfrom raw data One of the most attractive and popular methods in the field of data mining isclustering Clustering attempts to divide the data according to its nature into similar groups so thatthe data within each group are most similar to each other as well as the most distinction betweendifferent groups Today among clustering algorithms graph based clustering algorithms are at thecenter of attention of researchers The accuracy and speed of data processing and the identificationof clusters are two basic factors for evaluating such algorithms Due to the volume of data clusteringmethods generally do not have the proper speed and accuracy to detect clusters So these algorithmsdo not provide optimal results in datasets that are not normally distributed in space In this research clustering algorithm based on weighted graphs clustering methods has beendeveloped in order to increase accuracy and speed The developed algorithm uses the mathematicaltheory of Minimal Spanning Trees MST The formation of MST is based on minimizing the weightof the obtained tree Also the goal of clustering algorithms based on distance is to form clusters witha minimum of total intra cluster intervals Therefore the proposed algorithm in this study uses thetheory of extraction of the MST for data clustering In all the algorithms that have been done so farin clustering on the least common spanning trees first a spanning tree is extracted and thenclustering is done on the tree This is due to the fact that in the proposed algorithm to accelerate theprocessing speed the clustering process is performed simultaneously with the formation of aspanning tree One of the advantages of clustering methods based on the least spatial spanning treeis the extraction of clusters with different densities Therefore the proposed algorithm has lessprocessing time than the ability to identify clusters with different densities In this research the benchmark data is used to evaluate the proposed algorithm Also Jaccard F Measure and Rand measures are used to analyze and evaluate the results of the algorithm Theevaluation results show that the proposed algorithm has better performance than other clusteringmethods based on the MST as well as known clustering methods according to the evaluationmeasures Key Words Data mining Graph mining Clustering Weighted graph Minimal spanning tree Nearest neighbors Cluster merging
استاد راهنما :
علي‌زينل همداني، مهدي خاشعي
استاد داور :
غلامعلي رئيسي اردلي، مهدي علينقيان
