基于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可以容納一些“混合”成員，但可能陷入局部極值的情況，它的運算需要進行多次迭代?；跁r間和正常運行規律的考慮。在GMM與K-means算法的比較重，該寢室分配方案也更傾向與K-means算法。

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

6 結語

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