蔣茜茜, 楊風(fēng)暴, 楊童瑤, 張錦榮

(中北大學(xué) 信息與通信工程學(xué)院, 太原 030051)

信息社會(huì)產(chǎn)生的大量數(shù)據(jù)急需強(qiáng)有力的數(shù)據(jù)分析工具, 將數(shù)據(jù)轉(zhuǎn)換成有用的信息、知識(shí), 因此, 數(shù)據(jù)挖掘技術(shù)[1]應(yīng)運(yùn)而生. 高校體測(cè)數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘能直接反映項(xiàng)目集中數(shù)據(jù)的潛在關(guān)聯(lián), 對(duì)幫助學(xué)生提高體能素質(zhì)具有重要的意義.

張崇林等[2]通過體質(zhì)測(cè)試數(shù)據(jù)處理方法分析, 認(rèn)為體質(zhì)測(cè)試數(shù)據(jù)適合進(jìn)行關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘, 并且通過關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘, 發(fā)現(xiàn)了原知識(shí)體系利用BMI 和體脂率評(píng)價(jià)肥胖的矛盾現(xiàn)象, 可知Apriori 算法利用逐層迭代搜索的方法挖掘數(shù)據(jù)間的關(guān)聯(lián)關(guān)系, 是目前關(guān)聯(lián)規(guī)則應(yīng)用最廣、最經(jīng)典的算法. 趙常紅等[3]運(yùn)用關(guān)聯(lián)規(guī)則的Apriori 算法并設(shè)置支持度、置信度, 分析男、女生的不同體測(cè)數(shù)據(jù), 各測(cè)試指標(biāo)等級(jí)數(shù)量分布情況及其之間的關(guān)聯(lián)性, 但是忽略了算法的運(yùn)行效率. 劉辛等[4]提出一種基于數(shù)組的Apriori 算法, 減少了候選頻繁集冗余, 提高了Apriori 算法效率, 找出了各體測(cè)項(xiàng)目間的關(guān)聯(lián)關(guān)系, 但是忽略了遍歷數(shù)據(jù)庫(kù)的次數(shù)對(duì)運(yùn)行效率的影響. 崔亮等[5]提出一種基于動(dòng)態(tài)散列和事務(wù)壓縮的關(guān)聯(lián)規(guī)則挖掘算法, 通過估計(jì)產(chǎn)生候選項(xiàng)集的大小來(lái)動(dòng)態(tài)選擇是否使用hash 技術(shù), 并且利用事物壓縮技術(shù)刪除不包含頻繁項(xiàng)集的事務(wù), 從而提高算法運(yùn)行效率.

由上述文獻(xiàn)可知關(guān)聯(lián)規(guī)則Apriori 算法可應(yīng)用于高校體測(cè)數(shù)據(jù)場(chǎng)景, 其弊端在于數(shù)據(jù)量增加到一定程度時(shí)算法效率低下[6]. 與崔亮等[5]提出的方法不同, 本文提出的基于事務(wù)壓縮和hash 技術(shù)的改進(jìn)Apriori 算法, 無(wú)需估計(jì)產(chǎn)生候選項(xiàng)集的大小, 是根據(jù)體測(cè)數(shù)據(jù)特征有限并且長(zhǎng)度一致的特點(diǎn), 先使用散列技術(shù)壓縮要考察的候選項(xiàng)集, 再結(jié)合事務(wù)壓縮技術(shù)減少遍歷數(shù)據(jù)集的事務(wù)項(xiàng)數(shù)和長(zhǎng)度, 將這兩種算法優(yōu)勢(shì)完美結(jié)合, 從而大大提高算法的運(yùn)行效率, 并且有效得到體測(cè)數(shù)據(jù)間的關(guān)聯(lián), 能較好地預(yù)測(cè)影響學(xué)生體能素質(zhì)的因素, 從而輔助指導(dǎo)學(xué)生的體能訓(xùn)練.

