基于Apriori 算法的關(guān)聯(lián)規(guī)則挖掘在人工智能+個(gè)性化學(xué)習(xí)系統(tǒng)中的實(shí)踐與研究

浦慧忠

（無錫城市職業(yè)技術(shù)學(xué)院 江蘇 無錫 214153）

0 引言

一個(gè)真實(shí)案例是尿不濕和啤酒在美國大型連鎖超市沃爾瑪一起銷售，但結(jié)果是銷量雙雙增加。分析這一現(xiàn)象的原因：在美國，有些年輕的爸爸常常會(huì)在工作之后跑到超級(jí)市場(chǎng)購買嬰兒的尿片，而30%～40%的爸爸則會(huì)購買自己的飲料。這是一個(gè)關(guān)于“尿片和啤酒”的關(guān)聯(lián)案例。關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)涵式，最早用于消費(fèi)者購物籃分析，通過研究消費(fèi)者放置在“購物籃”中的各種物品的相關(guān)性，它可以幫助企業(yè)更好地了解消費(fèi)者同時(shí)購買哪些產(chǎn)品，進(jìn)而制定相應(yīng)的市場(chǎng)戰(zhàn)略。

在日常生活中，個(gè)性化學(xué)習(xí)系統(tǒng)存在大量的學(xué)生學(xué)習(xí)資料，其中包括了他們的個(gè)人資料和學(xué)習(xí)習(xí)慣，但他們的實(shí)際應(yīng)用還遠(yuǎn)遠(yuǎn)沒有被發(fā)掘和開發(fā)。而運(yùn)用關(guān)聯(lián)法則來進(jìn)行學(xué)生的學(xué)習(xí)行為記錄，挖掘其中隱含的規(guī)律，是十分值得我們研究的課題。

1 研究背景與現(xiàn)狀

1.1 個(gè)性化學(xué)習(xí)的現(xiàn)狀與趨勢(shì)

2017年美國國家教育技術(shù)計(jì)劃《重塑技術(shù)的教育角色》中提到：“在移動(dòng)數(shù)據(jù)收集工具和在線協(xié)作平臺(tái)的支持下，能夠?yàn)樗袑W(xué)生獲得個(gè)性化學(xué)習(xí)服務(wù)提供機(jī)遇；在領(lǐng)導(dǎo)力部分指出：個(gè)性化學(xué)生學(xué)習(xí)將作為有效領(lǐng)導(dǎo)力的核心關(guān)注領(lǐng)域之一，技術(shù)能夠?yàn)閷W(xué)生提供個(gè)性化學(xué)習(xí)路徑；在測(cè)評(píng)部分指出：形成性和總結(jié)性評(píng)價(jià)數(shù)據(jù)的收集和整合，能支持學(xué)生生成個(gè)性化數(shù)字學(xué)習(xí)體驗(yàn)，以及教師制定教學(xué)干預(yù)和決策?！蓖晡覈鴩鴦?wù)院發(fā)布的《新一代人工智能發(fā)展規(guī)劃》明確提出：“利用智能技術(shù)加快推動(dòng)人才培養(yǎng)模式、教學(xué)方法改革，構(gòu)建包含智能學(xué)習(xí)、交互式學(xué)習(xí)的新型教育體系。”可以看出，收集和整合大量的、不同源的數(shù)據(jù)支持實(shí)現(xiàn)個(gè)性化學(xué)習(xí)是必然趨勢(shì)，而人工智能技術(shù)的出現(xiàn)及應(yīng)用將是實(shí)現(xiàn)這些數(shù)據(jù)價(jià)值最大化的關(guān)鍵。

目前，個(gè)性化學(xué)習(xí)的研究主要集中在以下3 個(gè)方面：（1）個(gè)性化特征分析及其對(duì)網(wǎng)絡(luò)學(xué)習(xí)行為研究；（2）個(gè)性化學(xué)習(xí)教學(xué)模式與服務(wù)策略研究；（3）個(gè)性化網(wǎng)絡(luò)學(xué)習(xí)系統(tǒng)與平臺(tái)設(shè)計(jì)研究。因此，將人工智能系統(tǒng)應(yīng)用于學(xué)校，整合教育人工智能和數(shù)據(jù)挖掘技術(shù)，跟蹤學(xué)生行為數(shù)據(jù)，預(yù)測(cè)學(xué)習(xí)成績，支持個(gè)性化學(xué)習(xí)已成必然趨勢(shì)。

1.2 關(guān)聯(lián)規(guī)則的概念與現(xiàn)狀

