聚類與關(guān)聯(lián)規(guī)則挖掘算法及其應(yīng)用研究

摘要：該文介紹了數(shù)據(jù)挖掘中兩種重要的算法：1）發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的聚類算法；2）應(yīng)用最為廣泛的挖掘方法之一關(guān)聯(lián)規(guī)則挖掘算法，并就它們?cè)趹?yīng)用型院校本科教學(xué)評(píng)估中的應(yīng)用進(jìn)行了研究。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類；關(guān)聯(lián)規(guī)則；置信度；支持度

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)27-1881-04

Clustering and Association Rule Mining Algorithms and Their Applications

WANG Ai-xia

(Nanjing University of Aeronautics and Astronautics and College of Information Science Technology， Nanjing 210016， China)

Abstract: In this paper，two important algorithms of data mining are introduced: 1) the clustering algorithm of found data distribution and hidden patterns; 2) the association rule mining algorithms which is one of the most widely used data mining methods. The application of the two algorithms in the undergraduate teaching evaluation of application-oriented college is studied in this paper.

Key words: data mining; clustering; association rules; confidence; support

1 前言

隨著信息化的飛速發(fā)展，信息量超指數(shù)上升，現(xiàn)今資料流通量之巨大已到了令人咂舌地步，就實(shí)際限制而言，便遇到了諸如巨量的紀(jì)錄，高維的資料增加的傳統(tǒng)分析技術(shù)上的困難，搜集到的資料僅有5%至10%用來(lái)分析，越來(lái)越多的數(shù)據(jù)來(lái)不及分析就過時(shí)了，也有的數(shù)據(jù)因其數(shù)據(jù)量極大而難以分析數(shù)據(jù)間的關(guān)系，以致出現(xiàn)了“數(shù)據(jù)豐富，信息貧乏（data rich but information poor）”的局面。快速增長(zhǎng)的海量數(shù)據(jù)收集存放在大型和大量數(shù)據(jù)庫(kù)中，沒有強(qiáng)有力的工具，理解它們已遠(yuǎn)遠(yuǎn)超出了人的能力。結(jié)果，收集在大型數(shù)據(jù)庫(kù)中的數(shù)據(jù)變成了“數(shù)據(jù)墳?zāi)埂薄y得再訪問的數(shù)據(jù)檔案。

對(duì)信息社會(huì)中的任何組織和個(gè)人來(lái)說(shuō)，其最大的資本就是將積累的“可用”數(shù)據(jù)轉(zhuǎn)化為“有用”信息，能“利用”所掌握的信息“預(yù)測(cè)不可知的未來(lái)”。因此“凡事預(yù)則立”，這就需要一種方法，能夠自動(dòng)地發(fā)現(xiàn)和描述各數(shù)據(jù)間隱含的關(guān)聯(lián)性與事態(tài)的發(fā)展趨勢(shì)，自動(dòng)地標(biāo)記異常數(shù)據(jù)，為管理決策提供更強(qiáng)有力的支持，充分發(fā)揮歷史數(shù)據(jù)的作用。數(shù)據(jù)挖掘技術(shù)迎合了人們的需求，為自動(dòng)和智能地把海量的數(shù)據(jù)轉(zhuǎn)化為有用的信息知識(shí)提供了有力的手段，給數(shù)據(jù)和信息之間的鴻溝架設(shè)了方便之橋。

2 數(shù)據(jù)挖掘概述

數(shù)據(jù)挖掘就是從海量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中挖掘出可能有潛在價(jià)值的信息的技術(shù)，具有如下特點(diǎn)：1）能發(fā)現(xiàn)反映系統(tǒng)局部特征和規(guī)律的模型；2）自動(dòng)趨勢(shì)預(yù)測(cè)，能發(fā)現(xiàn)“新”的知識(shí)；3）比較容易獲得很多規(guī)則，并能及時(shí)更新。

數(shù)據(jù)挖掘一開始就是面向應(yīng)用，為決策服務(wù)的，綜合了各個(gè)學(xué)科技術(shù)，有很多的功能，當(dāng)前主要功能如下：

1）分類：按照分析對(duì)象的屬性、特征，建立不同的組類來(lái)描述事物；

