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

田春子 楊 萬 楊德會 王勇強 孫淑營

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

1 概述

現在人們大都是處在數據化的時代[3]，信息化迅速的發展，同時學校信息化進度也逐漸加快，校園里的信息化規模逐漸的擴大，例如學生存儲[3]在學校的校園卡日常消費數據、學期成績數據、去圖書館借書學習次數、課后上機實驗數據等校園活動，這些活動都一直在產生各種類型的數據，例如學生使用校園網產生的網絡日志也呈現指數級的增長，因此形成了學校里的大數據狀態[3]。

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

2 算法介紹

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

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

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

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

聚類算法是數據挖掘常見算法，通過挖掘的數據選定有效值（這里表示屬性），計算每個屬性的值（維度）對應的距離計算與閾值（分類的標準），距離是數據決定的，閾值可以通過結果去改變慢慢精確。

2.1 K-means 算法

k 均值聚類算法（k-means clustering algorithm）通過迭代分析計算獲取局部最優結果，一次次迭代都會使情況趨于穩定（最優）。

算法步驟：初始化目標點，通過計算與相應目標點較近的距離進行歸類，每次迭代更新目標點（可以是平均值）。終止條件可以是以下任何一個：

（1）沒有（或最小數目）對象被重新分配給不同的目標點。

（2）沒有（或最小數目）目標點再發生變化。

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

2.2 DBSCAN 算法

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

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

如果附近點的數量≥minPts，則當前點與其附近點形成一個簇，并且出發點被標記為已訪問(visited)。然后遞歸，以相同的方法處理該簇內所有未被標記為已訪問(visited)的點，從而對簇進行擴展。

如果附近點的數量＜minPts，則該點暫時被標記作為噪聲點。

如果簇充分地被擴展，即簇內的所有點被標記為已訪問，然后用同樣的算法去處理未被訪問的點。

3 算法應用與數據分析

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

3.1 K-Means 算法在學生行為分析中的應用

K-Means 算法在學生行為分析中的應用，在數據集中隨機挑選或者自動生成一個參照點（計算距離的樣本點），生成的點通常就是分類的個數，每個未被標記訪問的數據點，都將與這些生成的參照點進行距離計算，與較近的一個點歸為一類，依次對每個未標記訪問的點進行計算。

訪問一遍之后可以再進行迭代，從每個類里面再次隨機生成每個類里面的參照點，迭代次數越多分類變化會漸漸趨于穩定（分類可能不變化）。

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

01：Set＜Cluster＞chooseCenterCluster (){隨機選取中心點，構建成中心類。

02：Set＜Cluster＞點空間申請用來放點集合；

03：Random 隨機數用來隨機選取點的；

04：Point 從點集合中獲取隨機點使用隨機數挑選一個；

05：boolean 用來判斷點是否被選取;

06：if (cluster 是否與隨機點相同)

07：隨機點被使用就標記為false;

10：if (沒被標記為false)

11：增加集合點，數量加一；

12：return clusterSet;

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

14：float min_dis 距離;

15：兩點獲取最小距離;

16：if (點距離不同)

17：min_dis 獲取當前最小距離;

18：獲取點的id;

19：標記當前點的兩點間最小距離;

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

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

運行效果圖如圖1 所示。

以上的效果圖可以分析出對應屬性的分類情況，這里以canteen 與money 為例的數據分析統計，這里的輸出分類以后者的數值為準，所以是money，可以看出87.34（單位為百元）最多（人數），58.50 最少，以大局看來，大部分人花費8734 左右（元）都是比較多，從圖中信息看出花費6000-9000 生活費學生數量較多。

圖1 K-Means 分類統計效果圖（canteen 與money 屬性）

3.2 DBSCN 算法在學生行為分析中的應用

DBSCN 算法在學生行為分析中的應用，通過對數據的計算歸類，在數據中初始化一個點（數據隨機提取）作為本次迭代的起始點，并將其加入到數據集中；將取到的數據心點從未訪問樣本集合中標記為已使用；只要數據集不為空集，那么每次從其中提取出首個數據點，如果該數據點為起始對象，那么就將同時存在在該起始對象的數據集中的所有點和未訪問集合中的點記錄到數據集中，并且從中標記這些點；找到數據中所有的點后，集合數目增一，然后將那些出現在未訪問的集合原始拷貝中，且未出現在當前未訪問集合的點集合作為本次迭代生成的集合，最后從起始對象集合中標記出現的數據點；當不滿足迭代條件時，結束數據點訪問，繼續訪問其他未訪問的數據點。

DBSCAN 算法代碼如下：

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

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

02：boolean;//是否已經歸為某個類

03：boolean 標記為false;//是不是core 的"鄰居"

04：移除點//對某個core 點處理后就從core 集中去掉

05：for(point 遍歷點集合)

06：Isneighbour 標記為false;

07：isputToCluster 標記為false;

09：if cluster 是否與隨機點相同))//如果已經歸為某個類

10：隨機點被使用就標記為true;

11：break;

12：if(沒被標記為false)

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

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

15：添加該點

16：isneighbour 標記為true;

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

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

19：移除該點

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

運行效果圖如圖2 所示。

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

圖2 DBSCAN 分類統計效果圖（canteen 與money 屬性）

4 結果分析建議

4.1 K-Means 算法性能分析

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

4.2 DBSCAN 算法性能分析

DBSCAN 的效率較低，因為算法特性，會有重復處理的過程，但是在這里也優化了一番，速度提升明顯，在10000 個大數據的壓力下，最慢是2 分鐘左右，比起沒有優化過的無限期（30分鐘至少）快了很多，這個算法效率較低，空間要求也高。

5 算法分析比較

對算法的各個角度出發，分析算法的特性以及需要的標準，如表1。

6 結論

大數據是算法的用武之地，在本次的成果中解決了一次性的統計輸出，大大提高了數據統計的速度。

對算法的數據統計可以了解出學生的大體情況，可以通過實際考察來調整學生的在校活動，學校也可以通過結果來改善校園環境。

表1 算法 特性及標準

7 展望

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

（1）用戶不能有效看見數據的細節部分，比如分類的數據集。

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