基于K-means算法寝室分配问题

谢靖萱，徐宏达，秦溧，张晓霞

（辽宁科技大学计算机与软件工程学院，鞍山114051）

1 问题的提出

近些年来，随着大学生的数量逐渐增加，寝室的问题也逐渐增加，严重的甚至引发寝室杀人案。大学生在校生活花费最多时间的就是寝室，寝室生活会影响一名学生的未来发展以及三观的发展。有国外学者基于美国以及加拿大大学生的寝室调研数据证实，积极的文明寝室氛围对大学生精神面貌、学风学纪等多方面存在正向的推进作用[1]。为了避免寝室发生意外事故，也为了让当代大学生的思想、生活教育更为良好。研究基于K-means算法的寝室分配问题变得十分必要。

2 相关研究

和谐温馨的寝室环境益于大学生的成长和学习，近些年寝室关系的问题也成为了热点话题。寝室分配方案的不断探索与改进，集合不同的算法与方案。以便能设计出一种真正解决寝室矛盾问题并且能对大学生生活和学习有益的方案。以下是近几年对于寝室分配方案的一些研究：

2015年梁媛园提出并按照一定条件对寝室进行分配。针对调查结果，在制定新生寝室分配方案时，在2015年第二临床医学院本科新生入学宿舍分配中，除优先考虑需要照顾的有特殊情况的学生外，将作息规律作为重要参考条件之一，同时保证各地域生源学生混住，促进学生的交流，避免由于地域问题难以融入大学生活而被“边缘化”[2]。

顾洲一在2019年基于数据思维提出了新的寝室分配方式。借助人工智能技术优化学生寝室结构，形成科学客观的寝室分配系统[3]，此思维的提出对寝室全新分配方案作用不可小觑。应该从事情的源头上来解决寝室矛盾问题。这也可以证实借助智能化和算法来分配寝室是具有一定先进性和实用性的。

亓文杰在2019年提出同质化的分配寝室，即学生被大学录取后，就可以通过调研问卷了解学生来源地、日常爱好、性格基本特征[4]，来通过调查结果对寝室分配。这也是我们计划使用K-means算法分配前的必须步骤，相比于人力分配通过相关算法更加精准和高效。

杨蕙源在2020年谈到南京大学的寝室分配方案问题。他们用大数据来对学生宿舍进行分配，南大采用“隐语义模型”算法量化评估新生之间的兴趣爱好相似度[5]。这种对调查问卷的细化方法及大数据也是现代寝室分配的前沿。“隐语义模型”可以简单概括为通过一些简单的问题可以大致对学生的性格和习惯进行一些区分和聚类。

随着时代的不断发展，当代青年学生的性格差异也越来越大。和谐的寝室生活对学生的生活、学习和心理都有有益的影响。所以，通过问卷调查结果来分配寝室对寝室文化来说显得格外重要。

K-means是最典型的划分式聚类算法之一，适合对大型数据集进行分析，运算效率高是其显著优点[6]。选择K-means算法来计算调查问卷的结果和附加的权值是当下较为合适的一种方法，也能较为精准地分配一个合理的寝室。一个合理分配的宿舍会让大学生的心灵更加健康，有更好的学习氛围。相信通过Kmeans算法与调查问卷相结合的方式分配的寝室会令更多人所满意的。

3 K-means算法的应用

选取W={w1，w2，…，wn}为我们的待分配人员的节点集合，相似度则用以下公式来计算：

根据公式（1），我们的待分配寝室人员x问卷答案的集合为Xx，待分配寝室人员y问卷答案的集合为Xy，x与y待分配寝室人员答案结果相同的为Rx,y。以此类推便可以算出我们想要的分配寝室的数据。

根据节点相似度计算公式，推导出用户x节点的加权度界定表达式与加权聚集度定义式，分别如下所示[7]：

这种加权的方式也是为了能更加准确地分出和谐的寝室，我们将把调查问卷中不同的问题赋予不同的权值。有些重要的问题权值就相对更高一些，有些没那么重要的问题，我们设置的权值也会相对的调低一些。所以加权来对问卷分析这一点也是我们选取K-means算法中重要的一点。因此也解决了一些关于问卷的问题。

（1）从若干元素中以随机的方式选择k个元素，以这k个元素作为k个簇的中心。

（2）单个计算除k外所有元素到k个簇的中心的距离，将每个元素都找到相距最近的中心，并划分到该簇。

（3）根据以上所得结果，再次计算k个簇的中心，以每簇的平均值作为每簇的中心。

（4）按照新的中心以（2）为方法重新计算。

（5）一直重复（4）过程，直到数据不再变化。

我们将学生的数量定义为若干元素，当然学生数量不会是一个巨大的数值，因为考虑到性别、专业甚至是班级的因素。这样在算法运行时会更容易找到每个簇的中心，也就是我们认为的寝室中心。我们会在这些的基础上在进行K-means聚类分析算法来实现我们的想法。其中的k就是我们最后要得到的划分出的寝室的数量。通过不断地重复步骤（4）直到数据不再变化，就可以得到最终我们想要的寝室数据。

