李 涵，傅文鴻，范昱煊，焦宇航，胡雪巍，黨 赫

（北京信息科技大學(xué)理學(xué)院，北京 100096）

隨著信息技術(shù)的高速發(fā)展，計算機技術(shù)已經(jīng)被運用到各個領(lǐng)域，極大促進了生產(chǎn)力的提升，也在高等院校的信息化管理中凸顯了極大的便利。宿舍作為高校進行系統(tǒng)化管理的重要組成單位，是高校學(xué)生最主要的生活場所，宿舍管理事關(guān)一所學(xué)校的校風(fēng)與學(xué)生的生活體驗。近年來高校招生人數(shù)的不斷增加，宿舍間人際關(guān)系問題日益浮現(xiàn)，傳統(tǒng)管理方式也顯現(xiàn)出其弊端所在。傳統(tǒng)管理方式不能很好勝任宿舍日常管理需求，因此越來越多的高校都已經(jīng)逐漸開始將信息化技術(shù)應(yīng)用于校園管理中。當(dāng)前絕大多數(shù)高校普遍依靠性別、專業(yè)、班級、學(xué)號等進行宿舍分配，沒有更多考慮學(xué)生個性發(fā)展的多樣化因素，如何利用計算機強大的數(shù)據(jù)分析能力實現(xiàn)智能化宿舍分配是當(dāng)下宿舍管理中相當(dāng)值得思考的問題[1-2]。在此設(shè)計實現(xiàn)一款基于數(shù)據(jù)挖掘技術(shù)的宿舍智能分配系統(tǒng)，對解決上述問題做出嘗試。

2 算法基礎(chǔ)

2.1 數(shù)據(jù)挖掘技術(shù)

數(shù)據(jù)挖掘[3]針對隱含于某個大數(shù)據(jù)集中的先前未知的并具有潛在價值信息。數(shù)據(jù)挖掘技術(shù)是涉及到機器學(xué)習(xí)、統(tǒng)計學(xué)和數(shù)據(jù)庫系統(tǒng)的交叉方法，是計算機科學(xué)和統(tǒng)計學(xué)的一個跨學(xué)科子領(lǐng)域，其總體目標(biāo)是通過智能化方法從數(shù)據(jù)集中提取信息，并將這些信息轉(zhuǎn)換為可理解的結(jié)構(gòu)以供進一步使用。數(shù)據(jù)挖掘包括聚類分析、異常檢測、關(guān)聯(lián)規(guī)則挖掘、順序模式挖掘等內(nèi)容。完整的數(shù)據(jù)挖掘流程如圖1。

圖1 數(shù)據(jù)挖掘流程圖

2.2 k-means聚類算法

1967年James MacQueen提出的k均值聚類算法（k-Means Clustering Algorithm）是一種迭代求解的聚類分析算法[4-5]。數(shù)據(jù)被分為k組，隨機選取k個對象作為初始的聚類中心，計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據(jù)聚類中現(xiàn)有的對象被重新計算。這個過程將不斷重復(fù)直到滿足某個終止條件。終止條件可以是沒有（或最小數(shù)目）對象被重新分配給不同的聚類、沒有（或最小數(shù)目）聚類中心再發(fā)生變化、誤差平方和局部最小。

k-means聚類算法思想分析及數(shù)學(xué)分析如下[6]：

輸入：簇的數(shù)目k和含有n個數(shù)據(jù)對象的數(shù)據(jù)集。

處理流程：從數(shù)據(jù)集中選擇k個對象作為初始聚類中心→計算每個聚類對象到聚類中心的距離來劃分→再次計算每個聚類中心→計算的標(biāo)準(zhǔn)測量功能。如果達到最大迭代次數(shù)，停止，否則繼續(xù)。