1 基于事物壓縮和hash 技術(shù)的Apriori 關(guān)聯(lián)規(guī)則算法

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)事務(wù)特征屬性間的規(guī)律, 通過某些屬性來(lái)預(yù)測(cè)其他屬性的關(guān)聯(lián). 在體測(cè)數(shù)據(jù)中, 設(shè)項(xiàng)集itemset={item_1,item_2, …,item_n}是高校學(xué)生體測(cè)數(shù)據(jù)特征屬性的集合,n是屬性的個(gè)數(shù)[7]. 一條學(xué)生體測(cè)數(shù)據(jù)是一個(gè)事務(wù)T, 一個(gè)事務(wù)T是一個(gè)項(xiàng)集, 每個(gè)事務(wù)均與一個(gè)唯一標(biāo)識(shí)符Tid相聯(lián)系, 體測(cè)數(shù)據(jù)中學(xué)籍號(hào)是唯一的標(biāo)識(shí)符Tid[8]. 不同學(xué)生的體測(cè)數(shù)據(jù)組成了事務(wù)集D, 它構(gòu)成了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的事務(wù)數(shù)據(jù)庫(kù).

用支持度和置信度衡量關(guān)聯(lián)規(guī)則的標(biāo)準(zhǔn), 例如形如A?B的關(guān)聯(lián)規(guī)則, 體測(cè)數(shù)據(jù)屬性項(xiàng)A與屬性項(xiàng)B同時(shí)存在的概率即為該數(shù)據(jù)關(guān)聯(lián)規(guī)則的支持度Support(A?B); 體測(cè)數(shù)據(jù)屬性A存在的條件下, 屬性B也存在的概率即為體測(cè)數(shù)據(jù)關(guān)聯(lián)規(guī)則的置信度Confidence(A?B), 其分別如式(1)和式(2)表示.

1.1 Apriori 算法

Apriori 算法是利用k-項(xiàng)集來(lái)產(chǎn)生(k+1)-項(xiàng)集迭代的方法[9], 其操作流程如圖1, 設(shè)定最小支持度min_sup和最小置信度min_conf, 掃描整個(gè)數(shù)據(jù)庫(kù), 統(tǒng)計(jì)長(zhǎng)度為1 的每一項(xiàng)的個(gè)數(shù), 篩選滿足最小支持度的項(xiàng), 得到頻繁1-項(xiàng)集L1; 由L1自身連接生成候選2-項(xiàng)集C2, 得到的C2進(jìn)行剪枝操作, 統(tǒng)計(jì)長(zhǎng)度為2 的每一項(xiàng)的個(gè)數(shù),刪除不滿足最小支持度的項(xiàng), 得到頻繁2-項(xiàng)集L2, 如此迭代下去, 直到不能再找到頻繁k-項(xiàng)集[10], 最終得到頻繁項(xiàng)集L={L1,L2, …,Lk}.

圖1 經(jīng)典Apriori 算法流程

Apriori 算法的弊端在于數(shù)據(jù)量增加到一定程度時(shí)算法效率低下, 具體表現(xiàn)在以下3 個(gè)方面:

1)在Lk-1與自身連接生成Ck過程中, 可能需要產(chǎn)生大量候選項(xiàng)集. 例如, 假設(shè)Lk-1中有m個(gè)k-項(xiàng)集,則在進(jìn)行自身連接需要進(jìn)行比較的時(shí)間復(fù)雜度為O(k×m2).

2) 在對(duì)Ck剪枝的過程中, 判斷Ck中任意一個(gè)k項(xiàng)候選集的(k-1)-項(xiàng)候子集是否為L(zhǎng)k-1的子集, 最快只需要掃描一次得出結(jié)果, 最慢需要k-1 次, 所以平均時(shí)間為|Ck|×|Lk-1|×k/2.

3)在篩選滿足最小支持度的候選項(xiàng)集過程中, 對(duì)Ck中的每個(gè)項(xiàng)進(jìn)行計(jì)數(shù), 需要掃描數(shù)據(jù)庫(kù)|Ck|次.

