一种基于改进型Chameleon算法的宿舍分配方法

A dormitory allocation method based on improved Chameleon algorithm

本文基于Chameleon算法对高维度R型问题进行聚类分析,提出加权共享-变色龙算法(KSNN-Chameleon)用于改进学生宿舍分配问题。KSNN-Chameleon算法首先将学生的宿舍集通过K近邻算法稀疏化,然后采用近邻加权方式处理已稀疏化的数据集得到加权近邻图;接着对加权近邻图通过洪水覆盖法(flood-fill)和点间共享近邻相似度(SNN)进行图划分;最后KSNN-Chameleon算法采用第一截断法来快速确认数据集的分簇是否符合要求,反复划分与合并获得最终的聚类结果。实验结果证明,KSNN-Chameleon算法不仅在面对R型高维度聚类问题时仍能保证较好的稳定性与精度,且与传统Chameleon算法相比,KSNN-Chameleon的聚类精度提升了20.88%,聚类时间提升了2.73%。

In order to solve the intelligent assignment problem of the student dormitory,the paper proposes the K-Shared Nearest Neighbour-Chameleon algorithm(KSNN-Chameleon)based on the traditional Chameleon algorithm for clustering analysis of high-dimensional R-type problems.The KSNN-Chameleon algorithm first processes sparsely the obtained student dormitory set by the K-nearest neighbor algorithm,and then the weighted nearest neighbor graph is obtained by processing the sparsed data set using nearest neighbor weighting;the weighted nearest neighbor graph is later divided into graphs by flood-fill method and the data are merged using the shared nearest neighbor(SNN)similarity method;finally,the KSNN-Chameleon algorithm uses the first truncation method to quickly confirm the subclustering of the dataset,and the final clustering results are obtained by iterative division and merging.The experimental results demonstrate that the KSNN-Chameleon algorithm not only ensures better stability and accuracy when facing the R-type high-dimensional clustering problem,but also improves the clustering accuracy of KSNN-Chameleon by 20.88%and the clustering time by 2.73%compared with the traditional Chameleon algorithm.