2）聚類：識(shí)別出分析對(duì)內(nèi)在的規(guī)則，按照這些規(guī)則把對(duì)象分成若干類；

3）關(guān)聯(lián)規(guī)則和序列模式的發(fā)現(xiàn)：關(guān)聯(lián)是某種事物發(fā)生時(shí)其他事物會(huì)發(fā)生的這樣一種聯(lián)系。而序列是一種縱向的聯(lián)系；

4）預(yù)測(cè)：把握分析對(duì)象發(fā)展的規(guī)律，對(duì)未來(lái)的趨勢(shì)做出預(yù)見；

5）偏差的檢測(cè)：對(duì)分析對(duì)象的少數(shù)的、極端的特例的描述，揭示內(nèi)在的原因。

數(shù)據(jù)挖掘的各項(xiàng)功能不是獨(dú)立存在的，在數(shù)據(jù)挖掘中互相聯(lián)系，發(fā)揮作用。作為一門處理數(shù)據(jù)的新興技術(shù)，數(shù)據(jù)挖掘有許多的新特征。首先，數(shù)據(jù)挖掘面對(duì)的是海量的數(shù)據(jù)。其次，數(shù)據(jù)可能是不完全的、有噪聲的、隨機(jī)的，有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，維數(shù)大。最后，數(shù)據(jù)挖掘是許多學(xué)科的交叉，運(yùn)用了統(tǒng)計(jì)學(xué)，計(jì)算機(jī)，數(shù)學(xué)等學(xué)科的技術(shù)。

3 聚類描述及其算法

3.1 聚類描述

聚類是由聚類分析工具根據(jù)一定規(guī)則，將數(shù)據(jù)對(duì)象分組成為多個(gè)類。在同一個(gè)類別中，個(gè)體之間的差異較小，具有很高的相似性（相關(guān)性），不同類別的個(gè)體之間差異較大（不相關(guān)性）。同一類別的相似性（同質(zhì)性）越大，不同類別間差別越大，聚類就越好。聚類分析問題可描述為：給定n維空間R中的n個(gè)向量，把每個(gè)向量歸屬到C個(gè)聚類中的某一個(gè)，使得每個(gè)向量與其聚類中心的距離最小。聚類分析可以建立宏觀的概念，發(fā)現(xiàn)數(shù)據(jù)的分布模式，以及可能的數(shù)據(jù)屬性之間的相互關(guān)系。聚類分析方法的核心只有兩個(gè)：一個(gè)是樣本的相似性度量問題，另一個(gè)是聚類準(zhǔn)則的問題。聚類方法包括統(tǒng)計(jì)分析方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法等。

3.2 凝聚型層次聚類介紹

凝聚層次聚類是一種自底向上的方法，將每一個(gè)對(duì)象看作一個(gè)聚類，把它們逐漸合并成越來(lái)越大的聚類。在每一層中，根據(jù)一些規(guī)則將距最近的兩個(gè)聚類合并，直到滿足預(yù)先設(shè)定的終止條件。

給定包含n個(gè)對(duì)象的數(shù)據(jù)集合D={t1，t2，……tn}，算法描述如下：

K=n；

For i=1 to n//在初始階段所有對(duì)象均單獨(dú)成為一類

Ci={ti}；

Repeat

Find the Ci andCj in D such that dis(Ci，Cj) is the smallest；//找到距離最小的兩個(gè)類

Ci= Ci U Cj；//將距離最小的兩個(gè)類合并產(chǎn)生新類

Delete Cj；//刪除已被合并的舊類

Until k=1；//直至所有對(duì)象被合并為一類

3.3 改進(jìn)的凝聚型層次聚類算法

1）算法改進(jìn)的基本思想：在初始譜系圖中，每一個(gè)對(duì)象仍單獨(dú)成為一類，將當(dāng)前所有距離小于距離閾值ε的類進(jìn)行合并，接下來(lái)重新對(duì)ε取值，進(jìn)行下一層次的合并，重復(fù)以上步驟直至到達(dá)結(jié)束條件。

2）改進(jìn)算法：給定包含n個(gè)對(duì)象的數(shù)據(jù)集合D={t1，t2 ，……tn}，算法描述如下：

K=n；

For i=1 to n//在初始階段所有對(duì)象均單獨(dú)成為一類