1.2 基于散列技術(shù)的Apriori 算法

散列技術(shù)又名hash 技術(shù)[11], 基于散列技術(shù)的Apriori算法的優(yōu)勢(shì)主要體現(xiàn)在能將生成的Ck進(jìn)行壓縮, 大大縮小了Ck占用空間. 首先, 掃描數(shù)據(jù)庫(kù)所有的事務(wù)得到C1, 篩選滿足最小支持度的候選項(xiàng)集得到L1; 然后利用散列技術(shù)來(lái)改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法, 具體如下: 將每條事務(wù)生成其所有的2-項(xiàng)集并且運(yùn)用散列技術(shù)構(gòu)造散列函數(shù)把它散列到相應(yīng)的散列表中, 即分配到不同的桶中并計(jì)數(shù), 而且相同的數(shù)據(jù)項(xiàng)被分配到同一存儲(chǔ)空間, 且對(duì)應(yīng)著同一計(jì)數(shù)器, 只需計(jì)數(shù)加一即可,且降低了所需的存儲(chǔ)空間. 同樣的生成頻繁k-項(xiàng)集也是用相同的方法, 并且在散列表中可以篩選出容器計(jì)數(shù)小于支持度閾值的k-項(xiàng)集, 因此可以很好的對(duì)要檢測(cè)的k-項(xiàng)集執(zhí)行壓縮操作.

散列技術(shù)的缺點(diǎn)是其運(yùn)行效率依賴于事務(wù)的平均長(zhǎng)度, 也就是說(shuō)如果數(shù)據(jù)集的特征少, 平均長(zhǎng)度短, 其運(yùn)行效率就高, 反之運(yùn)行效果差. 而Apriori 方法運(yùn)行效率不依賴于數(shù)據(jù)集特征的長(zhǎng)度和數(shù)量, 所以一定程度上彌補(bǔ)hash 技術(shù)的缺點(diǎn), 兩者互補(bǔ)可以大大增加算法的運(yùn)行效率.

1.3 基于事務(wù)壓縮技術(shù)的Apriori 算法

基于事務(wù)壓縮技術(shù)的Apriori 算法的優(yōu)勢(shì)主要體現(xiàn)在將進(jìn)一步迭代掃描的數(shù)據(jù)庫(kù)進(jìn)行壓縮, 進(jìn)而影響掃描事務(wù)庫(kù)的次數(shù), 增加算法的運(yùn)行效率[12]. 該技術(shù)的改進(jìn)是根據(jù)經(jīng)典Apriori 算法的性質(zhì), 即如果一個(gè)事務(wù)不包含任何的頻繁k-項(xiàng)集, 則其也不包含任何的頻繁(k+1)-項(xiàng)集. 因此在生成Lj(j＞k)時(shí), 遇到上述事務(wù)時(shí),可以加上標(biāo)記或刪除, 掃描數(shù)據(jù)庫(kù)時(shí)不需要再掃描該事務(wù), 減少掃描事務(wù)庫(kù)的次數(shù).

1.4 基于散列技術(shù)和事務(wù)壓縮相結(jié)合的改進(jìn)

根據(jù)以上了解可知, 基于散列技術(shù)的改進(jìn)和基于事務(wù)壓縮技術(shù)作用于Apriori 算法過程中的不同部分,基于散列技術(shù)的改進(jìn)體現(xiàn)在減少候選項(xiàng)集的規(guī)模, 并更進(jìn)一步減少數(shù)據(jù)庫(kù)掃描的次數(shù), 而事務(wù)壓縮技術(shù)能夠逐漸減小數(shù)據(jù)庫(kù)中事務(wù)的長(zhǎng)度和規(guī)模, 都主要作用在Apriori 算法的剪枝部分[13], 并且兩者會(huì)促進(jìn)對(duì)方的效果, 而不產(chǎn)生負(fù)面影響.

