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

謝靖萱，徐宏達(dá)，秦溧，張曉霞

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

1 問題的提出

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 K-means實(shí)驗(yàn)結(jié)果及分析

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

表1 實(shí)驗(yàn)樣例數(shù)據(jù)表

第一次劃分：假定隨機(jī)選擇兩個(gè)對(duì)象，如序號(hào)1和序號(hào)2作為劃分點(diǎn)，我們通過計(jì)算每個(gè)點(diǎn)到最近對(duì)象的歐氏距離，并產(chǎn)生了兩個(gè)簇{1，3，5，7，10}，{2，4，6，8，9}。對(duì)于簇{1，3，5，7，10}平均值點(diǎn)為（2.8，3.4，6），對(duì)于簇{2，4，6，8，9}平均值點(diǎn)為（2.4，3.6，7）。

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

表2 實(shí)驗(yàn)結(jié)果表

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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