Ci={ti}；

ε=dmin+a(dmin+ dmax)；//計(jì)算距離閾值ε

//以下循環(huán)用于將所有距離小于ε的類合并While Find the Ci and Cj in D such that dis(Ci，Cj) is less thanεdoCi= Ci U Cj；

Delete Cj； K=k-1；End Until k=1；//直至所有對(duì)象合并為一類

3）算法分析：由于要存儲(chǔ)鄰接矩陣，層次算法的空間復(fù)雜性是O(n2)。存儲(chǔ)譜系圖的空間復(fù)雜性要比層次算法的空間復(fù)雜性O(shè)(n2)小得多，為O(kn)。在傳統(tǒng)層次凝聚算法中，合并閾值為2，將n個(gè)對(duì)象最終合并為一個(gè)簇中需要迭代n-1次，時(shí)間復(fù)雜度為O(n2)。在改進(jìn)的算法中，假設(shè)平均每次合并t個(gè)對(duì)象，則其迭代次數(shù)為n/t，其時(shí)間復(fù)雜度為O(n2/t)。當(dāng)t>1時(shí)，O(n2/t)>> O(n2)，顯然改進(jìn)算法大大縮短了聚類時(shí)間。

4 關(guān)聯(lián)規(guī)則基本概念及其算法

4.1 關(guān)聯(lián)規(guī)則的基本概念

關(guān)聯(lián)規(guī)則是由R.A grawal等人提出的，是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間某種潛在關(guān)系的規(guī)則，在數(shù)據(jù)挖掘的各種方法中應(yīng)用得最為廣泛，是數(shù)據(jù)中一種簡(jiǎn)單但很實(shí)用的規(guī)則。關(guān)聯(lián)規(guī)則模式屬于描述型模式，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的算法屬于無(wú)監(jiān)督學(xué)習(xí)的方法。

關(guān)聯(lián)規(guī)則可形式化描述如下：令I(lǐng)={i1，i2，i3，…，in}為一組屬性的可能取值，稱為數(shù)據(jù)項(xiàng)集（Itemset），其中ik（1≤i≤n）稱為數(shù)據(jù)項(xiàng)（item）。I中元素的個(gè)數(shù)稱為數(shù)據(jù)項(xiàng)集的長(zhǎng)度，長(zhǎng)度為n的數(shù)據(jù)項(xiàng)集稱為n維數(shù)據(jù)項(xiàng)集（n-Item-set）。一條關(guān)聯(lián)規(guī)則是如下形式的蘊(yùn)涵式X→Y，其中X，Y包含于I且X∩Y=φ，則稱規(guī)則X→Y在事務(wù)集合D中成立。一般用如下兩個(gè)參數(shù)描述一條規(guī)則的屬性：

1）置信度（Confidence）——如果D中包含X的事務(wù)有C%也同時(shí)包含Y，則C為關(guān)聯(lián)規(guī)則X→Y的置信度。置信度就是指在出現(xiàn)了數(shù)據(jù)項(xiàng)集X的事務(wù)中，數(shù)據(jù)項(xiàng)集Y也同時(shí)出現(xiàn)的概率有多大。即置信度C%=The number of Transactions(X∪Y)/The number of Transaction(X)。置信度就是指在出現(xiàn)了數(shù)據(jù)項(xiàng)集X的事務(wù)中，數(shù)據(jù)項(xiàng)集Y也同時(shí)出現(xiàn)的概率有多大。置信度是對(duì)關(guān)聯(lián)規(guī)則的準(zhǔn)確度的衡量。

2）支持度（Support）——如果D中有S%的事務(wù)同時(shí)包含數(shù)據(jù)項(xiàng)集X和Y，則稱S%為關(guān)聯(lián)規(guī)X→Y的支持度。支持度是對(duì)關(guān)聯(lián)規(guī)則重要性的衡量。即支持度S%=The number of Transactions(X∪Y)/The number of Transactions(D)。支持度說(shuō)明了這條規(guī)則在所有事務(wù)中有多大的代表性，支持度越大，關(guān)聯(lián)規(guī)則越重要，應(yīng)用越廣泛。

