應(yīng)用于音樂節(jié)目分類的Apriori挖掘算法設(shè)計

李臻

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

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

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

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

1.3.2 ?連接操作改進

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

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

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

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

2 ?實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3 ?結(jié) ?論

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

參考文獻

[1] 鄭銀環(huán)，王嘉珺，郭威，等.基于特征旋律挖掘的二階馬爾可夫鏈在算法作曲中的研究與應(yīng)用[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] 李濤，林陳，王麗娜.一種改進的相關(guān)項對挖掘算法研究[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] 徐開勇，龔雪容，成茂才.基于改進Apriori算法的審計日志關(guān)聯(lián)規(guī)則挖掘[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].計算機科學，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)仿真學報，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] 楊俊瑤，蒙祖強，蔣亮.一種基于拓撲信息的物流頻繁路徑挖掘算法[J].計算機科學，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)雷擊災害的時空分布規(guī)律[J].應(yīng)用科學學報，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] 孫學波，石飛達.基于Hadoop的Apriori算法研究與優(yōu)化[J].計算機工程與設(shè)計，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] 朱付保，白慶春，湯萌萌，等.基于改進Apriori算法的鐵路軌道質(zhì)量分析與評價[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] 趙學健，孫知信，袁源.基于預判篩選的高效關(guān)聯(lián)規(guī)則挖掘算法[J].電子與信息學報，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.