李臻

摘 ?要： 傳統(tǒng)Apriori挖掘算法需多次掃描數(shù)據(jù)庫、多次連接頻繁項(xiàng)集，導(dǎo)致挖掘效率較低，為此對(duì)Apriori挖掘算法加以改進(jìn)，設(shè)計(jì)一種新的Apriori挖掘算法用于音樂節(jié)目分類。改進(jìn)的Apriori挖掘算法采用萊特準(zhǔn)則對(duì)音頻數(shù)據(jù)進(jìn)行野值與噪聲平滑處理，改進(jìn)Apriori挖掘算法的音頻數(shù)據(jù)庫映射令兩個(gè)線性表分別負(fù)責(zé)音頻數(shù)據(jù)存儲(chǔ)和對(duì)應(yīng)項(xiàng)存儲(chǔ)，音頻數(shù)據(jù)庫掃描次數(shù)降為一次;改進(jìn)Apriori挖掘算法的連接次數(shù)無需對(duì)不具備交運(yùn)算能力的元素進(jìn)行交運(yùn)算操作，減少頻繁項(xiàng)集連接次數(shù)?；诟倪M(jìn)頻繁項(xiàng)集Apriori挖掘算法挖掘頻繁項(xiàng)集、生成音頻數(shù)據(jù)關(guān)聯(lián)規(guī)則，基于關(guān)聯(lián)規(guī)則集構(gòu)建分類器，實(shí)現(xiàn)音樂節(jié)目分類。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)Apriori挖掘算法用于音樂節(jié)目分類的效率優(yōu)勢突出，準(zhǔn)確度高。

關(guān)鍵詞： 音樂節(jié)目; 節(jié)目分類; Apriori挖掘算法; 分類器構(gòu)建; 頻繁項(xiàng)集; 關(guān)聯(lián)規(guī)則

中圖分類號(hào)： TN911.1?34; TP301.6 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）19?0090?05

Abstract： Traditional Apriori mining algorithm needs to scan database and connect frequent itemsets many times， which results in low mining efficiency. To improve the Apriori mining algorithm， a new Apriori mining algorithm is designed for music program classification. The Wright criterion is used in the improved Apriori mining algorithm to smooth the outliers and noises of audio data， and improves the mapping of the audio database of Apriori mining algorithm， so as to make the two linear tables responsible for the storage of audio data and corresponding items respectively， and the scanning times of the audio database reduced to one time. The improved Apriori mining algorithm does not need to operate the connection times of the elements that do not have the ability of intersection operation. Row intersection operation reduces the number of frequent itemset connections. Based on the improved Apriori mining algorithm of frequent itemsets， frequent itemsets are mined and audio data association rules are generated. A classifier is constructed based on association rules to realize music program classification. The experimental results show that the improved Apriori mining algorithm has prominent efficiency advantages and high accuracy in music program classification.

Keywords： music program; program classification; Apriori mining algorithm; classifier establishment; frequent itemset; association rule

0 ?引 ?言