為了發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，需給定兩個(gè)閾值：最小支持度（Min Supp）和最小置信度（Min Conf）。關(guān)聯(lián)規(guī)則挖掘就是以給定的事務(wù)集合D中產(chǎn)生所有滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則的過程。可把關(guān)聯(lián)規(guī)則挖掘劃分為兩個(gè)子問題：

1）根據(jù)最小支持度找出數(shù)據(jù)集D中的所有頻繁項(xiàng)目集。是關(guān)聯(lián)規(guī)則挖掘的中心問題，是衡量關(guān)聯(lián)規(guī)則挖掘算法的標(biāo)準(zhǔn)。

2）根據(jù)頻繁項(xiàng)目集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。

4.2 關(guān)聯(lián)規(guī)則挖掘算法——Apriori算法

Apriori算法是關(guān)聯(lián)規(guī)則挖掘的核心算法，該算法堪稱是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，算法描述如下：

Input:DB，minsupp

Output:Result=所有的頻繁項(xiàng)集和它們的支持度。

方法：

Result:={};

K:=1；

C1:=所有的1-項(xiàng)集

While (Ck) do

Begin

為每一個(gè)Ck中的項(xiàng)集生成一個(gè)計(jì)數(shù)器；

For(i=1;i<=｜DB｜;i++)

Begin/*所有DB中的記錄T*/

對(duì)第i個(gè)記錄T支持的每一個(gè)Ck中的項(xiàng)集，其計(jì)數(shù)器加1；

End

Lk:= Ck中滿足大于minsupp的全體項(xiàng)集；

Lk的支持度保留；

Result:=Result(Lk) ；

Ck+1=所有的（k+1）-項(xiàng)集中滿足其k-子集都在Lk里的全體；

K:=k+1；

End do

Apriori算法是一種寬度優(yōu)先算法，該算法通過對(duì)數(shù)據(jù)庫(kù)D多趟掃描發(fā)現(xiàn)所有的頻繁數(shù)據(jù)項(xiàng)集，在每一趟掃描中只考慮具有同一長(zhǎng)度k（即項(xiàng)集中所含項(xiàng)目的個(gè)數(shù)）的所有k-項(xiàng)集。在第一趟掃描中，Apriori算法計(jì)算D中所有單個(gè)項(xiàng)的支持度，生成長(zhǎng)度為1的頻繁項(xiàng)集L1。在后續(xù)的每一趟掃描中，需要使用前一趟生成的頻繁項(xiàng)集Lk生成候選項(xiàng)集Ck+1，即合并有k-1個(gè)公共項(xiàng)的兩個(gè)Lk頻繁項(xiàng)（表示為L(zhǎng)k×Lk）然后掃描數(shù)據(jù)庫(kù)D，計(jì)算Ck+1中各候選項(xiàng)集的支持度，最后確定哪些候選項(xiàng)集真正成為該趟掃描的頻繁項(xiàng)集Lk+1。重復(fù)上述過程直到?jīng)]有新的頻繁項(xiàng)集生成。

5 聚類與關(guān)聯(lián)規(guī)則挖掘算法在應(yīng)用型院校本科教學(xué)評(píng)估中的應(yīng)用研究

5.1 應(yīng)用凝聚型層次聚類算法獲取不同成績(jī)特征的學(xué)生群體

從我校“正方教學(xué)管理系統(tǒng)”的學(xué)生成績(jī)庫(kù)中抽取一部分學(xué)生英語(yǔ)四級(jí)和專業(yè)課的成績(jī)數(shù)據(jù)，對(duì)其進(jìn)行凝聚型層次聚類分析，獲取具有不同成績(jī)特征的學(xué)生群體，就每個(gè)群體內(nèi)的學(xué)生分析其具有的共同特征。

1) 凝聚型層次聚類分析的初始數(shù)據(jù)如表1所示：

2）凝聚型層次聚類分析的結(jié)果

在spss13.0中輸入初始數(shù)據(jù)，進(jìn)行凝聚型層次聚類分析，得到如表2聚類結(jié)果。

3）凝聚型層次聚類分析結(jié)果描述及分析如表3所示：

