Signal and Data Processing

fa ترکیب وزن‌دار خوشه‌بندی‌ها با هدف افزایش صحّت خوشه‌بندی نهایی Weighted Ensemble Clustering for Increasing the Accuracy of the Final Clustering مقالات پردازش داده‌های رقمی Paper پژوهشي Research <div style="text-align: justify;">با توجه به ماهیت بدون ناظر مسائل خوشه‌بندی و تأثیرگذاری مؤلفه‌های مختلف از جمله تعداد خوشه‌ها، معیار فاصله و الگوریتم انتخابی، ترکیب خوشه‌بندی‌ها برای کاهش تأثیر این مؤلفه‌ها و افزایش صحت خوشه‌بندی نهایی معرفی شده است. در این مقاله، روشی برای ترکیب وزن‌دار خوشه‌بندی‌های پایه با وزن‌دهی به خوشه‌بندی‌ها بر اساس روش AD ارائه شده است. روش AD برای برآورد صحّت انسان‌ها در مسائل جمعسپاری از هماهنگی یا تضاد بین آرای آنها استفاده می‌کند و با پیشنهاد مدلی احتمالاتی، فرآیند برآورد صحّت را به‌کمک یک فرآیند بهینه‌سازی انجام می‌دهد. نوآوری اصلی این مقاله، تخمین صحت خوشه‌بندی‌های پایه با استفاده از روش AD و استفاده از صحت‌های تخمین زده‌شده در وزن‌دهی به خوشه‌بندی‌های پایه در فرآیند ترکیب است. نحوه تطبیق مسأله خوشه‌بندی به روش برآورد صحّت AD و نحوه استفاده از صحّت‌های برآورد‌شده در فرآیند ترکیب نهایی خوشه‌ها، از چالش‌هایی است که در این پژوهش به آنها پرداخته شده است. چهار روش برای تولید خوشه‌بندی‌های پایه شامل الگوریتم‌های متفاوت، معیارهای فاصله‌ی متفاوت در اجرای k-means، ویژگی‌های توزیع‌شده و تعداد خوشه‌های متفاوت بررسی شده است. در فرآیند ترکیب، قابلیت وزن‌‌دهی به الگوریتم‌های خوشه‌بندی ترکیبی CSPA و HGPA اضافه شده است. نتایج روش پیشنهادی روی سیزده مجموعه داده مصنوعی و واقعی مختلف و بر اساس نُه معیار ارزیابی متفاوت نشان می‌دهد که روش ترکیب وزن‌دار ارائه‌شده در بیش‌تر موارد بهتر از روش ترکیب خوشه‌بندی بدون وزن عمل می‌کند که این بهبود برای روش HGPA نسبت به CSPA بیشتر است.</div> <div style="text-align: justify;">Clustering algorithms are highly dependent on different factors such as the number of clusters, the specific clustering algorithm, and the used distance measure. Inspired from ensemble classification, one approach to reduce the effect of these factors on the final clustering is ensemble clustering. Since weighting the base classifiers has been a successful idea in ensemble classification, in this paper we propose a method to use weighting in the ensemble clustering problem. The accuracies of base clusterings are estimated using an algorithm from crowdsourcing literature called agreement/disagreement method (AD). This method exploits the agreements or disagreements between different labelers for estimating their accuracies. It assumes different labelers have labeled a set of samples, so each two persons have an agreement ratio in their labeled samples. Under some independence assumptions, there is a closed-form formula for the agreement ratio between two labelers based on their accuracies. The AD method estimates the labelers’ accuracies by minimizing the difference between the parametric agreement ratio from the closed-form formula and the agreement ratio from the labels provided by labelers. To adapt the AD method to the clustering problem, an agreement between two clusterings are defined as having the same opinion about a pair of samples. This agreement can be as either being in the same cluster or being in different clusters. In other words, if two clusterings agree that two samples should be in the same or different clusters, this is considered as an agreement. Then, an optimization problem is solved to obtain the base clusterings’ accuracies such that the difference between their available agreement ratios and the expected agreements based on their accuracies is minimized. To generate the base clusterings, we use four different settings including different clustering algorithms, different distance measures, distributed features, and different number of clusters. The used clustering algorithms are mean shift, k-means, mini-batch k-means, affinity propagation, DBSCAN, spectral, BIRCH, and agglomerative clustering with average and ward metrics. For distance measures, we use correlation, city block, cosine, and Euclidean measures. In distributed features setting, the k-means algorithm is performed for 40%, 50%,…, and 100% of randomly selected features. Finally, for different number of clusters, we run the k-means algorithm by k equals to 2 and also 50%, 75%, 100%, 150%, and 200% of true number of clusters. We add the estimated weights by the AD algorithm to two famous ensemble clustering methods, i.e., Cluster-based Similarity Partitioning Algorithm (CSPA) and Hyper Graph Partitioning Algorithm (HGPA). In CSPA, the similarity matrix is computed by taking a weighted average of the opinions of different clusterings. In HGPA, we propose to weight the hyperedges by different values such as the estimated clustering accuracies, size of clusters, and the silhouette of clusterings. The experiments are performed on 13 real and artificial datasets. The reported evaluation measures include adjusted rand index, Fowlkes-Mallows, mutual index, adjusted mutual index, normalized mutual index, homogeneity, completeness, v-measure, and purity. The results show that in the majority of cases, the proposed weighted-based method outperforms the unweighted ensemble clustering. In addition, the weighting is more effective in improving the HGPA algorithm than CSPA. For different weighting methods proposed for HGPA algorithm, the best average results are obtained when we use the accuracies estimated by the AD method to weight the hyperedges, and the worst results are obtained when using the normalized silhouette measure for weighting. Finally, among different methods for generating base clusterings, the best results in weighted HGPA are obtained when we use different clustering algorithms to come up with different base clusterings.</div> خوشه‌بندی ترکیبی وزندار, یادگیری بدون نظارت, HGPA, CSPA, AD Weighted Ensemble Clustering, Unsupervised Learning, HGPA, CSPA, AD 100 85 http://jsdp.rcisp.ac.ir/browse.php?a_code=A-10-1443-1&slc_lang=fa&sid=1 Sedigheh Vahidi Ferdosi صدیقه وحیدی فردوسی s.vahidi@stu.qom.ac.ir 10031947532846009101 10031947532846009101 No University of Qom دانشگاه قم Hossein Amirkhani حسین امیرخانی amirkhani@qom.ac.ir 10031947532846009102 10031947532846009102 Yes University of Qom دانشگاه قم