Apriori算法是一種高效、準(zhǔn)確的數(shù)據(jù)挖掘算法，用于挖掘數(shù)據(jù)庫頻繁項(xiàng)集、生成關(guān)聯(lián)規(guī)則，得到的關(guān)聯(lián)規(guī)則符合置信度與支持度最小原則[1]?；谏傻年P(guān)聯(lián)規(guī)則可完成數(shù)據(jù)挖掘，從海量數(shù)據(jù)中獲取目標(biāo)數(shù)據(jù)?；陉P(guān)聯(lián)規(guī)則集構(gòu)造分類器進(jìn)行數(shù)據(jù)分類已經(jīng)取得良好成效。因此，Apriori挖掘算法在海量數(shù)據(jù)處理方面具有廣泛的應(yīng)用前景，目前涉及醫(yī)療、教育、電子商務(wù)等熱門行業(yè)，實(shí)現(xiàn)經(jīng)濟(jì)效益與社會(huì)效益雙豐收[2]。待挖掘數(shù)據(jù)庫中的海量數(shù)據(jù)往往存在噪聲和缺失部分，為保障挖掘精度和效率，需對(duì)數(shù)據(jù)庫進(jìn)行過濾處理，降低數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘難度[3]。本文設(shè)計(jì)一種應(yīng)用于音樂節(jié)目分類的Apriori挖掘算法，對(duì)傳統(tǒng)Apriori挖掘算法加以改進(jìn)。待挖掘數(shù)據(jù)為音樂節(jié)目的音頻數(shù)據(jù)，首先基于野值處理與噪聲平滑處理方式清理音頻數(shù)據(jù)，其次采用改進(jìn)的Apriori挖掘算法挖掘音頻數(shù)據(jù)間的關(guān)聯(lián)規(guī)則，該關(guān)聯(lián)規(guī)則的支持度與置信度最小。基于改進(jìn)Apriori挖掘算法獲取的關(guān)聯(lián)規(guī)則提取音樂節(jié)目音頻數(shù)據(jù)間的關(guān)聯(lián)關(guān)系，最后實(shí)現(xiàn)音樂節(jié)目分類。

2） 掃描音頻數(shù)據(jù)庫即可獲取全部1?候選項(xiàng)集的音頻標(biāo)識(shí)，繼而掃描[Bk]，[Hk]，生成其余候選集，上述過程只進(jìn)行一次音樂節(jié)目音頻數(shù)據(jù)庫掃描。

1.3.2 ?連接操作改進(jìn)

定義如下情況，[L3={{]1，2，3}，{1，2，4}，{1，2，5}，{1，2，6}，{1，2，7}，{2，3，4}，{2，3，5}，{2，3，6}，{2，3，7}}，此時(shí)支持度最小值已知，求取[H4]數(shù)值。采用Apriori挖掘算法求取時(shí)，生成的[H4]候選集包括16個(gè)候選子集，生成的候選項(xiàng)冗余內(nèi)容占比較大，降低了音頻數(shù)據(jù)挖掘效率、提升了數(shù)據(jù)挖掘難度，若想獲取頻繁項(xiàng)集挖掘的最終結(jié)果需經(jīng)過數(shù)次連接操作。

通過優(yōu)化交運(yùn)算改進(jìn)Apriori挖掘算法中的連接操作，減少連接操作的次數(shù)，節(jié)約數(shù)據(jù)挖掘時(shí)間[9]。采用Apriori挖掘算法挖掘關(guān)聯(lián)規(guī)則過程中，頻繁項(xiàng)集生成候選集時(shí)，在音頻數(shù)據(jù)集生成新音頻數(shù)據(jù)集過程中進(jìn)行交運(yùn)算[10]。候選項(xiàng)集支持度通過音頻數(shù)據(jù)模與音頻數(shù)據(jù)數(shù)量集得到，任意頻繁項(xiàng)集中的[xi]與[xj]不具備交運(yùn)算的能力時(shí)，無需對(duì)[xi]與[xj]之后的元素進(jìn)行交運(yùn)算操作，節(jié)約連接次數(shù)，提升算法效率。

1.3.3 ?分類器構(gòu)建

根據(jù)改進(jìn)Apriori挖掘算法生成高質(zhì)量的音樂節(jié)目分類關(guān)聯(lián)規(guī)則，構(gòu)建音樂節(jié)目分類器。基于改進(jìn)Apriori挖掘算法得到關(guān)聯(lián)規(guī)則集，定義為[S]，[M]表示訓(xùn)練音頻數(shù)據(jù)集。分類器構(gòu)建原理為：查找具備覆蓋數(shù)據(jù)集[E]能力的規(guī)則集命名為[V?S]，查找范圍是[S]，根據(jù)[S]中不同的規(guī)則排序情況選取[L]中的規(guī)則，此時(shí)默認(rèn)類別存在[V]中。由此完成分類器構(gòu)建，實(shí)現(xiàn)音樂節(jié)目高效分類。

