基于K- Means 與DBSCAN 聚類算法據(jù)背景下基于高校綜合性數(shù)據(jù)的學(xué)生行為分析與研究

田春子 楊 萬 楊德會 王勇強(qiáng) 孫淑營

（北京交通大學(xué)海濱學(xué)院，河北 黃驊061199）

1 概述

現(xiàn)在人們大都是處在數(shù)據(jù)化的時代[3]，信息化迅速的發(fā)展，同時學(xué)校信息化進(jìn)度也逐漸加快，校園里的信息化規(guī)模逐漸的擴(kuò)大，例如學(xué)生存儲[3]在學(xué)校的校園卡日常消費(fèi)數(shù)據(jù)、學(xué)期成績數(shù)據(jù)、去圖書館借書學(xué)習(xí)次數(shù)、課后上機(jī)實(shí)驗(yàn)數(shù)據(jù)等校園活動，這些活動都一直在產(chǎn)生各種類型的數(shù)據(jù)，例如學(xué)生使用校園網(wǎng)產(chǎn)生的網(wǎng)絡(luò)日志也呈現(xiàn)指數(shù)級的增長，因此形成了學(xué)校里的大數(shù)據(jù)狀態(tài)[3]。

因此怎樣更好的利用信息結(jié)果去提升學(xué)生管理質(zhì)量和效率，是目前需要特別面對的問題，本文結(jié)合數(shù)據(jù)挖掘算法（K-Means 與DBSCAN）和大數(shù)據(jù)技術(shù)分析學(xué)生在校期間產(chǎn)生的多類型數(shù)據(jù)，從中得出有幫助的、有意義的結(jié)果，以便學(xué)校工作者更好的管理學(xué)生，提高他們的工作效率和服務(wù)質(zhì)量，讓學(xué)校管理工作人員對學(xué)生有更多的了解，讓他們在工作時能找到有價值的指導(dǎo)，從而可以為學(xué)生提供更好的幫助[3]。

2 算法介紹

聚類與分類有著離不開的關(guān)系，分類可以通過劃分歸類、層次歸類、密度、網(wǎng)格、模型法等等來分類。聚類需要具有很多較好的特點(diǎn)：

伸縮性：小于500 這樣的數(shù)據(jù)的處理可能會有較好的表現(xiàn)，但是在上萬甚至上百萬的數(shù)據(jù)量下可能出現(xiàn)的結(jié)果偏離，所以伸縮性是有必要的。

高緯度：在低維（二維或三維以下）的信息處理下，人們也許可以自己處理很快的處理出來，所以在高緯度的聚類分類是非常復(fù)雜的處理，具有高緯度處理也是有必要的。

數(shù)據(jù)挖掘中會出現(xiàn)的數(shù)據(jù)量的繁多、具有噪聲的、模糊的、隨機(jī)的，所以在數(shù)據(jù)量的堆積下分類可能出現(xiàn)一些效應(yīng)（結(jié)果不匹配）。通過聚類算法可以一步步解決，甚至自己可以從分類的結(jié)果中發(fā)現(xiàn)數(shù)據(jù)的奇特歸類。

聚類算法是數(shù)據(jù)挖掘常見算法，通過挖掘的數(shù)據(jù)選定有效值（這里表示屬性），計(jì)算每個屬性的值（維度）對應(yīng)的距離計(jì)算與閾值（分類的標(biāo)準(zhǔn)），距離是數(shù)據(jù)決定的，閾值可以通過結(jié)果去改變慢慢精確。

2.1 K-means 算法

k 均值聚類算法（k-means clustering algorithm）通過迭代分析計(jì)算獲取局部最優(yōu)結(jié)果，一次次迭代都會使情況趨于穩(wěn)定（最優(yōu)）。

算法步驟：初始化目標(biāo)點(diǎn)，通過計(jì)算與相應(yīng)目標(biāo)點(diǎn)較近的距離進(jìn)行歸類，每次迭代更新目標(biāo)點(diǎn)（可以是平均值）。終止條件可以是以下任何一個：