假設(shè)I={I1，I2，…，Im}是項(xiàng)的集合。給定一個(gè)數(shù)據(jù)庫D，其中每個(gè)事務(wù)（Transaction）T是I的非空子集，即每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID（Transaction ID）對(duì)應(yīng)。關(guān)聯(lián)規(guī)則在D中的支持度（support）是D 中事務(wù)同時(shí)包含X、Y的百分比，也稱概率；置信度（confidence）是D 中事務(wù)已經(jīng)包含X的情況下包含Y的百分比，也稱條件概率。如果滿足最小支持度閾值和最小置信度閾值，則認(rèn)為關(guān)聯(lián)規(guī)則是有趣的。這些閾值是根據(jù)挖掘需要人為設(shè)定[1]。

一個(gè)簡單的關(guān)聯(lián)規(guī)則實(shí)例：表1 是客戶購買記錄的數(shù)據(jù)庫D，包括6 筆交易。項(xiàng)集I={網(wǎng)球拍、網(wǎng)球、運(yùn)動(dòng)鞋、羽毛球}?？紤]關(guān)聯(lián)規(guī)則（頻繁二項(xiàng)集）：網(wǎng)球拍與網(wǎng)球，事務(wù)1、2、3、4、6 包含網(wǎng)球拍，事務(wù)1、2、6 同時(shí)包含網(wǎng)球拍和網(wǎng)球，X^Y=3，D=6，支持度（X^Y）/D=0.5；X=5，置信度（X^Y）/X=0.6。若給定最小支持度α=0.5，最小置信度β=0.6，則可認(rèn)為購買網(wǎng)球拍和購買網(wǎng)球之間存在關(guān)聯(lián)。

表1 關(guān)聯(lián)規(guī)則實(shí)例

關(guān)聯(lián)規(guī)則挖掘最早由Agrawal 等人提出。當(dāng)時(shí)初衷是為了在事務(wù)數(shù)據(jù)庫中找到各種產(chǎn)品的關(guān)聯(lián)規(guī)則，從而分析客戶的購買行為，指導(dǎo)商家科學(xué)安排進(jìn)貨、庫存以及貨架設(shè)計(jì)等。目前的研究主要集中在提高挖掘規(guī)則算法的效率、適應(yīng)性、可用性以及應(yīng)用推廣等方面，如多循環(huán)方式挖掘算法（層次挖掘算法）、增量式更新算法、分布、并行式挖掘算法、多層關(guān)聯(lián)規(guī)則的挖掘算法、多值關(guān)聯(lián)規(guī)則的挖掘算法、基于概念格的關(guān)聯(lián)規(guī)則挖掘算法等。

2 算法的原理與優(yōu)缺點(diǎn)

Apriori 算法是第一個(gè)關(guān)聯(lián)規(guī)則挖掘算法，也是最經(jīng)典的算法[2]。它通過頻繁項(xiàng)集挖掘關(guān)聯(lián)規(guī)則，不僅可以發(fā)現(xiàn)頻繁項(xiàng)集，還可以挖掘項(xiàng)之間的關(guān)聯(lián)規(guī)則。Apriori 算法使用支持度和置信度分別量化頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則，其核心思想是通過候選集生成和向下封閉檢驗(yàn)檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集[3]。

2.1 Apriori 算法原理

Apriori 算法采用逐層搜索的迭代方法，屬于一維、單層分類，圖1 是Apiori 算法示例?；静襟E是：首先找出數(shù)據(jù)庫中項(xiàng)集之間的關(guān)系，形成規(guī)則，其過程主要包括連接（類矩陣運(yùn)算）和剪枝（去掉那些沒必要的中間結(jié)果）兩個(gè)步驟。

所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻集[4]。具體來說：先找到一個(gè)頻繁項(xiàng)集L1，然后用L1找到兩個(gè)頻繁項(xiàng)集L2，再用L2找到L3，直到找不到k個(gè)頻繁項(xiàng)集為止。當(dāng)出現(xiàn)這種情況時(shí)，需要通過數(shù)據(jù)庫掃描找到每個(gè)LK。

2.2 Apriori 算法的優(yōu)缺點(diǎn)

Apriori 算法的優(yōu)點(diǎn)是：（1）簡單易于理解與實(shí)現(xiàn)，因此應(yīng)用很廣泛；（2）它的關(guān)聯(lián)規(guī)則是基于頻繁項(xiàng)集生成的，可以保證這些規(guī)則的支持度達(dá)到規(guī)定的水平，具有普遍性和說服力。

但它存在難以克服的缺點(diǎn)：（1）對(duì)數(shù)據(jù)庫的掃描次數(shù)過多；（2）會(huì)產(chǎn)生大量的中間項(xiàng)集；（3）采用唯一支持度；（4）算法的適應(yīng)面窄等[5]。其中最大缺點(diǎn)是每次計(jì)算項(xiàng)集支持度時(shí)，對(duì)數(shù)據(jù)庫中的所有數(shù)據(jù)進(jìn)行掃描和比較，I/O負(fù)載很大，尤其面對(duì)大型數(shù)據(jù)庫時(shí)其效率堪憂[6]。