2 ?實(shí)驗(yàn)分析

基于本文設(shè)計(jì)的改進(jìn)Apriori挖掘算法進(jìn)行音樂節(jié)目分類實(shí)驗(yàn)，驗(yàn)證本文算法用于音樂節(jié)目分類的優(yōu)越性。實(shí)驗(yàn)采用的音樂節(jié)目音頻數(shù)據(jù)由某權(quán)威數(shù)據(jù)平臺(tái)提供，包括流行、美聲、古典、民族、說唱5個(gè)音樂節(jié)目類別，數(shù)據(jù)總規(guī)模為500 MB，依據(jù)測試實(shí)際情況劃分成不同大小的小規(guī)模音頻數(shù)據(jù)庫，分別命名為數(shù)據(jù)庫A、數(shù)據(jù)庫B、數(shù)據(jù)庫C、數(shù)據(jù)庫D、數(shù)據(jù)庫E。

2.1 ?音頻數(shù)據(jù)規(guī)模與運(yùn)行時(shí)間的關(guān)系

設(shè)定支持度最小值為定值，研究音頻數(shù)據(jù)規(guī)模與運(yùn)行時(shí)間的關(guān)系，當(dāng)本文算法的最小支持度設(shè)定為8%，15%，22%時(shí)，音頻數(shù)據(jù)規(guī)模與運(yùn)行時(shí)長的關(guān)系如圖2所示。

分析圖2能夠看出，音樂節(jié)目音頻數(shù)據(jù)規(guī)模與本文算法挖掘頻繁項(xiàng)集用時(shí)成正比，兩者為同時(shí)增長趨勢。數(shù)據(jù)規(guī)模相等的情況下，最小支持度越小，算法挖掘用時(shí)越長，這是因?yàn)楸疚乃惴ㄗ钚≈С侄仍黾?，而符合條件的支持度值相應(yīng)減少，減少了算法運(yùn)算步驟與用時(shí)，算法挖掘效率有所提升。

由此可知，本文算法挖掘音樂節(jié)目音頻數(shù)據(jù)過程中，挖掘效率受數(shù)據(jù)庫規(guī)模與算法最小值支持度的影響。

2.2 ?支持度最小值與運(yùn)行時(shí)間的關(guān)系

設(shè)置25 MB，50 MB，75 MB三種規(guī)模的音樂節(jié)目音頻數(shù)據(jù)庫，采用本文算法完成音樂節(jié)目分類中的關(guān)聯(lián)規(guī)則挖掘，得到最小支持度與算法挖掘用時(shí)關(guān)系，如圖3所示。

分析圖3能夠看出，音頻數(shù)據(jù)庫規(guī)模為75 MB，50 MB，25 MB時(shí)，算法運(yùn)行最大用時(shí)出現(xiàn)在最小支持度為8%時(shí)，分別為21 s，15.8 s，8.8 s，三種規(guī)模數(shù)據(jù)庫運(yùn)行曲線均為下降趨勢，即隨著算法最小支持度的增加，算法運(yùn)行時(shí)長降低，此現(xiàn)象與2.1小節(jié)結(jié)論一致。圖中數(shù)據(jù)顯示，音頻數(shù)據(jù)庫規(guī)模越大，算法運(yùn)行時(shí)間越長，這是因?yàn)閿?shù)據(jù)庫規(guī)模大，掃描數(shù)據(jù)的用時(shí)較長，導(dǎo)致算法運(yùn)行效率降低。上述實(shí)驗(yàn)結(jié)果表明，改善本文算法挖掘關(guān)聯(lián)規(guī)則效率的方法是減少音樂節(jié)目音頻數(shù)據(jù)庫掃描次數(shù)。