（1）沒有（或最小數(shù)目）對象被重新分配給不同的目標(biāo)點(diǎn)。

（2）沒有（或最小數(shù)目）目標(biāo)點(diǎn)再發(fā)生變化。

（3）誤差平方和局部最小[5]。

2.2 DBSCAN 算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。通過尋找對應(yīng)距離（半徑內(nèi)）進(jìn)行歸類，而且歸類的集合都是一起的（如果半徑?jīng)]有修改）。

算法步驟：DBSCAN[8]需要二個參數(shù)：掃描半徑（DR）和最小包含點(diǎn)數(shù)（minPts）。任選一個未被訪問（unvisited）的點(diǎn)開始，找出與其距離在DR 之內(nèi)（包括DR）的所有附近點(diǎn)。

如果附近點(diǎn)的數(shù)量≥minPts，則當(dāng)前點(diǎn)與其附近點(diǎn)形成一個簇，并且出發(fā)點(diǎn)被標(biāo)記為已訪問(visited)。然后遞歸，以相同的方法處理該簇內(nèi)所有未被標(biāo)記為已訪問(visited)的點(diǎn)，從而對簇進(jìn)行擴(kuò)展。

如果附近點(diǎn)的數(shù)量＜minPts，則該點(diǎn)暫時被標(biāo)記作為噪聲點(diǎn)。

如果簇充分地被擴(kuò)展，即簇內(nèi)的所有點(diǎn)被標(biāo)記為已訪問，然后用同樣的算法去處理未被訪問的點(diǎn)。

3 算法應(yīng)用與數(shù)據(jù)分析

K-Means 以屬性值計(jì)算出距離最近（最優(yōu)）進(jìn)行歸類，DBSCAN 以屬性值計(jì)算兩點(diǎn)距離是否在閾值范圍內(nèi)以此來歸類。與DBSCAN 不同的是DBSCAN 一次性就能出現(xiàn)結(jié)果，K-Means 可以通過迭代多次來精確閾值的范圍，而DBSCAN 只能通過結(jié)果觀察去慢慢改變（缺少靈活性），于此同時可以發(fā)現(xiàn)DBSCAN 是具有具體的結(jié)果數(shù)據(jù)（穩(wěn)定結(jié)果），K-Means 的隨機(jī)性較高，最后的結(jié)果會有一定偏差（這里的偏差指的是迭代的次數(shù)的影響）。K-Means 可以多屬性（高維）處理而DBSCAN 不行（這里只能二維），在數(shù)據(jù)分析中可能K-Means 在多維優(yōu)勢可以體現(xiàn)出來。

3.1 K-Means 算法在學(xué)生行為分析中的應(yīng)用

K-Means 算法在學(xué)生行為分析中的應(yīng)用，在數(shù)據(jù)集中隨機(jī)挑選或者自動生成一個參照點(diǎn)（計(jì)算距離的樣本點(diǎn)），生成的點(diǎn)通常就是分類的個數(shù)，每個未被標(biāo)記訪問的數(shù)據(jù)點(diǎn)，都將與這些生成的參照點(diǎn)進(jìn)行距離計(jì)算，與較近的一個點(diǎn)歸為一類，依次對每個未標(biāo)記訪問的點(diǎn)進(jìn)行計(jì)算。

訪問一遍之后可以再進(jìn)行迭代，從每個類里面再次隨機(jī)生成每個類里面的參照點(diǎn)，迭代次數(shù)越多分類變化會漸漸趨于穩(wěn)定（分類可能不變化）。

K-Means 算法偽代碼代碼如下：

