基于K-means算法寢室分配問題

謝靖萱，徐宏達，秦溧，張曉霞

（遼寧科技大學(xué)計算機與軟件工程學(xué)院，鞍山114051）

1 問題的提出

近些年來，隨著大學(xué)生的數(shù)量逐漸增加，寢室的問題也逐漸增加，嚴(yán)重的甚至引發(fā)寢室殺人案。大學(xué)生在校生活花費最多時間的就是寢室，寢室生活會影響一名學(xué)生的未來發(fā)展以及三觀的發(fā)展。有國外學(xué)者基于美國以及加拿大大學(xué)生的寢室調(diào)研數(shù)據(jù)證實，積極的文明寢室氛圍對大學(xué)生精神面貌、學(xué)風(fēng)學(xué)紀(jì)等多方面存在正向的推進作用[1]。為了避免寢室發(fā)生意外事故，也為了讓當(dāng)代大學(xué)生的思想、生活教育更為良好。研究基于K-means算法的寢室分配問題變得十分必要。

2 相關(guān)研究

和諧溫馨的寢室環(huán)境益于大學(xué)生的成長和學(xué)習(xí)，近些年寢室關(guān)系的問題也成為了熱點話題。寢室分配方案的不斷探索與改進，集合不同的算法與方案。以便能設(shè)計出一種真正解決寢室矛盾問題并且能對大學(xué)生生活和學(xué)習(xí)有益的方案。以下是近幾年對于寢室分配方案的一些研究：

2015年梁媛園提出并按照一定條件對寢室進行分配。針對調(diào)查結(jié)果，在制定新生寢室分配方案時，在2015年第二臨床醫(yī)學(xué)院本科新生入學(xué)宿舍分配中，除優(yōu)先考慮需要照顧的有特殊情況的學(xué)生外，將作息規(guī)律作為重要參考條件之一，同時保證各地域生源學(xué)生混住，促進學(xué)生的交流，避免由于地域問題難以融入大學(xué)生活而被“邊緣化”[2]。

顧洲一在2019年基于數(shù)據(jù)思維提出了新的寢室分配方式。借助人工智能技術(shù)優(yōu)化學(xué)生寢室結(jié)構(gòu)，形成科學(xué)客觀的寢室分配系統(tǒng)[3]，此思維的提出對寢室全新分配方案作用不可小覷。應(yīng)該從事情的源頭上來解決寢室矛盾問題。這也可以證實借助智能化和算法來分配寢室是具有一定先進性和實用性的。

亓文杰在2019年提出同質(zhì)化的分配寢室，即學(xué)生被大學(xué)錄取后，就可以通過調(diào)研問卷了解學(xué)生來源地、日常愛好、性格基本特征[4]，來通過調(diào)查結(jié)果對寢室分配。這也是我們計劃使用K-means算法分配前的必須步驟，相比于人力分配通過相關(guān)算法更加精準(zhǔn)和高效。