关于加权问题，每个学生所最在意的条件我们将把该项的权值升高，例如大部分人会在意室友的休息时间及睡眠质量，我们就可以把这一项赋值为5。如果是不太重要的问题，我们将会赋值为1。既然能在调查问卷上体现出的问题也都是相对比较重要的。这样加上权值的一个分配更有助于寝室分配的合理性与实用性。

4 K-means实验结果及分析

此时我们不妨以生活习惯和性格为主要参考依据，对学生寝室进行划分，性格孤僻赋值为1，活泼赋值为2，随和赋值为5，生活习惯中喜欢熬夜赋值为3，不喜欢熬夜赋值为4，有洁癖赋值为6，没有洁癖赋值为7。这里假设有10个同学，需要分到两个寝室。这四个同学的生活习惯以及性格如表1所示。

表1 实验样例数据表

第一次划分：假定随机选择两个对象，如序号1和序号2作为划分点，我们通过计算每个点到最近对象的欧氏距离，并产生了两个簇{1，3，5，7，10}，{2，4，6，8，9}。对于簇{1，3，5，7，10}平均值点为（2.8，3.4，6），对于簇{2，4，6，8，9}平均值点为（2.4，3.6，7）。

第二次划分：通过计算出的两个平均值点重新调整对象所在的簇，并重新划分，即将所有的点按照离（2.8，3.4，6），（2.4，3.6，7）最近的原则重新分配。得到两个新的簇{1，3，5，7，10}，{2，4，6，8，9}。发现并未重新分配，则说明结果已经收敛，实验结果如表2所示。

表2 实验结果表

按照此种方式进行的划分，即让有洁癖同时晚上喜欢熬夜的同学尽可能分到一个寝室；没洁癖晚上不喜欢熬夜的同学可能分到一个寝室；同时也让性格开朗、孤僻和随和的同学混合分配。这样划分会更加有利于寝室氛围和谐和学生的成长。

5 K-means与其他聚类算法的比较

K-means算法是聚类分析方法中的一种，选用K-means算法是因为它能在大规模的数据中进行聚类是能较为精准且高效地对数据进行分类，并且算法对数值型数据的聚类效果好，聚类结果也与数据的输入顺序无关。这样的一个前提条件更有益于做精准的寝室分配，让结果与预期偏差不会太大。K-means算法不但使用起来高效而且可伸缩，而且这种算法通俗易懂，使用起来也比较简便。这种算法也更加适用于日常生活中。下面是一些其他聚类算法与K-means算法的比较：

（1）拿系统聚类方法来作为对比的话，在寝室分配方案中选择系统聚类的方法的情况下，我们的调查问卷内容将变得单一，但没有任何单一的问题就可以解决寝室分配的难题。而且也很难将我们需要的问卷中所有数据整合在一起来进行分类。相对于系统聚类方案来比较，K-means算法是能在寝室分配问题上起到更好的解决作用的算法。

（2）K-median是一个与K-means较为相似的一种算法。虽然说在某种程度上K-median在K-means算法的基础上有提高点，但是它是使用簇的中值向量来重新计算质点对异常值不敏感。而在我们的分配方案中，是需要考虑到异常值得处理的，而且异常值也作为这个项目的重要点，例如有的人有一些比较特殊的习惯，虽然大部分人没有但这一点对于很多人而言都是至关重要的一点，这种情况将难以处理。所以在这个项目中选择K-means算法更优于K-median算法

（3）DBSCAN算法也是大家所熟悉且经常被选择的一种聚类分析算法。这种算法虽然有很多的优点，但也正因为它能过滤掉不合适的点，但对于我们的需求来说，我们不能随意去排除任何一个需要获得寝室的学生名单。所以假使我们用这种方式来进行一个固定人数分配的寝室是难为实现的。因此在对比中，我们选择K-means算法。

（4）GMM算法，虽然GMM可以容纳一些“混合”成员，但可能陷入局部极值的情况，它的运算需要进行多次迭代。基于时间和正常运行规律的考虑。在GMM与K-means算法的比较重，该寝室分配方案也更倾向与K-means算法。

基于运算简单、结果精确、不大材小用的原则，我们也认为K-means算法是在聚类分析算法中较为适用于寝室分配方案的一种算法，它既可以准确地分出我们想要的寝室结果，又能提高分出寝室的速率，无论从哪个角度看选择它都是无疑的。

6 结语

现有的高校寝室分配方案大多基于随机分配的方式或者说单单基于成绩、家乡这样的方式来确定一个最终的寝室人员构成。这种方式虽然简洁且可以快速分配，但经过若干年的实践来看，它并不能达到一个积极的效果。很多宿舍也因为性格和生活习惯等问题发生了许多的事故。因此能够参照性格和生活习惯来对寝室进行一个合理的分配也是对学习和生活有一个积极的影响的。那么对于这样一个有条件要求的聚类分配，K-means算法是几种相关算法中比较突出有用的方法。通过K-means算法与隐语义模型的调查问卷相结合的方式来进行寝室分配无疑是一个避免寝室矛盾使寝室文化更加积极阳光的好办法。