01：Set＜Cluster＞chooseCenterCluster (){隨機(jī)選取中心點(diǎn)，構(gòu)建成中心類。

02：Set＜Cluster＞點(diǎn)空間申請用來放點(diǎn)集合；

03：Random 隨機(jī)數(shù)用來隨機(jī)選取點(diǎn)的；

04：Point 從點(diǎn)集合中獲取隨機(jī)點(diǎn)使用隨機(jī)數(shù)挑選一個；

05：boolean 用來判斷點(diǎn)是否被選取;

06：if (cluster 是否與隨機(jī)點(diǎn)相同)

07：隨機(jī)點(diǎn)被使用就標(biāo)記為false;

10：if (沒被標(biāo)記為false)

11：增加集合點(diǎn)，數(shù)量加一；

12：return clusterSet;

13：void cluster(Set＜Cluster＞clusterSet)//為每個點(diǎn)分配一個類

14：float min_dis 距離;

15：兩點(diǎn)獲取最小距離;

16：if (點(diǎn)距離不同)

17：min_dis 獲取當(dāng)前最小距離;

18：獲取點(diǎn)的id;

19：標(biāo)記當(dāng)前點(diǎn)的兩點(diǎn)間最小距離;

20：新清除原來所有的類中成員。把所有的點(diǎn)，分別加入每個類別

以上代碼為K-Means 對點(diǎn)的選取以及分類，介紹了K-Means 的主要思想。用需要先了解算法思想再去看代碼可能容易理解。

運(yùn)行效果圖如圖1 所示。

以上的效果圖可以分析出對應(yīng)屬性的分類情況，這里以canteen 與money 為例的數(shù)據(jù)分析統(tǒng)計(jì)，這里的輸出分類以后者的數(shù)值為準(zhǔn)，所以是money，可以看出87.34（單位為百元）最多（人數(shù)），58.50 最少，以大局看來，大部分人花費(fèi)8734 左右（元）都是比較多，從圖中信息看出花費(fèi)6000-9000 生活費(fèi)學(xué)生數(shù)量較多。

圖1 K-Means 分類統(tǒng)計(jì)效果圖（canteen 與money 屬性）

3.2 DBSCN 算法在學(xué)生行為分析中的應(yīng)用

DBSCN 算法在學(xué)生行為分析中的應(yīng)用，通過對數(shù)據(jù)的計(jì)算歸類，在數(shù)據(jù)中初始化一個點(diǎn)（數(shù)據(jù)隨機(jī)提?。┳鳛楸敬蔚钠鹗键c(diǎn)，并將其加入到數(shù)據(jù)集中；將取到的數(shù)據(jù)心點(diǎn)從未訪問樣本集合中標(biāo)記為已使用；只要數(shù)據(jù)集不為空集，那么每次從其中提取出首個數(shù)據(jù)點(diǎn)，如果該數(shù)據(jù)點(diǎn)為起始對象，那么就將同時存在在該起始對象的數(shù)據(jù)集中的所有點(diǎn)和未訪問集合中的點(diǎn)記錄到數(shù)據(jù)集中，并且從中標(biāo)記這些點(diǎn)；找到數(shù)據(jù)中所有的點(diǎn)后，集合數(shù)目增一，然后將那些出現(xiàn)在未訪問的集合原始拷貝中，且未出現(xiàn)在當(dāng)前未訪問集合的點(diǎn)集合作為本次迭代生成的集合，最后從起始對象集合中標(biāo)記出現(xiàn)的數(shù)據(jù)點(diǎn)；當(dāng)不滿足迭代條件時，結(jié)束數(shù)據(jù)點(diǎn)訪問，繼續(xù)訪問其他未訪問的數(shù)據(jù)點(diǎn)。

DBSCAN 算法代碼如下：

室內(nèi)環(huán)境中VOCs的來源是多種多樣的。木材在室內(nèi)，無論是木梁和柱材的實(shí)木形式，或作為工程產(chǎn)品人造板、地板或家具，都會排放VOCs。

01：private void densityConnected(double[][])

02：boolean;//是否已經(jīng)歸為某個類

03：boolean 標(biāo)記為false;//是不是core 的"鄰居"

04：移除點(diǎn)//對某個core 點(diǎn)處理后就從core 集中去掉

05：for(point 遍歷點(diǎn)集合)

06：Isneighbour 標(biāo)記為false;

07：isputToCluster 標(biāo)記為false;

09：if cluster 是否與隨機(jī)點(diǎn)相同))//如果已經(jīng)歸為某個類