改進(jìn)算法流程如算法1 所示, 根據(jù)高校體測(cè)數(shù)據(jù)的特征有限和并且長(zhǎng)度一致的特點(diǎn), 利用散列技術(shù)遍歷一次事務(wù)集, 即可生成頻繁項(xiàng)集L1,L2,L3, 再利用事務(wù)壓縮技術(shù)由L3生成L4, 如此迭代下去, 直到不能再找到頻繁k-項(xiàng)集. 因?yàn)榈珊蜻x項(xiàng)時(shí)可能性太多,數(shù)據(jù)量大時(shí)占用內(nèi)存太大, 所以不繼續(xù)使用hash 技術(shù)繼續(xù)生成L4, 而改用事務(wù)壓縮技術(shù), 有效地避免hash技術(shù)的短板.

算法1. 改進(jìn)Apriori 算法輸入: 數(shù)據(jù)庫(kù)D, 最小支持度min_sup, 最小置信度min_conf過程:1)掃描數(shù)據(jù)庫(kù), 利用散列技術(shù)生成頻繁1-項(xiàng)集L1, 頻繁2-項(xiàng)集L2, 頻繁3-項(xiàng)集L3;2)通過頻繁項(xiàng)集Lk-1 自身連接生成Ck 候選項(xiàng)集, 再進(jìn)行剪枝;3)利用事務(wù)壓縮技術(shù)減少掃描事務(wù)集的次數(shù), 刪除不滿足最小支持度的項(xiàng)集, 生成頻繁k-項(xiàng)集Lk;4)對(duì)k＞3, 重復(fù)執(zhí)行步驟2)和3), 判斷頻繁k-項(xiàng)集的長(zhǎng)度, 如果為0,則跳出循環(huán), 得到最終結(jié)果頻繁項(xiàng)集L, 否則返回步驟2);5)篩選出滿足min_sup 和min_conf 的頻繁項(xiàng)集即強(qiáng)關(guān)聯(lián)規(guī)則, 結(jié)束.輸出: 強(qiáng)關(guān)聯(lián)規(guī)則

2 實(shí)驗(yàn)過程及分析

2.1 數(shù)據(jù)準(zhǔn)備

以我校2016 級(jí)7 709 名大學(xué)生第一學(xué)年的體測(cè)成績(jī)?yōu)閷?shí)驗(yàn)對(duì)象, 從數(shù)據(jù)庫(kù)中提取與體測(cè)成績(jī)有關(guān)的數(shù)據(jù), 如: 學(xué)籍號(hào)、性別、身高、體重、肺活量、50 m、立定跳遠(yuǎn)、1 000 m (男生)、800 m (女生)、引體向上(男生)、仰臥起坐(女生)共11 個(gè)屬性, 表1 是以學(xué)籍號(hào)為主鍵的體測(cè)成績(jī).

表1 學(xué)生2016 年的體測(cè)成績(jī)

2.2 數(shù)據(jù)清洗及轉(zhuǎn)換

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于我校體測(cè)中心, 所以得到的數(shù)據(jù)較為規(guī)范, 但是數(shù)據(jù)中存在部分學(xué)生體測(cè)成績(jī)?nèi)表?xiàng), 又考慮到部分特殊學(xué)生免測(cè)的情況, 所以要對(duì)原始數(shù)據(jù)先進(jìn)行預(yù)處理, 經(jīng)過數(shù)據(jù)清洗、數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)消減,實(shí)現(xiàn)算法在高校學(xué)生體測(cè)中的應(yīng)用.

數(shù)據(jù)清洗的實(shí)際操作主要有:

(1)針對(duì)缺項(xiàng)數(shù)據(jù), 如果缺項(xiàng)數(shù)據(jù)較多則刪除該學(xué)生的體測(cè)成績(jī)[12]; 如果缺項(xiàng)較少, 則可以通過求該項(xiàng)目成績(jī)的平均值、眾數(shù)或者中位數(shù)填充;

(2)針對(duì)免考學(xué)生的數(shù)據(jù), 由于各項(xiàng)成績(jī)?yōu)槿表?xiàng),可以直接刪除, 使得清洗后的數(shù)據(jù)標(biāo)準(zhǔn)、干凈且連續(xù).