3 改進(jìn)方法

目前關(guān)于Apriori 算法的優(yōu)化方法有很多，比如動(dòng)態(tài)項(xiàng)集計(jì)數(shù)[7]。動(dòng)態(tài)計(jì)數(shù)就是在不同的項(xiàng)目集中添加候選點(diǎn)，如果候選項(xiàng)集滿足最低支持度，則可以直接將其添加到頻繁項(xiàng)集，而無需進(jìn)一步掃描、比較和計(jì)算。

具體做法如下。

（1）簡單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)目出現(xiàn)的頻率，找到大于等于最小支持度的項(xiàng)集，并生成一維頻繁項(xiàng)集Lt。

（2）循環(huán)，直到不再生成更高維度的頻繁項(xiàng)集為止。比如，在步驟k中，根據(jù)在步驟k-1 中生成的k-1 維頻繁項(xiàng)集生成k維候選項(xiàng)集。

（3）Apriori 算法用于檢查新k維頻繁項(xiàng)集的所有k-1 維項(xiàng)集是否已包含在計(jì)算出的k-1 維頻繁項(xiàng)集中，并刪除未包含的組合，以獲得真正的k維頻繁項(xiàng)集。

（4）掃描數(shù)據(jù)庫D的每個(gè)事務(wù)TID。若它至少包含一個(gè)候選項(xiàng)集CK，則保留。否則，將事務(wù)記錄與數(shù)據(jù)庫末尾沒有刪除標(biāo)記的事務(wù)記錄交換，并將其標(biāo)記為刪除[8]。

掃描完整個(gè)數(shù)據(jù)庫后，它將成為一個(gè)新的事務(wù)數(shù)據(jù)庫D’，具體過程見圖2 和圖3。

改進(jìn)算法與Apriori算法基本相似，但又有不同之處[9]，主要為：（1）對(duì)參與組合的元素進(jìn)行計(jì)數(shù)，根據(jù)結(jié)果排除不符合條件的元素，減少組合的可能性，進(jìn)而減少循環(huán)判斷的次數(shù)；（2）數(shù)據(jù)庫掃描后的再生，新數(shù)據(jù)庫的掃描次數(shù)隨著循環(huán)次數(shù)的增加而逐漸減少。

4 實(shí)驗(yàn)結(jié)果驗(yàn)證及分析

通過某職業(yè)技術(shù)學(xué)院19 級(jí)計(jì)算機(jī)系學(xué)生的《數(shù)據(jù)庫原理》課程中的學(xué)生學(xué)習(xí)行為記錄庫，提取章節(jié)與章節(jié)之間可能相關(guān)性，進(jìn)而得出知識(shí)點(diǎn)和測(cè)試成績之間的函數(shù)關(guān)系，最后利用關(guān)聯(lián)規(guī)則挖掘算法發(fā)現(xiàn)學(xué)生所學(xué)課程知識(shí)點(diǎn)與測(cè)試成績之間的關(guān)系，具體關(guān)聯(lián)規(guī)則生成見圖4。

主要流程如下。

Step 1 對(duì)學(xué)生的學(xué)習(xí)行為數(shù)據(jù)進(jìn)行清理，生成結(jié)果放到學(xué)習(xí)成果數(shù)據(jù)庫中。

Step 2 從學(xué)習(xí)成果數(shù)據(jù)庫中提取數(shù)據(jù)挖掘?qū)ο?，進(jìn)行編碼，并將關(guān)系表轉(zhuǎn)化為事務(wù)數(shù)據(jù)庫。

Step 3 在事務(wù)數(shù)據(jù)庫中，根據(jù)給定的最小支持度生成頻繁項(xiàng)集，再結(jié)合給定的最小置信度生成關(guān)聯(lián)規(guī)則。

4.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)挖掘主要根據(jù)學(xué)習(xí)記錄數(shù)據(jù)庫中的代碼表（表2）和簡化關(guān)系表（表3）中提供的對(duì)象，含有學(xué)生人數(shù)、學(xué)習(xí)時(shí)間、課程內(nèi)容、考試結(jié)果、學(xué)習(xí)方法等數(shù)據(jù)。

表2 代碼表

表3 關(guān)系表

4.2 事務(wù)數(shù)據(jù)庫的生成

將關(guān)系表轉(zhuǎn)換為相應(yīng)的事務(wù)數(shù)據(jù)庫并編寫代碼。例如，選擇一部分學(xué)生的《數(shù)據(jù)庫原理》作為事務(wù)數(shù)據(jù)庫（表4），通過代碼表將成績優(yōu)異的章節(jié)轉(zhuǎn)換成相應(yīng)的項(xiàng)目。