10：隨機(jī)點(diǎn)被使用就標(biāo)記為true;

11：break;

12：if(沒被標(biāo)記為false)

13：continue;//已在聚類中，跳過，不處理

14：if(點(diǎn)的鄰居)//是目前加入的core 點(diǎn)的"鄰居"嗎？，ture的話，就和這個core 加入一個類

15：添加該點(diǎn)

16：isneighbour 標(biāo)記為true;

17：if (是鄰居)// 如果是鄰居，才會接下來對鄰居進(jìn)行densityConnected 處理，否則，結(jié)束這個core 點(diǎn)的處理

18：if(cores.contains(points[i]))

19：移除該點(diǎn)

以上代碼為DBSCAN 對點(diǎn)的分類，介紹了DBSCAN 的主要思想。用需要先了解算法思想再去看代碼可能容易理解。

運(yùn)行效果圖如圖2 所示。

以上的效果圖可以分析出對應(yīng)屬性的分類情況，這里以canteen 與money 為例的數(shù)據(jù)分析統(tǒng)計(jì)，這里的輸出分類以后者的數(shù)值為準(zhǔn)，所以是money，可以看出74.69（單位為百元）最多（人數(shù)），從圖中信息看出花費(fèi)6400-8300（元）生活費(fèi)學(xué)生數(shù)量較多，結(jié)合剛剛K-means 分析的結(jié)果可以看出7500 左右的花費(fèi)占主要，所以可以結(jié)合學(xué)生個人情況去建議學(xué)生每學(xué)期的花費(fèi)使用（增加生活費(fèi)或者減少生活費(fèi)）。

圖2 DBSCAN 分類統(tǒng)計(jì)效果圖（canteen 與money 屬性）

4 結(jié)果分析建議

4.1 K-Means 算法性能分析

在通過10000 個大數(shù)據(jù)的計(jì)算下本程序?qū)-Means 的效率相對滿意，對信息處理的速度較快，前期出現(xiàn)過空間棧的超出，也盡快解決，通過限定分類的數(shù)量（一次處理）。所以總體可以發(fā)現(xiàn)K-Means 的速度是較快的，但是對空間要求較高，不過已經(jīng)解決了。

4.2 DBSCAN 算法性能分析

DBSCAN 的效率較低，因?yàn)樗惴ㄌ匦裕瑫兄貜?fù)處理的過程，但是在這里也優(yōu)化了一番，速度提升明顯，在10000 個大數(shù)據(jù)的壓力下，最慢是2 分鐘左右，比起沒有優(yōu)化過的無限期（30分鐘至少）快了很多，這個算法效率較低，空間要求也高。

5 算法分析比較

對算法的各個角度出發(fā)，分析算法的特性以及需要的標(biāo)準(zhǔn)，如表1。

6 結(jié)論

大數(shù)據(jù)是算法的用武之地，在本次的成果中解決了一次性的統(tǒng)計(jì)輸出，大大提高了數(shù)據(jù)統(tǒng)計(jì)的速度。

對算法的數(shù)據(jù)統(tǒng)計(jì)可以了解出學(xué)生的大體情況，可以通過實(shí)際考察來調(diào)整學(xué)生的在?；顒樱瑢W(xué)校也可以通過結(jié)果來改善校園環(huán)境。

表1 算法 特性及標(biāo)準(zhǔn)

7 展望

從算法的應(yīng)用出發(fā)，算法的功能基本完善，但還是有考慮不是特別全面的地方需要進(jìn)一步完善，主要不足之處如下：

（1）用戶不能有效看見數(shù)據(jù)的細(xì)節(jié)部分，比如分類的數(shù)據(jù)集。

（2）初次接觸的用戶可能不了解算法機(jī)制存在迷惑。（3）算法優(yōu)化上可以結(jié)合分類算法來提高效率。