k-means聚類算法操作簡單、運算速度較快，能夠有效地處理中小型數(shù)據(jù)集。但是也存在缺點：kmeans聚類算法的初始聚類中心是隨機選擇的，因此初始中心點選取的好壞會導(dǎo)致最終的聚類效果不同。選擇不同的初始聚類中心將改變由最終集群獲得的集群。另外，k-means聚類一般算法使用準(zhǔn)則函數(shù)作為目標(biāo)函數(shù)，并且僅存在一個全局最小和N最小值的準(zhǔn)則函數(shù)[7]，這使得算法在運算過程中將陷入局部極小，所以最后的結(jié)果是不是全局最優(yōu)解還不確定。除此之外，k-means聚類算法中k表示聚簇的個數(shù)，聚類結(jié)果取決于k值的選取[8]，然而k值的選取需要根據(jù)實際的需求來確定，通常情況下并不知道要將數(shù)據(jù)集聚為多少個類簇最為合適，因此針對k值的選取問題依然有待解決。

3 宿舍智能分配系統(tǒng)

在此設(shè)計并實現(xiàn)一款基于數(shù)據(jù)挖掘技術(shù)的宿舍智能分配系統(tǒng)。在理想情況下，能夠?qū)崿F(xiàn)每個宿舍中的學(xué)生的生活作息大致相同，性格類似且愛好相通。

3.1 問卷設(shè)計方案

在進行聚類之前需要獲取數(shù)據(jù)。設(shè)計采用調(diào)查問卷的方式，獲取新生的基本信息，并進行預(yù)處理。調(diào)查問卷設(shè)計分為三個步驟：

1)對學(xué)生的姓名、性別、學(xué)院、專業(yè)、班級、生活等基本信息進行采集，并收取各種生活習(xí)慣數(shù)據(jù)，如睡覺的時間等。對于學(xué)生宿舍分類，將得到的數(shù)據(jù)先按性別、校區(qū)、學(xué)院等梯度分類，再將“某學(xué)院”這一梯度的學(xué)生的生活作息時間劃分為一個個區(qū)間。

2)采集詳細(xì)的性格特征。性格包括：大方外向、自制力、敏感、責(zé)任心、衛(wèi)生五個方面。在調(diào)查問卷中，這五個大方向共有20道小題，每個大方向有四個小題，每個小題有四個選項，選項根據(jù)得分按序排列，分?jǐn)?shù)賦值提前按照順序排列好，從A到D分別是1到4分，生成表格時按序號生成，那么每個序號就對應(yīng)了相應(yīng)的得分。

3)愛好選擇。此部分應(yīng)用了5道多項選擇題，分別為每個人喜歡的運動、劇種、書籍、游戲、音樂類別。當(dāng)導(dǎo)出為表格時，此部分的表格每一列的列名變?yōu)轭}目的選項，表格元素也不再是選項的序號，而改用0或者1來表示是否有此愛好。在后續(xù)聚類過程中，假若第二次分類時，有宿舍人數(shù)達到飽和，學(xué)生得分相近，那么就要依靠此部分將學(xué)生進行詳細(xì)拆分，篩選愛好相對差異較小的學(xué)生。

3.2 數(shù)據(jù)庫設(shè)計

對前一步調(diào)查問卷得到的信息進行導(dǎo)出，存入數(shù)據(jù)庫中。由于調(diào)查問卷的問題內(nèi)容過于冗長，需要先修改列名以使語句精簡。修改完成后，將數(shù)據(jù)進行分層處理。修改完的數(shù)據(jù)表生成為原始層的數(shù)據(jù)表，再用查詢語句生成數(shù)據(jù)運營層（Operational Data Store,ODS）。實際語句如圖2所示。

圖2 性格得分處理語句

圖中語句處理的是問卷第二部分。將每個性格的得分匯總，并只生成五列，對應(yīng)五個性格。隨后從ODS層提取數(shù)據(jù)，形成新的表，當(dāng)做新的一層數(shù)據(jù)倉庫（Data Warehouse,DW）層，部分語句如圖3。

圖3 倉庫層處理相關(guān)部分語句

