基于數(shù)據(jù)挖掘技術(shù)的宿舍智能分配系統(tǒng)*

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

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

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

2 算法基礎(chǔ)

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

數(shù)據(jù)挖掘[3]針對(duì)隱含于某個(gè)大數(shù)據(jù)集中的先前未知的并具有潛在價(jià)值信息。數(shù)據(jù)挖掘技術(shù)是涉及到機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)和數(shù)據(jù)庫(kù)系統(tǒng)的交叉方法，是計(jì)算機(jī)科學(xué)和統(tǒng)計(jì)學(xué)的一個(gè)跨學(xué)科子領(lǐng)域，其總體目標(biāo)是通過(guò)智能化方法從數(shù)據(jù)集中提取信息，并將這些信息轉(zhuǎn)換為可理解的結(jié)構(gòu)以供進(jìn)一步使用。數(shù)據(jù)挖掘包括聚類分析、異常檢測(cè)、關(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組，隨機(jī)選取k個(gè)對(duì)象作為初始的聚類中心，計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對(duì)象就代表一個(gè)聚類。每分配一個(gè)樣本，聚類的聚類中心會(huì)根據(jù)聚類中現(xiàn)有的對(duì)象被重新計(jì)算。這個(gè)過(guò)程將不斷重復(fù)直到滿足某個(gè)終止條件。終止條件可以是沒(méi)有（或最小數(shù)目）對(duì)象被重新分配給不同的聚類、沒(méi)有（或最小數(shù)目）聚類中心再發(fā)生變化、誤差平方和局部最小。

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

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

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

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

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

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

3.1 問(wèn)卷設(shè)計(jì)方案

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

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

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

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

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

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

圖2 性格得分處理語(yǔ)句

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

圖3 倉(cāng)庫(kù)層處理相關(guān)部分語(yǔ)句

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

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

3.3 宿舍聚類和分類

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

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

圖5 k-means聚類過(guò)程

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

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

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

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

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

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

圖7 聚類結(jié)果

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

圖8 查詢結(jié)果圖

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

5 結(jié)束語(yǔ)

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