表4 事務(wù)數(shù)據(jù)庫D

4.3 頻繁項(xiàng)集的生成

生成事務(wù)數(shù)據(jù)庫D后，|D|=9，K={K01，K02，K03，K04，K05，K06，K07，K08，K09}。假設(shè)給定的最小支持度為0.25，利用Apriori 算法求D 的所有頻繁項(xiàng)集，具體步驟見表5。

表5 頻繁項(xiàng)集生成過程

4.4 關(guān)聯(lián)規(guī)則的生成

生成頻繁項(xiàng)集后，對(duì)于任意K個(gè)頻繁項(xiàng)集，找出所有可能的真子集，并計(jì)算相應(yīng)規(guī)則的置信度。當(dāng)大于給定的最小置信度時(shí)，則輸出規(guī)則，直到最終連接到k-1項(xiàng)的子集。從上一節(jié)中的頻繁項(xiàng)集中選擇的一些關(guān)聯(lián)規(guī)則見表6。

表6 事務(wù)數(shù)據(jù)庫生成的關(guān)聯(lián)規(guī)則

當(dāng)最小置信閾值設(shè)置為0.75時(shí)，規(guī)則為 K01∧K08→K03。具體來說在學(xué)習(xí)《數(shù)據(jù)庫原理》課程時(shí)，如果學(xué)生在“緒論”和“數(shù)據(jù)庫編程”章節(jié)中取得好成績，“關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL”章節(jié)的成績也會(huì)更好，所以在個(gè)性化學(xué)習(xí)系統(tǒng)中就可以考慮將“數(shù)據(jù)庫編程”放在“關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL”之前，或者當(dāng)學(xué)生在選擇學(xué)習(xí)“關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL”時(shí)，個(gè)性化學(xué)習(xí)系統(tǒng)會(huì)建議學(xué)生先復(fù)習(xí)鞏固“緒論”和“數(shù)據(jù)庫編程”這兩章內(nèi)容。比如具有“學(xué)術(shù)型”學(xué)習(xí)風(fēng)格的學(xué)生在學(xué)習(xí)“關(guān)系數(shù)據(jù)理論”這一章節(jié)時(shí)，更多使用理論文本材料進(jìn)行學(xué)習(xí)，絕大多數(shù)的學(xué)生學(xué)習(xí)成績優(yōu)秀。相反具有“操作型”學(xué)習(xí)風(fēng)格的學(xué)生在學(xué)習(xí)“關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL”這一章節(jié)時(shí)，更多使用視頻動(dòng)畫進(jìn)行實(shí)踐學(xué)習(xí)，大多數(shù)的學(xué)生學(xué)習(xí)成績也優(yōu)秀。因此，當(dāng)“學(xué)術(shù)型”學(xué)習(xí)風(fēng)格的學(xué)生選擇學(xué)習(xí)內(nèi)容時(shí)，個(gè)性化學(xué)習(xí)系統(tǒng)將優(yōu)先為學(xué)生推薦呈現(xiàn)理論文本為主的學(xué)習(xí)材料。當(dāng)“操作型”學(xué)習(xí)風(fēng)格的學(xué)生選擇學(xué)習(xí)內(nèi)容時(shí)，系統(tǒng)將優(yōu)先為學(xué)生呈現(xiàn)視頻動(dòng)畫為主的學(xué)習(xí)材料。

因此，關(guān)聯(lián)規(guī)則分析不僅可以挖掘隱藏在課程內(nèi)容之間相互的關(guān)系，還可以發(fā)現(xiàn)不同學(xué)習(xí)風(fēng)格的學(xué)生使用哪些學(xué)習(xí)策略能更有效地學(xué)習(xí)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的Apriori 算法大大提高了運(yùn)算效率，挖掘出的規(guī)則也能有效地輔助教師進(jìn)行學(xué)習(xí)監(jiān)督和指導(dǎo)。

5 結(jié)語

隨著人工智能技術(shù)在信息化領(lǐng)域的不斷深入，學(xué)習(xí)過程中數(shù)據(jù)源的大量涌現(xiàn)，關(guān)聯(lián)規(guī)則作為一種常見的無監(jiān)督學(xué)習(xí)方法，在個(gè)性化學(xué)習(xí)系統(tǒng)中有著廣闊的應(yīng)用前景。本文從經(jīng)典的Apriori 算法出發(fā)，探索并發(fā)現(xiàn)了一種更高效、穩(wěn)定的關(guān)聯(lián)規(guī)則分析方法，該方法在個(gè)性化化學(xué)學(xué)習(xí)系統(tǒng)中進(jìn)行了充分的實(shí)踐，取得了一定的應(yīng)用效果，為后續(xù)研究積累了相關(guān)經(jīng)驗(yàn)。