這一層分為三個表，每個表的主鍵都是學(xué)生的學(xué)號，在聚類時，先根據(jù)基本信息表進行梯度分類，再按照性格表和愛好表進行聚類。其中，性格為聚類的主要依據(jù)，愛好為次要依據(jù)，如超出一個宿舍最大容量的人數(shù)性格相似，可再按照愛好分類。最終表的分層結(jié)構(gòu)如圖4所示。

圖4 數(shù)據(jù)庫表結(jié)構(gòu)

3.3 宿舍聚類和分類

k值的選取根據(jù)給學(xué)生安排的宿舍個數(shù)自行填寫，這樣聚類得出的每一個簇即為一個宿舍。若有m個學(xué)生填寫了問卷，每個宿舍可安排n個人入住，則k=m/n，暫設(shè)n=6。

初始聚類中心的選擇是根據(jù)性格表（dw_nature）當(dāng)中的五個性格特點（outgoing，selfcontrol，sensitive，responsibility，health）作為一個五維向量基，取所有學(xué)生中的前k個學(xué)生的性格特點構(gòu)成的五維向量為初始的k個聚類中心。計算每一個學(xué)生的性格向量與聚類中心的歐氏距離，根據(jù)k-means算法的思想迭代運算，即可得到每個學(xué)生與簇心的距離，最接近某一簇心的n個學(xué)生即分配到同一宿舍。聚類過程如圖5所示。

圖5 k-means聚類過程

當(dāng)聚類完成之后，有可能會出現(xiàn)極端值的情況，比如該簇已經(jīng)聚入了5個學(xué)生，但是之后又出現(xiàn)了5個學(xué)生與簇心距離相同，但是一個簇里只能有6個學(xué)生，這時就需要剔除4個學(xué)生。此時應(yīng)以如下方法處理：

先將n個元素分成x1,x2,...,xn，然后計算x1到x2、x3、……xn各點的距離l1i。這是將愛好多選題中的每個選項取出，將x1與xi之間的選項求異或（選項為多選，其中的內(nèi)容都是為0，1的int型元素），把各個異或的數(shù)值進行相加，得出的距離就是x1與xi之間的距離l1i。

4 實驗結(jié)果

對系統(tǒng)進行實驗測試。在實驗中，由學(xué)生通過填寫調(diào)查問卷，為聚類提供數(shù)據(jù)。部分調(diào)查問卷如圖6所示。

圖6 調(diào)查問卷形式

從問卷收集到的信息并不是直接進行聚類，而是先按照事先分配的性別和學(xué)院，將原本的數(shù)據(jù)進行初步分類，如分類得到“理學(xué)院男”、“理學(xué)院女”、“計算機學(xué)院男”、“計算機學(xué)院女”等類別。在每個小類別中，利用k-means算法進行聚類。其中k值為宿舍的數(shù)量，k初值選取為小類中前k個學(xué)生信息，距離是通過性格的五維向量計算得來的歐氏距離。其中聚類結(jié)果與簇內(nèi)距離如圖7所示。

圖7 聚類結(jié)果

完成宿舍智能分配后，可以通過前臺界面查詢結(jié)果，如圖8所示。

圖8 查詢結(jié)果圖

通過在數(shù)據(jù)庫中查看聚類結(jié)果及簇內(nèi)距離，也能證明以該方法進行宿舍分類是有效的、可行的。

5 結(jié)束語

使用數(shù)據(jù)挖掘技術(shù)和k-means聚類思想，結(jié)合SQL server數(shù)據(jù)庫，研究并實現(xiàn)了高校宿舍智能分配系統(tǒng)。該方案將基本信息、性格、愛好等各項屬性相近的學(xué)生安排至同一個房間，充分尊重了學(xué)生的個體差異，系統(tǒng)的功能模塊基本覆蓋了宿舍分配中可能遇到的各種問題，界面友好，操作簡單，具有可拓展性好、開發(fā)成本較低的特點，有效提高了學(xué)生對于宿舍分配的滿足感，為學(xué)生營造了溫馨和諧且更加人性化的宿舍氛圍，也為智慧校園的建設(shè)提供了具有價值的參考方案。