快速DOC算法及其學生成績分析中的應用研究

夏建兵　廖大強

摘要：針對現有基于密度聚類算法在簇擴展方法上的優勢及其聚類判據的弊端，提出了一種融入啟發式思想的基于密度的DOC算法。啟發式DOC算法通過降低掃描數據的個數，加快DOC算法的運行速度。實驗表明，算法在聚類精度、執行效率方面具有一定的優越性，能夠發現任意形狀分布的數據。

關鍵詞：映射聚類；DOC算法；高維數據；學生成績；啟發式算法

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9599（2013）01-0183-02

1 引言

教學管理及教學指導中學生成績的分析往往缺乏系統的指導，各高等學校普遍所采取的成績分析方式僅為綜合成績排序、單科成績排序、平均成績排序等。常用的數據挖掘方法在發現數據隱藏規律時存在著某些不足，如關聯規則[1]發現課程間的關聯，需要大量的先驗知識；而聚類算法，在高維空間內，由于數據稀疏使得傳統的聚類算法[2]不利于高維計算，且無法同時得到課程間的相關性[2]。

2 映射聚類算法分析

大多數聚類算法都是為聚類低維數據設計的，當數據的維度實際很高時（如超過十維，或者多某些任務中甚至超過數千維），這些聚類方法就面臨挑戰。這是因為當維度增加時，通常只有少數的幾維與某些簇相關，但是其他不相關維的數據可能會產生大量的噪聲而屏蔽真實的簇，使之無法發現。采用降維或特征提取來處理這一問題，則在不同的維度上能找到一個分類，同時又會丟失某些分類信息，即每個維度至少涉及到一個分類 [4]。DOC算法的主要優點是可以發現任意形狀的簇，對噪聲不敏感，并且對數據的輸入順序不敏感，不用事先指定簇的個數。同時還具有可以自動得到聚類的數目、以及一組維度相差很大的簇、可識別數據點稀少的簇等特點。鑒于此，本文采用DOC算法對學生成績進行數據分析。

3 啟發式算法加快DOC運行速度的工作原理及過程

3.1 算法的主要思想

啟發式算法的運用在提高DOC算法運行速度的同時要以降低聚類的質量為代價，如前面所分析的質量保證。但是，正如下面所討論的，計算簇大部分情況下與實際應用相關。在每一次內循環中，只計算集合 ，執行 次內循環以后，設 為 個維度集合中最大的一個，計算 。這樣只在外循環時掃描數據一次，而無法保證每次返回的簇的質量大于等于 ，這一方法返回一個一個大小為 -密度且維度較大的簇。如大部分模式發現和數據所用中的應用，映射聚類這些屬性已經足夠了。采用更進一步的方法減少計算量，給定閾值 ，一旦發現集合 ，且 ，計算相關的集合 ，并返回 。另外還設置內循環的上界為MAXITER，這一啟發式算法稱之為快速DOC算法。

從上述的算法描述可知，先通過外循環計算 ，從而每計算一個簇只要掃描一次數據集，另外，還需要訪問數據以選擇隨機樣本。但是，可以在一次掃描中選擇并保存所有的隨機樣本，且 最大為MAXITER。設判別集 大小為 ，內循環 次。由于每計算一個簇只要掃描一次數據集，相比常規DOC算法每計算一個簇要掃描m次數據集來說，運算速度有較大改觀。

3.2 DOC算法的實驗和分析

為了校驗算法的正確性和有效性，用網格算法、傳統DOC算法和快速DOC算法進行了分析比較。圖1是在數據個數n=100k，維數d=100的數據集上，測試DOC算法和基于網格的聚類算法聚類準確度。

實驗數據充分表明，DOC算法作為一種基于密度的聚類算法，不論從準確度還是效率上來講，都無疑是最優秀的算法，這正是本系統的核心價值體現點。

4 快速DOC算法及其學生成績分析中的應用

考試成績是衡量學生對知識掌握情況的重要指標，同時，采用映射聚類對學生成績進行分析可以將學生分為不同的組群，發現各科目間的相關性，為學生選課提供了重要參考依據，校方教務部門也可以據此制定詳細合理的教學計劃。

4.1 確定聚類對象及目標

為了驗證本文所提出的DOC算法在學生成績數據挖掘中的有效性與可靠性，本文以某高校國際貿易專業的學生成績作為實驗對象，經處理得到樣本個數為45000個，對應11個科目，詳情如下：

5 結論

通過歸納總結DOC算法的特點，結合學生成績的實際情況論文詳細的介紹了以DOC算法為基礎的學生成績分析的數據挖掘模型的建立過程。針對學生成績數據的特點對其中具體的數據預處理過程方法做了有益的探索與嘗試，并通過實驗證明了該方法的可行性。

參考文獻：

[1]方毅，張春元.基于數據挖掘的多策略研究生教育課程成績分析方法研究[J].計算機工程與科學，2009，31（6）：20-23.

[2]菜廣基，嚴玉清，李師賢.最小一乘聚類中心模型及算法[J].計算機科學，2008，35（7）：195-196.

[3]Ester M， Kriegel H P， Sander J， et al. Incrementai clustering for mining in a data warehousing environment[D]. In： Proceedings of the 24th International Conference on Very Large Databases（VLDB98），New York，1998：323-333.

[4]Bouguettaya A. On-line clustering[J].IEEE Transact ions on Knowledge and Data Engineering，1996，8 （2）：333-339.