通過聚類分析，可以看出學(xué)生英語(yǔ)四級(jí)與專業(yè)課的成績(jī)分布情況，有約三分之一的同學(xué)集中在第2類，第5類同學(xué)只是少數(shù)，第1、3、4類同學(xué)分布均勻，則在日常的教學(xué)管理中就要根據(jù)學(xué)生的特點(diǎn)改進(jìn)教學(xué)工作，調(diào)整教學(xué)方法，使學(xué)生全面發(fā)展。

5.2 關(guān)聯(lián)規(guī)則在教師教學(xué)質(zhì)量評(píng)價(jià)中的應(yīng)用

教學(xué)質(zhì)量評(píng)價(jià)不僅對(duì)教學(xué)起著調(diào)節(jié)、控制、指導(dǎo)和激勵(lì)作用，而且有很強(qiáng)的導(dǎo)向性，是學(xué)校教學(xué)管理重要的組成部分，是評(píng)價(jià)教學(xué)工作成績(jī)的主要手段。將關(guān)聯(lián)規(guī)則應(yīng)用于教師教學(xué)質(zhì)量評(píng)價(jià)，探討教師的年齡、職稱、學(xué)歷與教學(xué)效果之間的聯(lián)系。

1）數(shù)據(jù)預(yù)處理：選取我校“正方教學(xué)管理系統(tǒng)”中某二級(jí)學(xué)院2007-2008學(xué)年第一學(xué)期50名教師的教學(xué)數(shù)據(jù)，按照如下的數(shù)據(jù)變換規(guī)則：

數(shù)據(jù)變換規(guī)則1：

結(jié)果表明：對(duì)由中、老年教師所教授的課程，學(xué)生的評(píng)價(jià)較高，而對(duì)于年青教師，學(xué)生的評(píng)價(jià)多數(shù)為中，這就說(shuō)明在一定程度上，教師的年齡越大，教齡越長(zhǎng)，則其教學(xué)經(jīng)驗(yàn)越豐富，教學(xué)效果越好。則學(xué)校要依據(jù)挖掘結(jié)果合理配置班級(jí)的上課教師，保證學(xué)生保持良好的學(xué)習(xí)態(tài)度，有針對(duì)性地加強(qiáng)對(duì)青年教師的培養(yǎng)，使青年教師在老教師的言傳身教下，利用“傳、幫、帶”的方式，不斷積累教學(xué)經(jīng)驗(yàn)，提高教學(xué)水平，保證人才培養(yǎng)。

6 結(jié)束語(yǔ)

為了從海量的數(shù)據(jù)存儲(chǔ)中抽取模式、找出數(shù)據(jù)變化的規(guī)律和數(shù)據(jù)之間的相互關(guān)系，數(shù)據(jù)挖掘技術(shù)已成為計(jì)算機(jī)科學(xué)界的一大研究熱點(diǎn)，將數(shù)據(jù)挖掘技術(shù)應(yīng)用到應(yīng)用型院校本科教學(xué)評(píng)估中，必將客觀、科學(xué)、全面地對(duì)教學(xué)質(zhì)量進(jìn)行評(píng)價(jià)，提高教學(xué)評(píng)價(jià)的科學(xué)性、客觀性和準(zhǔn)確性，為管理決策提供信息，進(jìn)而提高教師的師資水平和教學(xué)效果，提高人才培養(yǎng)質(zhì)量，促進(jìn)教育事業(yè)的發(fā)展。

參考文獻(xiàn)：

[1] Han J，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京:機(jī)械工業(yè)出版社，2001.

[2] 呂爽，陳高云.數(shù)據(jù)挖掘技術(shù)在高校教學(xué)評(píng)估中的應(yīng)用[J].廣東廣播電視大學(xué)學(xué)報(bào)，2006，(3):24-27.

[3] 楊春建，石銳明，張宏.數(shù)據(jù)挖掘在青海大學(xué)教學(xué)評(píng)估中的應(yīng)用[J].計(jì)算機(jī)教育，2007，(8):57-59.

[4] 張彥釗，李霞.關(guān)聯(lián)規(guī)則在教學(xué)評(píng)價(jià)數(shù)據(jù)分析中的應(yīng)用[J].微計(jì)算機(jī)應(yīng)用，2005，26(5):616-619.

[5] 劉興波.凝聚型層次聚類算法的研究[J].科技信息，2008，(11):202.