2.3 ?不同挖掘算法用于音樂節(jié)目分類

采用傳統(tǒng)Apriori挖掘算法、IM?Apriori挖掘算法作為對(duì)比算法進(jìn)行測試，測試三種算法在音樂節(jié)目分類中的應(yīng)用情況，記錄三種算法進(jìn)行音樂節(jié)目分類的時(shí)間開銷情況，不同算法時(shí)間開銷如表1所示。

由表1能夠看出三種算法用于音樂節(jié)目分類的效率，其中，本文算法時(shí)間開銷最短，在4.4～6.5 ms之間，傳統(tǒng)Apriori挖掘算法與IM?Apriori挖掘算法時(shí)間開銷分別在14.1～22.3 ms之間，本文算法呈現(xiàn)較優(yōu)的挖掘效率。這是因?yàn)楸疚乃惴ㄔ趥鹘y(tǒng)Apriori挖掘算法基礎(chǔ)上對(duì)音頻數(shù)據(jù)庫映射和連接操作加以改進(jìn)，數(shù)據(jù)庫映射改進(jìn)后包含兩個(gè)線性表，分別負(fù)責(zé)音頻數(shù)據(jù)存儲(chǔ)、對(duì)應(yīng)項(xiàng)存儲(chǔ)，只需進(jìn)行一次音頻數(shù)據(jù)庫掃描，大大節(jié)約了算法挖掘時(shí)間。此外，判斷頻繁項(xiàng)集的交運(yùn)算能力，對(duì)于不具備交運(yùn)算能力[xi]與[xj]之后的元素?zé)o需進(jìn)行交運(yùn)算操作，節(jié)約了連接次數(shù)，提升了本文算法效率。

三種算法進(jìn)行音樂節(jié)目分類結(jié)果如表2所示。

分析表2能夠看出，本文算法進(jìn)行音樂節(jié)目分類誤差較小，低于2.5%，傳統(tǒng)Apriori挖掘算法與IM?Apriori挖掘算法的分類誤差均在5%以上，因此，本文算法精度最高。同時(shí)，三種算法的分類誤差均隨音樂節(jié)目音頻數(shù)據(jù)庫規(guī)模的增加而增加，證明數(shù)據(jù)庫規(guī)模影響算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘的準(zhǔn)確度，影響音樂節(jié)目分類誤差。

3 ?結(jié) ?論

本文對(duì)傳統(tǒng)Apriori挖掘算法進(jìn)行優(yōu)化，設(shè)計(jì)一種新的Apriori挖掘算法用于音樂節(jié)目分類。本文算法改進(jìn)體現(xiàn)在兩個(gè)方面：音頻數(shù)據(jù)庫映射改進(jìn)和連接操作改進(jìn)。一方面，數(shù)據(jù)庫映射改進(jìn)后存在兩個(gè)線性表，分別負(fù)責(zé)音頻數(shù)據(jù)存儲(chǔ)、對(duì)應(yīng)項(xiàng)存儲(chǔ)，掃描數(shù)據(jù)庫次數(shù)由多次變?yōu)橐淮?，提高了算法挖掘效?另一方面，通過判斷頻繁項(xiàng)集的交運(yùn)算能力，終止任意頻繁項(xiàng)集中不具備交運(yùn)算能力的元素進(jìn)行交運(yùn)算操作，減少連接次數(shù)，提升算法效率。本文算法改進(jìn)后，挖掘音頻數(shù)據(jù)關(guān)聯(lián)規(guī)則的效率大大提升，進(jìn)一步提升了音樂節(jié)目分類效率。

參考文獻(xiàn)

[1] 鄭銀環(huán)，王嘉珺，郭威，等.基于特征旋律挖掘的二階馬爾可夫鏈在算法作曲中的研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2018，35（3）：849?853.

ZHENG Yinhuan， WANG Jiajun， GUO Wei， et al. Research and application on second?order Markov chains based on feature melody mining in algorithmic composition [J]. Application research of computers， 2018， 35（3）：849?853.