楊蕙源在2020年談到南京大學(xué)的寢室分配方案問題。他們用大數(shù)據(jù)來對學(xué)生宿舍進行分配，南大采用“隱語義模型”算法量化評估新生之間的興趣愛好相似度[5]。這種對調(diào)查問卷的細化方法及大數(shù)據(jù)也是現(xiàn)代寢室分配的前沿?！半[語義模型”可以簡單概括為通過一些簡單的問題可以大致對學(xué)生的性格和習(xí)慣進行一些區(qū)分和聚類。

隨著時代的不斷發(fā)展，當(dāng)代青年學(xué)生的性格差異也越來越大。和諧的寢室生活對學(xué)生的生活、學(xué)習(xí)和心理都有有益的影響。所以，通過問卷調(diào)查結(jié)果來分配寢室對寢室文化來說顯得格外重要。

K-means是最典型的劃分式聚類算法之一，適合對大型數(shù)據(jù)集進行分析，運算效率高是其顯著優(yōu)點[6]。選擇K-means算法來計算調(diào)查問卷的結(jié)果和附加的權(quán)值是當(dāng)下較為合適的一種方法，也能較為精準(zhǔn)地分配一個合理的寢室。一個合理分配的宿舍會讓大學(xué)生的心靈更加健康，有更好的學(xué)習(xí)氛圍。相信通過Kmeans算法與調(diào)查問卷相結(jié)合的方式分配的寢室會令更多人所滿意的。

3 K-means算法的應(yīng)用

選取W={w1，w2，…，wn}為我們的待分配人員的節(jié)點集合，相似度則用以下公式來計算：

根據(jù)公式（1），我們的待分配寢室人員x問卷答案的集合為Xx，待分配寢室人員y問卷答案的集合為Xy，x與y待分配寢室人員答案結(jié)果相同的為Rx,y。以此類推便可以算出我們想要的分配寢室的數(shù)據(jù)。

根據(jù)節(jié)點相似度計算公式，推導(dǎo)出用戶x節(jié)點的加權(quán)度界定表達式與加權(quán)聚集度定義式，分別如下所示[7]：

這種加權(quán)的方式也是為了能更加準(zhǔn)確地分出和諧的寢室，我們將把調(diào)查問卷中不同的問題賦予不同的權(quán)值。有些重要的問題權(quán)值就相對更高一些，有些沒那么重要的問題，我們設(shè)置的權(quán)值也會相對的調(diào)低一些。所以加權(quán)來對問卷分析這一點也是我們選取K-means算法中重要的一點。因此也解決了一些關(guān)于問卷的問題。

（1）從若干元素中以隨機的方式選擇k個元素，以這k個元素作為k個簇的中心。

（2）單個計算除k外所有元素到k個簇的中心的距離，將每個元素都找到相距最近的中心，并劃分到該簇。

（3）根據(jù)以上所得結(jié)果，再次計算k個簇的中心，以每簇的平均值作為每簇的中心。

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

（5）一直重復(fù)（4）過程，直到數(shù)據(jù)不再變化。

我們將學(xué)生的數(shù)量定義為若干元素，當(dāng)然學(xué)生數(shù)量不會是一個巨大的數(shù)值，因為考慮到性別、專業(yè)甚至是班級的因素。這樣在算法運行時會更容易找到每個簇的中心，也就是我們認(rèn)為的寢室中心。我們會在這些的基礎(chǔ)上在進行K-means聚類分析算法來實現(xiàn)我們的想法。其中的k就是我們最后要得到的劃分出的寢室的數(shù)量。通過不斷地重復(fù)步驟（4）直到數(shù)據(jù)不再變化，就可以得到最終我們想要的寢室數(shù)據(jù)。

關(guān)于加權(quán)問題，每個學(xué)生所最在意的條件我們將把該項的權(quán)值升高，例如大部分人會在意室友的休息時間及睡眠質(zhì)量，我們就可以把這一項賦值為5。如果是不太重要的問題，我們將會賦值為1。既然能在調(diào)查問卷上體現(xiàn)出的問題也都是相對比較重要的。這樣加上權(quán)值的一個分配更有助于寢室分配的合理性與實用性。

4 K-means實驗結(jié)果及分析

此時我們不妨以生活習(xí)慣和性格為主要參考依據(jù)，對學(xué)生寢室進行劃分，性格孤僻賦值為1，活潑賦值為2，隨和賦值為5，生活習(xí)慣中喜歡熬夜賦值為3，不喜歡熬夜賦值為4，有潔癖賦值為6，沒有潔癖賦值為7。這里假設(shè)有10個同學(xué)，需要分到兩個寢室。這四個同學(xué)的生活習(xí)慣以及性格如表1所示。

表1 實驗樣例數(shù)據(jù)表

第一次劃分：假定隨機選擇兩個對象，如序號1和序號2作為劃分點，我們通過計算每個點到最近對象的歐氏距離，并產(chǎn)生了兩個簇{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）。

第二次劃分：通過計算出的兩個平均值點重新調(diào)整對象所在的簇，并重新劃分，即將所有的點按照離（2.8，3.4，6），（2.4，3.6，7）最近的原則重新分配。得到兩個新的簇{1，3，5，7，10}，{2，4，6，8，9}。發(fā)現(xiàn)并未重新分配，則說明結(jié)果已經(jīng)收斂，實驗結(jié)果如表2所示。

表2 實驗結(jié)果表

按照此種方式進行的劃分，即讓有潔癖同時晚上喜歡熬夜的同學(xué)盡可能分到一個寢室；沒潔癖晚上不喜歡熬夜的同學(xué)可能分到一個寢室；同時也讓性格開朗、孤僻和隨和的同學(xué)混合分配。這樣劃分會更加有利于寢室氛圍和諧和學(xué)生的成長。

5 K-means與其他聚類算法的比較

K-means算法是聚類分析方法中的一種，選用K-means算法是因為它能在大規(guī)模的數(shù)據(jù)中進行聚類是能較為精準(zhǔn)且高效地對數(shù)據(jù)進行分類，并且算法對數(shù)值型數(shù)據(jù)的聚類效果好，聚類結(jié)果也與數(shù)據(jù)的輸入順序無關(guān)。這樣的一個前提條件更有益于做精準(zhǔn)的寢室分配，讓結(jié)果與預(yù)期偏差不會太大。K-means算法不但使用起來高效而且可伸縮，而且這種算法通俗易懂，使用起來也比較簡便。這種算法也更加適用于日常生活中。下面是一些其他聚類算法與K-means算法的比較：

（1）拿系統(tǒng)聚類方法來作為對比的話，在寢室分配方案中選擇系統(tǒng)聚類的方法的情況下，我們的調(diào)查問卷內(nèi)容將變得單一，但沒有任何單一的問題就可以解決寢室分配的難題。而且也很難將我們需要的問卷中所有數(shù)據(jù)整合在一起來進行分類。相對于系統(tǒng)聚類方案來比較，K-means算法是能在寢室分配問題上起到更好的解決作用的算法。

（2）K-median是一個與K-means較為相似的一種算法。雖然說在某種程度上K-median在K-means算法的基礎(chǔ)上有提高點，但是它是使用簇的中值向量來重新計算質(zhì)點對異常值不敏感。而在我們的分配方案中，是需要考慮到異常值得處理的，而且異常值也作為這個項目的重要點，例如有的人有一些比較特殊的習(xí)慣，雖然大部分人沒有但這一點對于很多人而言都是至關(guān)重要的一點，這種情況將難以處理。所以在這個項目中選擇K-means算法更優(yōu)于K-median算法

（3）DBSCAN算法也是大家所熟悉且經(jīng)常被選擇的一種聚類分析算法。這種算法雖然有很多的優(yōu)點，但也正因為它能過濾掉不合適的點，但對于我們的需求來說，我們不能隨意去排除任何一個需要獲得寢室的學(xué)生名單。所以假使我們用這種方式來進行一個固定人數(shù)分配的寢室是難為實現(xiàn)的。因此在對比中，我們選擇K-means算法。

（4）GMM算法，雖然GMM可以容納一些“混合”成員，但可能陷入局部極值的情況，它的運算需要進行多次迭代。基于時間和正常運行規(guī)律的考慮。在GMM與K-means算法的比較重，該寢室分配方案也更傾向與K-means算法。

基于運算簡單、結(jié)果精確、不大材小用的原則，我們也認(rèn)為K-means算法是在聚類分析算法中較為適用于寢室分配方案的一種算法，它既可以準(zhǔn)確地分出我們想要的寢室結(jié)果，又能提高分出寢室的速率，無論從哪個角度看選擇它都是無疑的。

6 結(jié)語

現(xiàn)有的高校寢室分配方案大多基于隨機分配的方式或者說單單基于成績、家鄉(xiāng)這樣的方式來確定一個最終的寢室人員構(gòu)成。這種方式雖然簡潔且可以快速分配，但經(jīng)過若干年的實踐來看，它并不能達到一個積極的效果。很多宿舍也因為性格和生活習(xí)慣等問題發(fā)生了許多的事故。因此能夠參照性格和生活習(xí)慣來對寢室進行一個合理的分配也是對學(xué)習(xí)和生活有一個積極的影響的。那么對于這樣一個有條件要求的聚類分配，K-means算法是幾種相關(guān)算法中比較突出有用的方法。通過K-means算法與隱語義模型的調(diào)查問卷相結(jié)合的方式來進行寢室分配無疑是一個避免寢室矛盾使寢室文化更加積極陽光的好辦法。