الگوريتم خوشه بندي سلسله مراتبي چند گانه

چكيده انگليسي :

MULTI HIERARCHICAL CLUSTERING ALGORITHM Elaheh Rashedi e rashedi@ec iut ac ir Date of Submission 2011 04 20 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Dr Abdolreza Mirzaei mirzaei@cc iut ac irAbstract Clustering algorithms are unsupervised learning methods which explore and group similar patternswithin a set of patterns The goal of the clustering methods is to partition the set of input patterns intoclusters such that all patterns within a cluster are similar to each other and different from the members ofother clusters In many applications clustering methods which lead to representations that are hierarchicalare more appropriate than flat representations The most natural representation of a hierarchical clustering isits corresponding tree which is called dendrogram which shows how the data points are grouped Generally hierarchical clustering is preferred in comparison with the nonhierarchical clustering forapplications when the exact number of the clusters is not determined or when we are interested in findingthe relation between clusters In supervised pattern recognition an effective method for solving complicatedproblems is to use decision combination The idea of ensemble learning is to combine multiple learners predictions In the area of supervised and unsupervised learning algorithms ensembles often create betterresults compared to single solutions Classifier ensemble methods combine classifiers to achieve aclassification solution of higher predictive accuracy Similarly clustering ensemble methods createclusterings of an improved quality by combination of clusterings The most recent powerful ensemblemethods are bagging and boosting Boosting is a general problem of machine learning which converts aweak learning algorithm into the one with higher accuracy There are many successful algorithms proposedin the area of multi classifier systems based on boosting and also there are some positive outcome multiclustering algorithms based on bagging and boosting which are introduced on the flat clusterings Accordingly there is a potential for greater gains in hierarchical cluster quality improvement when usingensembles In this thesis we introduce two different multiple topology frameworks in which ensemblehierarchical clusterings are constructed and then combined In these frameworks first a description matrixis created for each hierarchy and then the description matrices of the input hierarchies are aggregated toform a consensus matrix from which the final hierarchy is derived In the first framework a weightedaverage combination method is used to aggregate the hierarchical clusterings in which the weights areinitiated based on genetic algorithm Experimental analysis shows that the proposed method createsclusterings of better quality than traditional hierarchical clustering algorithms In the second framework weintroduce a new hierarchical cluster ensemble method based on boosting theory which is used to obtainimprovement in terms of cluster accuracy The proposed algorithm includes a boosting iteration in which atraining set is created by weighted random sampling of elements from the original dataset and ahierarchical clustering is created on selected subsamples The final consensus hierarchical clustering iscreated by combining the individual clusterings of the ensemble built during each iteration Combination isdone by an aggregation of distance description matrices of hierarchical clustering results Experiments onreal popular datasets confirm that the boosted multi hierarchical clustering method provides superiorquality and more stable solutions compared to standard hierarchical clustering methods Keywords Ensemble clustering hierarchical clustering description matrix combination boosting theory

راشدي، الهه

الگوريتم خوشه بندي سلسله مراتبي چند گانه

تركيب ماتريس هاي توصيف , نظريه تقويت