數(shù)據(jù)轉(zhuǎn)換將不同標(biāo)準(zhǔn)的連續(xù)型數(shù)據(jù)轉(zhuǎn)換成標(biāo)準(zhǔn)相同的離散型數(shù)據(jù), 便于后續(xù)的統(tǒng)一處理. 雖然體測(cè)項(xiàng)目間的評(píng)判標(biāo)準(zhǔn)不同, 但是都可以劃分為A、B、C、D 四個(gè)等級(jí), 即優(yōu)秀、良好、及格、不及格, 其次, 為了方便統(tǒng)計(jì)以及提高數(shù)據(jù)挖掘的效率, 用數(shù)字1 和2分別代替性別的男和女, 用小寫字母開頭代替各項(xiàng)目的名稱, 如: 肺活量用fhl 代替.

數(shù)據(jù)轉(zhuǎn)換結(jié)果如表2 所示, 經(jīng)過數(shù)據(jù)清洗及轉(zhuǎn)換得到的標(biāo)準(zhǔn)數(shù)據(jù)最終有7 337 條.

表2 數(shù)據(jù)轉(zhuǎn)換結(jié)果

2.3 數(shù)據(jù)消減

數(shù)據(jù)消減是在保持?jǐn)?shù)據(jù)庫(kù)的完整性的情況下, 從上述數(shù)據(jù)集中獲得精簡(jiǎn)的數(shù)據(jù)集, 能夠保證不影響最終的算法結(jié)果. 男生和女生體測(cè)項(xiàng)目和評(píng)價(jià)標(biāo)準(zhǔn)有所不同, 所以本文將在數(shù)據(jù)挖掘時(shí)對(duì)男生和女生的體測(cè)成績(jī)數(shù)據(jù)分別進(jìn)行處理. 數(shù)據(jù)消減就是針對(duì)數(shù)據(jù)庫(kù)中篩選出的男生、女生的體測(cè)數(shù)據(jù), 消除與體測(cè)項(xiàng)目屬性無(wú)關(guān)的項(xiàng), 例如學(xué)籍號(hào), 性別.

2.4 實(shí)驗(yàn)驗(yàn)證

試驗(yàn)環(huán)境為Intel(R) Core(TM) i5-5200U 2.20 GHz處理器, 4 GB 內(nèi)存, 操作系統(tǒng)為Windows 10, 算法在Python 3.8 下實(shí)現(xiàn).

設(shè)定min_conf= 0.9, 設(shè)置不同的最小支持度, 利用Apriori 算法以及本文提出的事務(wù)壓縮和hash 結(jié)合的算法得到的結(jié)果如表3 所示, 在相同的最小支持度下得到的關(guān)聯(lián)規(guī)則數(shù)目相同, 表示改進(jìn)后的算法確保了Apriori 算法的準(zhǔn)確性, 由此可以得到改進(jìn)算法的可靠性; 隨著最小支持度的增加, 改進(jìn)后的算法執(zhí)行效率大大提高. 改進(jìn)后的算法在保證挖掘精度的同時(shí)提高算法效率.

表3 兩種算法比較

為了能直觀地反映出改進(jìn)后的算法運(yùn)行效率更高,在設(shè)置不同最小置信度、最小支持度情況下, 將得出的實(shí)現(xiàn)數(shù)據(jù)進(jìn)行分析對(duì)比, 結(jié)果如圖2 和圖3 所示. 圖中結(jié)果可知, 本文提出的改進(jìn)算法效率明顯優(yōu)于經(jīng)典Apriori 算法、基于hash 的Apriori 算法以及基于事物壓縮的Apriori 算法. Apriori 算法和基于事物壓縮的Apriori 算法隨著支持度和置信度的增加執(zhí)行效率比較接近, 其中基于事物壓縮的Apriori 算法效率稍高; 基于hash 改進(jìn)算法相較于Apriori 算法和基于事物壓縮的Apriori 算法本身具有一定的優(yōu)越性, 本文將hash技術(shù)與事務(wù)壓縮技術(shù)相結(jié)合得到了更好的效果.

