聚類分析是數(shù)據(jù)挖掘的一個重要方法，廣泛應(yīng)用于文本處理、Web搜索等多領(lǐng)域。其中比較典型的有k-means和DBSCAN算法，K-means算法將數(shù)據(jù)點劃分到距離最近的中心點進行聚類，該類算法很難將非球形數(shù)據(jù)集聚類，DBSCAN算法可以對任意形狀的數(shù)據(jù)集進行聚類，但須指定一個密度閾值，從而可以去除噪聲點。

基于密度峰值的空間聚類算法Clustering by Fast Search and Find of Density Peaks(簡稱CFSFDP)，用于發(fā)現(xiàn)被低密度區(qū)域分離的高密度區(qū)域。與K-means算法相比，CFSFDP可自動獲取類的個數(shù)，且算法的復(fù)雜度相對較低。與DBSCAN算法相比，CFSFDP可在噪聲環(huán)境下聚類任意形狀數(shù)據(jù)集且實現(xiàn)簡單速度快。但同樣也存在如下缺點：(1)算法使用全局密度閾值，并沒有考慮數(shù)據(jù)空間的分布特性，所以當(dāng)數(shù)據(jù)密度和類間距分布不均勻時，聚類質(zhì)量不高；(2)當(dāng)一個類中存在多密度峰值時，CFSFDP算法雖然對數(shù)據(jù)點按密度值降序進行排序，但聚類效果并不理想。

針對現(xiàn)有技術(shù)的不足，本發(fā)明的目的是提供一種基于網(wǎng)格快速搜尋密度峰值的教育數(shù)據(jù)聚類方法，解決了原CFSFDP算法中使用全局密度閾值，當(dāng)數(shù)據(jù)密度和類間距分布不均勻時，聚類質(zhì)量不高的問題。

本發(fā)明技術(shù)方案如下：一種基于網(wǎng)格快速搜尋密度峰值的教育數(shù)據(jù)聚類方法，依次包括以下步驟，

步驟1：讀取數(shù)據(jù)庫中數(shù)據(jù)，進行數(shù)據(jù)預(yù)處理形成待聚類數(shù)據(jù)集，所述數(shù)據(jù)集包括學(xué)生在校學(xué)習(xí)和生活的若干屬性，所述屬性包括學(xué)生個人信息，學(xué)生選課成績信息，學(xué)生的畢業(yè)情況信息，把所述信息的子屬性當(dāng)作聚類算法的輸入屬性，所述子屬性包括學(xué)好、成績、性別、政治面貌、民族、籍貫和考生類別，設(shè)每個所述子屬性上的值在區(qū)間[l_i，h_i)中，i＝1，2，…，d，d為自然數(shù)，則S＝[l₁，h₁)×[l₂，h₂)×…×[l_d，h_d)構(gòu)成數(shù)據(jù)集； 

步驟2：計算單個網(wǎng)格單元的邊長side，以及每維區(qū)間數(shù)，根據(jù)計算結(jié)果，對數(shù)據(jù)集的每一個維度進行劃分，將其劃分成邊長相等且互不相交的網(wǎng)格單元，對于每一維的網(wǎng)格單元，保證取值區(qū)間都是左閉右開的，所述每一個維度為每個所述子屬性；

步驟3：對數(shù)據(jù)點進行映射，映射至對應(yīng)的網(wǎng)格單元中，獲取每維上對應(yīng)的下標(biāo)，所述數(shù)據(jù)點為所述數(shù)據(jù)集中的子屬性的值；

步驟4：對每一網(wǎng)格單元，計算其包含的數(shù)據(jù)點數(shù)，考察任一網(wǎng)格單元P相鄰的網(wǎng)格單元，與相鄰網(wǎng)格單元比較密度大小，并向密度大于網(wǎng)格單元P的網(wǎng)格單元進行擴展，得到網(wǎng)格單元合集，形成數(shù)據(jù)分區(qū)；

步驟5：計算各數(shù)據(jù)分區(qū)中各數(shù)據(jù)點x_i的局部密度ρ_i和距離δ_i并確定密度閾值dc，根據(jù)決策圖確定聚類中心及其個數(shù)；

步驟6：對非聚類中心的數(shù)據(jù)點進行歸類，根據(jù)密度閾值d_c確定各類的核心區(qū)域和邊界區(qū)域，并指定邊界區(qū)域中最高點密度值ρ_b作為去除噪聲點的閾值；

步驟7：假設(shè)邊界點p的密度閾值d_c鄰域中包含的核心點同屬于一個聚類中，則把該點p直接劃分到包含這些核心點的簇中；假設(shè)邊界點p同時落在幾個分屬于不同簇的核心點的d_c鄰域內(nèi)，那么就把該邊界點劃入距離最近的簇中；

步驟8：計算類間相似度，合并兩個滿足類間相似條件的類； 

步驟9：輸出聚類結(jié)果。

本發(fā)明的優(yōu)點是： 

通過對待聚類數(shù)據(jù)的劃分和擴展形成多個網(wǎng)格單元合集，將該合集作為一個數(shù)據(jù)分區(qū)，采用CFSFDP算法對各個分區(qū)進行局部聚類。在局部聚類時，各分區(qū)根據(jù)其數(shù)據(jù)分布密集程度選擇合適的密度閾值進行聚類，因而由全局密度閾值導(dǎo)致的聚類質(zhì)量下降的問題得以解決，同時保持了CFSFDP算法的快速和高效。當(dāng)一個類中存在多密度峰值時，本發(fā)明的聚類效果提升。本發(fā)明只關(guān)注各個數(shù)據(jù)點之間的相似性度量(距離或其他衡量標(biāo)準)且無需指定數(shù)據(jù)集的中心點，比k-means算法更適合沒有坐標(biāo)的數(shù)據(jù)集，其確定類中心點的方案簡潔而且精準。