基于數據挖掘技術的宿舍智能分配系統*

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

（北京信息科技大學理學院，北京 100096）

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

2 算法基礎

2.1 數據挖掘技術

數據挖掘[3]針對隱含于某個大數據集中的先前未知的并具有潛在價值信息。數據挖掘技術是涉及到機器學習、統計學和數據庫系統的交叉方法，是計算機科學和統計學的一個跨學科子領域，其總體目標是通過智能化方法從數據集中提取信息，并將這些信息轉換為可理解的結構以供進一步使用。數據挖掘包括聚類分析、異常檢測、關聯規則挖掘、順序模式挖掘等內容。完整的數據挖掘流程如圖1。

圖1 數據挖掘流程圖

2.2 k-means聚類算法

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

k-means聚類算法思想分析及數學分析如下[6]：

輸入：簇的數目k和含有n個數據對象的數據集。

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

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

3 宿舍智能分配系統

在此設計并實現一款基于數據挖掘技術的宿舍智能分配系統。在理想情況下，能夠實現每個宿舍中的學生的生活作息大致相同，性格類似且愛好相通。

3.1 問卷設計方案

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

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

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

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

3.2 數據庫設計

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

圖2 性格得分處理語句

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

圖3 倉庫層處理相關部分語句

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

圖4 數據庫表結構

3.3 宿舍聚類和分類

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

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

圖5 k-means聚類過程

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

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

4 實驗結果

對系統進行實驗測試。在實驗中，由學生通過填寫調查問卷，為聚類提供數據。部分調查問卷如圖6所示。

圖6 調查問卷形式

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

圖7 聚類結果

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

圖8 查詢結果圖

通過在數據庫中查看聚類結果及簇內距離，也能證明以該方法進行宿舍分類是有效的、可行的。

5 結束語

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