圖2 不同支持度性能對(duì)比

圖3 不同置信度性能對(duì)比

2.5 結(jié)果分析

原始的體測(cè)數(shù)據(jù)經(jīng)過數(shù)據(jù)預(yù)處理后得到2 266 條女生體測(cè)數(shù)據(jù)和5 071 條男生體測(cè)數(shù)據(jù), 設(shè)置最小置信度min_conf= 0.9, 最小支持度min_sup= 0.3, 將這兩類數(shù)據(jù)分別用文中提到的4 種算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘,將各運(yùn)行效率進(jìn)行比較, 如表4 所示, 可以看出本文提出的基于事物壓縮和hash 結(jié)合的算法執(zhí)行效率更高,與經(jīng)典Apriori 算法執(zhí)行效率相比, 女生體測(cè)數(shù)據(jù)算法執(zhí)行效率提高了86.12%, 男生提高了90.63%; 與基于事物壓縮的Apriori 算法相比, 女生體測(cè)數(shù)據(jù)算法執(zhí)行效率提高了80.57%, 男生提高了89.32%; 與基于hash 的Apriori 算法相比, 女生體測(cè)數(shù)據(jù)算法執(zhí)行效率提高了48.1%, 男生提高了55.69%; 可見, 該4 種算法應(yīng)用于男生的體測(cè)數(shù)據(jù)的執(zhí)行效率比女生更高, 說(shuō)明數(shù)據(jù)集量越大改善效果越明顯.

表4 4 種算法執(zhí)行效率比較 (s)

表5 和表6 分別是男生和女生體測(cè)成績(jī)的關(guān)聯(lián)規(guī)則挖掘結(jié)果, 由表5 可以看出挖掘出的男生第一條關(guān)聯(lián)規(guī)則50 m:C ?ytxs:D, 支持度為72.1%, 置信度為93.5%, 說(shuō)明男生50 m 成績(jī)?nèi)绻荂 等級(jí), 那么他的引體向上的成績(jī)?yōu)镈 等級(jí)的可能性為93.5%, 而這種事件發(fā)生的可能性為72.1%, 可知此學(xué)生的50 m 成績(jī)可以預(yù)測(cè)其引體向上的成績(jī), 以此類推. 可通過某學(xué)生的歷史數(shù)據(jù)來(lái)預(yù)測(cè)其他成績(jī)的及格情況, 達(dá)到預(yù)警的效果, 使該學(xué)生加強(qiáng)某方面的鍛煉, 進(jìn)行有針對(duì)性的體能訓(xùn)練, 幫助老師安排訓(xùn)練計(jì)劃有著指導(dǎo)性的意義.

表5 關(guān)聯(lián)規(guī)則 (男生)

表6 關(guān)聯(lián)規(guī)則 (女生)

3 結(jié)論與展望

現(xiàn)在數(shù)據(jù)挖掘技術(shù)已經(jīng)非常成熟, 然而數(shù)據(jù)挖掘和體能分析結(jié)合的應(yīng)用卻很少, 本文通過對(duì)比4 種算法實(shí)現(xiàn)的結(jié)果和執(zhí)行效率, 表明改進(jìn)后的算法在高校學(xué)生體測(cè)中的應(yīng)用具有一定的可靠性和有效性, 對(duì)于比較大的數(shù)據(jù)集效率改善更明顯. 并且將本文所提出的算法, 與經(jīng)典Apriori 算法相比, 可知執(zhí)行效率提高了85%以上, 并且挖掘出體測(cè)成績(jī)間的潛在關(guān)聯(lián), 分析身體素質(zhì)的不足之處, 對(duì)學(xué)生重視體育鍛煉, 輔導(dǎo)老師安排學(xué)生的訓(xùn)練計(jì)劃具有指導(dǎo)性的意義.