[2] 李濤，林陳，王麗娜.一種改進(jìn)的相關(guān)項(xiàng)對(duì)挖掘算法研究[J].計(jì)算機(jī)仿真，2016，33（8）：223?228.

LI Tao， LIN Chen， WANG Lina. An improved algorithm research on mining correlation pairs [J]. Computer simulation， 2016， 33（8）： 223?228.

[3] 徐開勇，龔雪容，成茂才.基于改進(jìn)Apriori算法的審計(jì)日志關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)應(yīng)用，2016，36（7）：1847?1851.

XU Kaiyong， GONG Xuerong， CHENG Maocai. Audit log association rule mining based on improved apriori algorithm [J]. Journal of computer applications， 2016， 36（7）： 1847?1851.

[4] 魏玲，魏永江，高長元.基于Bigtable與MapReduce的Apriori算法改進(jìn)[J].計(jì)算機(jī)科學(xué)，2015，42（10）：208?210.

WEI Ling， WEI Yongjiang， GAO Changyuan. Improved apriori algorithm based on Bigtable and MapReduce [J]. Computer science， 2015， 42（10）： 208?210.

[5] 黃文成，賈立，彭道剛，等.基于Apriori的關(guān)聯(lián)規(guī)則算法及其在電廠中的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2018，30（1）：266?271.

HUANG Wencheng， JIA Li， PENG Daogang， et al. Apriori?based association rule algorithm and its application in power plant [J]. Journal of system simulation， 2018， 30（1）： 266?271.

[6] 楊俊瑤，蒙祖強(qiáng)，蔣亮.一種基于拓?fù)湫畔⒌奈锪黝l繁路徑挖掘算法[J].計(jì)算機(jī)科學(xué)，2015，42（4）：258?262.

YANG Junyao， MENG Zuqiang， JIANG Liang. Logistics frequent path sequence mining algorithm based on topological information [J]. Computer science， 2015， 42（4）： 258?262.

[7] 黃俊杰，譚波，陳孝明，等.用Apriori關(guān)聯(lián)規(guī)則挖掘算法發(fā)現(xiàn)湖北電網(wǎng)雷擊災(zāi)害的時(shí)空分布規(guī)律[J].應(yīng)用科學(xué)學(xué)報(bào)，2017，35（1）：31?41.

HUANG Junjie， TAN Bo， CHEN Xiaoming， et al. Spatiotemporal distribution of lightning disasters of power lines in hubei province using data mining based on Apriori association rules[J]. Journal of applied sciences， 2017， 35（1）： 31?41.

[8] 孫學(xué)波，石飛達(dá).基于Hadoop的Apriori算法研究與優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì)，2018，39（1）：126?133.

SUN Xuebo， SHI Feida. Research and optimization of Apriori algorithm based on Hadoop [J]. Computer engineering and design， 2018， 39（1）： 126?133.

[9] 朱付保，白慶春，湯萌萌，等.基于改進(jìn)Apriori算法的鐵路軌道質(zhì)量分析與評(píng)價(jià)[J].微電子學(xué)與計(jì)算機(jī)，2015，32（10）：159?162.

ZHU Fubao， BAI Qingchun， TANG Mengmeng， et al. Quality analysis and evaluation of tracks based on improved Apriori algorithm [J]. Microelectronics & computer， 2015， 32（10）： 159?162.

[10] 趙學(xué)健，孫知信，袁源.基于預(yù)判篩選的高效關(guān)聯(lián)規(guī)則挖掘算法[J].電子與信息學(xué)報(bào)，2016，38（7）：1654?1659.

ZHAO Xuejian， SUN Zhixin， YUAN Yuan. An efficient association rule mining algorithm based on prejudging and screening [J]. Journal of electronics & information technology， 2016， 38（7）： 1654?1659.