夏建兵　廖大強(qiáng)

摘要：針對現(xiàn)有基于密度聚類算法在簇?cái)U(kuò)展方法上的優(yōu)勢及其聚類判據(jù)的弊端，提出了一種融入啟發(fā)式思想的基于密度的DOC算法。啟發(fā)式DOC算法通過降低掃描數(shù)據(jù)的個(gè)數(shù)，加快DOC算法的運(yùn)行速度。實(shí)驗(yàn)表明，算法在聚類精度、執(zhí)行效率方面具有一定的優(yōu)越性，能夠發(fā)現(xiàn)任意形狀分布的數(shù)據(jù)。

關(guān)鍵詞：映射聚類；DOC算法；高維數(shù)據(jù)；學(xué)生成績；啟發(fā)式算法

中圖分類號：TP311.13 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599（2013）01-0183-02

1 引言

教學(xué)管理及教學(xué)指導(dǎo)中學(xué)生成績的分析往往缺乏系統(tǒng)的指導(dǎo)，各高等學(xué)校普遍所采取的成績分析方式僅為綜合成績排序、單科成績排序、平均成績排序等。常用的數(shù)據(jù)挖掘方法在發(fā)現(xiàn)數(shù)據(jù)隱藏規(guī)律時(shí)存在著某些不足，如關(guān)聯(lián)規(guī)則[1]發(fā)現(xiàn)課程間的關(guān)聯(lián)，需要大量的先驗(yàn)知識；而聚類算法，在高維空間內(nèi)，由于數(shù)據(jù)稀疏使得傳統(tǒng)的聚類算法[2]不利于高維計(jì)算，且無法同時(shí)得到課程間的相關(guān)性[2]。

2 映射聚類算法分析

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

3 啟發(fā)式算法加快DOC運(yùn)行速度的工作原理及過程

3.1 算法的主要思想

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

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

3.2 DOC算法的實(shí)驗(yàn)和分析

為了校驗(yàn)算法的正確性和有效性，用網(wǎng)格算法、傳統(tǒng)DOC算法和快速DOC算法進(jìn)行了分析比較。圖1是在數(shù)據(jù)個(gè)數(shù)n=100k，維數(shù)d=100的數(shù)據(jù)集上，測試DOC算法和基于網(wǎng)格的聚類算法聚類準(zhǔn)確度。

實(shí)驗(yàn)數(shù)據(jù)充分表明，DOC算法作為一種基于密度的聚類算法，不論從準(zhǔn)確度還是效率上來講，都無疑是最優(yōu)秀的算法，這正是本系統(tǒng)的核心價(jià)值體現(xiàn)點(diǎn)。

4 快速DOC算法及其學(xué)生成績分析中的應(yīng)用

考試成績是衡量學(xué)生對知識掌握情況的重要指標(biāo)，同時(shí)，采用映射聚類對學(xué)生成績進(jìn)行分析可以將學(xué)生分為不同的組群，發(fā)現(xiàn)各科目間的相關(guān)性，為學(xué)生選課提供了重要參考依據(jù)，校方教務(wù)部門也可以據(jù)此制定詳細(xì)合理的教學(xué)計(jì)劃。

4.1 確定聚類對象及目標(biāo)

為了驗(yàn)證本文所提出的DOC算法在學(xué)生成績數(shù)據(jù)挖掘中的有效性與可靠性，本文以某高校國際貿(mào)易專業(yè)的學(xué)生成績作為實(shí)驗(yàn)對象，經(jīng)處理得到樣本個(gè)數(shù)為45000個(gè)，對應(yīng)11個(gè)科目，詳情如下：

5 結(jié)論

通過歸納總結(jié)DOC算法的特點(diǎn)，結(jié)合學(xué)生成績的實(shí)際情況論文詳細(xì)的介紹了以DOC算法為基礎(chǔ)的學(xué)生成績分析的數(shù)據(jù)挖掘模型的建立過程。針對學(xué)生成績數(shù)據(jù)的特點(diǎn)對其中具體的數(shù)據(jù)預(yù)處理過程方法做了有益的探索與嘗試，并通過實(shí)驗(yàn)證明了該方法的可行性。

參考文獻(xiàn)：

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

[2]菜廣基，嚴(yán)玉清，李師賢.最小一乘聚類中心模型及算法[J].計(jì)算機(jī)科學(xué)，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.