摘 ?要： 為了提高音樂(lè)分類(lèi)的精準(zhǔn)性及個(gè)性化，提出基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)在音樂(lè)分類(lèi)中的使用，解決單一軌道提取的局限性問(wèn)題。首先，對(duì)音樂(lè)文件預(yù)處理進(jìn)行分析，主要包括提取主旋律、分析和聲;之后，對(duì)基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格進(jìn)行分析。因?yàn)镕P_Growth算法只需要掃描兩遍原始數(shù)據(jù)，對(duì)原始數(shù)據(jù)進(jìn)行壓縮具有較高的效率，所以將FP_Growth關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于音樂(lè)媒體的風(fēng)格分類(lèi)中，并且創(chuàng)建基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的音樂(lè)風(fēng)格分類(lèi)，減少所需頻繁項(xiàng)集的數(shù)量，從而提高數(shù)據(jù)庫(kù)掃描速度，在此過(guò)程中不需要候選項(xiàng)集，實(shí)現(xiàn)音樂(lè)分類(lèi)過(guò)程中的數(shù)據(jù)挖掘;最后，對(duì)數(shù)據(jù)挖掘的效率進(jìn)行Matlab測(cè)試，測(cè)試結(jié)果表示，相比基于LAD和Apriori算法的音樂(lè)風(fēng)格分類(lèi)，基于FP_Growth的音樂(lè)風(fēng)格分類(lèi)減少了I/O開(kāi)銷(xiāo)，提高了運(yùn)行效率和分類(lèi)的精準(zhǔn)性。

關(guān)鍵詞： 音樂(lè)分類(lèi); 數(shù)據(jù)挖掘; 關(guān)聯(lián)規(guī)則算法; 音樂(lè)風(fēng)格分析; 主旋律提取; FP_Growth

中圖分類(lèi)號(hào)： TN911.1?34; TP393 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）01?0099?03

Application of data mining technology based on association rules

in music classification

ZHANG Tingting

Abstract： In order to improve the accuracy and individualization of music classification， the application of data mining technology based on association rules in music classification is proposed to solve the limitation problem of single track extraction. The preprocessing of music files is analyzed， including extraction of the main melody and analysis of harmony. Then， the music style based on FP_Growth association rules mining algorithm is analyzed. Because the FP_Growth algorithm only needs to scan the original data twice， it is more efficient to compress the original data， so the FP_Growth association rule mining algorithm is applied to the style classification of music media， and the music style classification based on FP_Growth association rules mining is created to reduces the number of the needed frequent itemsets， so as to improve the scanning speed of the database. There is no need of candidate itemsets in this process for realization of the data mining in the process of music classification. The efficiency of data mining is tested with Matlab. The test results show that， in comparison with the music style classification based on LAD and Apriori algorithms， the music style classification based on FP_Growth algorithm can reduce the overhead of I/O， and improve the running efficiency and the classification accuracy.

Keywords： music classification; data mining; association rule algorithm; music style analysis; main melody extraction; FP_Growth

0 ?引 ?言

數(shù)字化技術(shù)的發(fā)展導(dǎo)致音樂(lè)產(chǎn)業(yè)發(fā)生了翻天覆地的變化，傳統(tǒng)模式的音樂(lè)運(yùn)營(yíng)已經(jīng)逐漸銷(xiāo)聲匿跡，依托互聯(lián)網(wǎng)平臺(tái)的數(shù)字音樂(lè)產(chǎn)業(yè)已經(jīng)成為現(xiàn)今社會(huì)的主流。隨著創(chuàng)新型個(gè)性化服務(wù)產(chǎn)業(yè)的發(fā)展，要求數(shù)字音樂(lè)媒體需要根據(jù)用戶(hù)的興趣不同，推薦符合其喜好風(fēng)格的音樂(lè)，但是互聯(lián)網(wǎng)平臺(tái)中的音樂(lè)數(shù)據(jù)文件是海量的，如何在大規(guī)模音樂(lè)文件數(shù)據(jù)庫(kù)中進(jìn)行風(fēng)格分類(lèi)是現(xiàn)階段研究的熱點(diǎn)問(wèn)題[1?3]。

目前，主流的研究方向是采用數(shù)據(jù)挖掘技術(shù)實(shí)現(xiàn)音樂(lè)風(fēng)格分類(lèi)，例如文獻(xiàn)[4]提出基于LDA主體挖掘模型的音樂(lè)推薦算法，實(shí)現(xiàn)了基于音頻信息的音樂(lè)推薦以及協(xié)同過(guò)濾。文獻(xiàn)[5]提出基于特征旋律挖掘的二階馬爾可夫鏈算法，該算法是在關(guān)聯(lián)規(guī)則挖掘Apriori算法的基礎(chǔ)上引入特征旋律挖掘（Interval Sequence Mining，ISM）來(lái)實(shí)現(xiàn)音樂(lè)作曲風(fēng)格訓(xùn)練。常見(jiàn)的挖掘頻繁項(xiàng)集算法有兩類(lèi)[5?9]：一類(lèi)是Apriori算法;另一類(lèi)是FP_Growth算法。因此，本文提出將FP_Growth關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于音樂(lè)媒體的風(fēng)格分類(lèi)任務(wù)中，可有效提高數(shù)據(jù)庫(kù)掃描的速度且無(wú)需候選項(xiàng)集。此外，采用多維度數(shù)據(jù)庫(kù)中數(shù)據(jù)結(jié)構(gòu)Skyline算法[10]提取多軌道的音頻媒體文件的主旋律，并進(jìn)行和弦構(gòu)成分析。

1 ?音樂(lè)媒體文件的預(yù)處理

1.1 ?主旋律提取

主旋律是音樂(lè)風(fēng)格劃分的關(guān)鍵因素，直接影響后續(xù)分類(lèi)算法的性能，是一個(gè)重要的預(yù)處理環(huán)節(jié)。目前，較為典型的主旋律提取算法是Skyline旋律提取算法，但是Skyline算法只能實(shí)現(xiàn)單一軌道的旋律提取，因此對(duì)每個(gè)軌道執(zhí)行Skyline算法。具體通過(guò)如下公式對(duì)音軌[ci]的平均音調(diào)值[pi]進(jìn)行計(jì)算：

[pi=j=1npijn] ? （1）

式中：[pij]表示音軌[ci]中音符[j]的音調(diào)值;[n]為音軌[ci]中音符的個(gè)數(shù)。

然后將每個(gè)音軌上音符的音調(diào)值做12維映射投影[10]，每個(gè)統(tǒng)計(jì)表如下所示：

[hi=（hi1，hi2，…，hi12）] （2）

對(duì)于一個(gè)音樂(lè)媒體文件來(lái)說(shuō)，12維映射的整體統(tǒng)計(jì)表示為：

[h=（h1，h2，…，h12）] （3）

其中：

[hi=j=1ChiCC] （4）

式中[C]表示音樂(lè)媒體文件中的音軌數(shù)量。

通過(guò)式（5）計(jì)算[hi=（hi1，hi2，…，hi12）]和[h=（h1，h2，…，h12）]之間的歐幾里得距離：

[edistj=i=112hij-hj2] （5）

在上述距離差計(jì)算結(jié)果的基礎(chǔ)上對(duì)兩個(gè)音軌進(jìn)行簇劃分[11]，判斷方式如下：

[edisti-edistj<δ for ?hi，hj] （6）

式中[δ]表示設(shè)定的閾值。如果任意兩個(gè)音軌[hi，hj]之間的歐幾里得距離滿(mǎn)足式（6）的條件，則表示這兩個(gè)音軌屬于同一簇。

1.2 ?和聲分析

設(shè)定[ni]，[ni+1]分別表示不同的音符，[ei]，[ei+1]分別表示兩個(gè)音符的停止時(shí)刻，[si]，[si+1]分別表示兩個(gè)音符的開(kāi)始時(shí)刻，則兩個(gè)音符和聲的表示方式為：

[ni，ni+1si≤si+1，ei>ei+1] （7）

[ni]，[ni+1]的音程計(jì)算方式如下：

[Ii，i+1=pi-pi+1] （8）

式中[pi]和[pi+1]分別表示兩個(gè)音符的音調(diào)值。

此外，利用頻繁與不頻繁的統(tǒng)計(jì)來(lái)實(shí)施音樂(lè)的分箱操作[12]，方式如下：

[fi=frequenet， ? ?f（xi）>δinot， ? ?else] （9）

式中[f（xi）]表示頻度。

2 ?基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格分類(lèi)

關(guān)聯(lián)規(guī)則是指形如[X→Y]的表達(dá)式。關(guān)聯(lián)規(guī)則挖掘Apriori算法需要通過(guò)不斷地構(gòu)造候選集、篩選候選集挖掘出頻繁項(xiàng)集，需要多次掃描原始數(shù)據(jù)，當(dāng)原始數(shù)據(jù)較大時(shí)，磁盤(pán)I/O次數(shù)太多，效率比較低下。不同于Apriori算法的“試探”策略，作為一種常見(jiàn)的挖掘頻繁項(xiàng)集算法，F(xiàn)P_Growth算法只需掃描原始數(shù)據(jù)兩遍，通過(guò)FP?tree數(shù)據(jù)結(jié)構(gòu)對(duì)原始數(shù)據(jù)進(jìn)行壓縮，效率較高[13]。因此，將FP_Growth關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于音樂(lè)媒體的風(fēng)格分類(lèi)任務(wù)中。

令[I=i1，i2，…，id]表示音樂(lè)數(shù)據(jù)中所有項(xiàng)的集合，而[T=t1，t2，…，tN]表示所有事務(wù)的集合。每個(gè)事務(wù)[ti]包含的項(xiàng)集都是[I]的子集。

在關(guān)聯(lián)分析中，支持度（support）和置信度（confidence）[14?15]的具體表示方式為：

[s（X→Y）=σ（X?Y）N] （10）

[c（X→Y）=σ（X?Y）σ（X）] （11）

式中[N]表示事務(wù)的數(shù)量。

本文提出的音樂(lè)分類(lèi)方式的支持度計(jì)算方式如下：

[s={xx∈D，rulei∈x}] （12）

式中：[D]表示訓(xùn)練數(shù)據(jù)集;[rulei]為[D]的規(guī)則。在關(guān)聯(lián)分析中集合被視為項(xiàng)集（itemset）。

基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的音樂(lè)風(fēng)格分類(lèi)的核心步驟是構(gòu)建FP?tree樹(shù)節(jié)點(diǎn)，以便減少所需頻繁項(xiàng)集的數(shù)量。事務(wù)型數(shù)據(jù)庫(kù)的示例如表1所示，F(xiàn)P_tree樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)如圖1所示，其構(gòu)造FP_tree樹(shù)的每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體代碼如下：

class TreeNode {

private：

int32 N_Nodes; ?//節(jié)點(diǎn)名稱(chēng)

int Numbers; ?//支持度計(jì)數(shù)

TreeNode *P_Nodes; ?//父節(jié)點(diǎn)

Vector C_Nodes; //子節(jié)點(diǎn)

TreeNode *Ner_Nodes; ?//指向同名節(jié)點(diǎn)

…

}

3 ?仿真結(jié)果

實(shí)驗(yàn)數(shù)據(jù)庫(kù)為互聯(lián)網(wǎng)音樂(lè)平臺(tái)中隨機(jī)選取的500首音樂(lè)文件，共包括6種音樂(lè)風(fēng)格類(lèi)型（POP，ROCK，JAZZ，METAL，BLUES，F(xiàn)OLK）。所有實(shí)驗(yàn)運(yùn)行環(huán)境配置信息為：操作系統(tǒng)為Windiws 10，CPU為Intel Pentium4@2.4 GHz，內(nèi)存為4 GB DDR SDRAM，硬盤(pán)為7 200轉(zhuǎn)的500 GB IDE硬盤(pán)。

將基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格分類(lèi)方法與基于LAD主題[4]、Apriori算法[5]的音樂(lè)風(fēng)格分類(lèi)方法進(jìn)行對(duì)比分析。針對(duì)相同的音樂(lè)數(shù)據(jù)庫(kù)，當(dāng)置信度為56%時(shí)，在支持度分別為0.4%，0.5%，0.6%，0.8%，1.0%，1.2%和1.5%的情況下，三種方法的運(yùn)行時(shí)間比較結(jié)果如圖2所示。

從圖2可以看出，隨著支持度逐漸增大，三種方法的運(yùn)行時(shí)間均逐漸減少。但是在支持度較小時(shí)，本文提出音樂(lè)風(fēng)格分類(lèi)方法具有明顯的效率優(yōu)勢(shì)，在0.4%最小支持度時(shí)，本文方法運(yùn)行時(shí)間約為其他兩種方法的35%。這是因?yàn)榛贔P_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格分類(lèi)方法在支持度很小的情況下仍只掃描兩次數(shù)據(jù)庫(kù)，即I/O開(kāi)銷(xiāo)較小，而其他兩種方法會(huì)隨著選項(xiàng)集的長(zhǎng)度變大而增加I/O開(kāi)銷(xiāo)。

三種音樂(lè)風(fēng)格分類(lèi)方法的準(zhǔn)確性對(duì)比結(jié)果如表2所示?？梢钥闯?，相比于其他兩種方法，基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格分類(lèi)方法的準(zhǔn)確率更高，分類(lèi)準(zhǔn)確率提高約2%。

4 ?結(jié) ?語(yǔ)

本文提出一種高效的適用于音樂(lè)媒體分類(lèi)的FP_Growth關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法，在單一軌道旋律提取的基礎(chǔ)上，采用多維度數(shù)據(jù)庫(kù)中數(shù)據(jù)結(jié)構(gòu)Skyline算法提取多軌道的音頻媒體文件的主旋律。仿真測(cè)試結(jié)果顯示，基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法的音樂(lè)風(fēng)格分類(lèi)方法的性能表現(xiàn)（在運(yùn)行時(shí)間和準(zhǔn)確度方面）較為突出，勝過(guò)其他所有的方法。但是在某些類(lèi)型的音樂(lè)識(shí)別中表現(xiàn)欠佳，例如ROCK風(fēng)格類(lèi)型，后續(xù)將針對(duì)該方面進(jìn)行側(cè)重分析。

參考文獻(xiàn)

[1] DENG J J， LEUNG C H C， MILANI A， et al. Emotional states associated with music： classification， prediction of changes， and consideration in recommendation [J]. ACM tran?sactions on interactive intelligent systems， 2015， 5（1）： 1?36.

[2] KOUR G， MEHAN N， KOUR G， et al. Music genre classification using MFCC， SVM and BPNN [J]. International journal of computer applications， 2015， 112（6）： 12?14.

[3] CHOI K， LEE J H， HU X， et al. Music subject classification based on lyrics and user interpretations [J]. Proceedings of the association for information science & technology， 2016， 53（1）： 1?10.

[4] 李博，陳志剛，黃瑞，等.基于LDA模型的音樂(lè)推薦算法[J].計(jì)算機(jī)工程，2016，42（6）：175?179.

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

[6] NAJI M， FIROOZABADI M， AZADFALLAH P. Emotion classification during music listening from forehead biosignals [J]. Signal image & video processing， 2015， 9（6）： 1365?1375.

[7] BANIYA B K， LEE J. Importance of audio feature reduction in automatic music genre classification [J]. Multimedia tools & applications， 2016， 75（6）： 1?14.

[8] KHONGLAH B K， PRASANNA S R M. Speech/music classification using speech?specific features [J]. Digital signal proces?sing， 2016， 48（3）： 71?83.

[9] RODRIGUES F A. A survey on symbolic data?based music genre classification [J]. Expert systems with applications， 2016， 60（3）： 190?210.

[10] FARROKHMANESH M， HAMZEH A. Music classification as a new approach for malware detection [J]. Journal of computer virology & hacking techniques， 2018（2）： 1?20.

[11] ULAGANATHAN A S， RAMANNA S. Granular methods in automatic music genre classification： a case study [J]. Journal of intelligent information systems， 2018（23）： 1?21.

[12] ROSNER A， KOSTEK B. Automatic music genre classification based on musical instrument track separation [J]. Journal of intelligent information systems， 2017（2）： 1?22.

[13] 王建明，袁偉.基于節(jié)點(diǎn)表的FP?Growth算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2018，39（1）：140?145.

[14] WANG B， DAN C， SHI B， et al. Comprehensive association rules mining of health examination data with an extended FP?Growth method [J]. Mobile networks & applications， 2017， 22（2）： 1?8.

[15] KHONGLAH B K， PRASANNA S R M. Clean speech/speech with background music classification using HNGD spectrum [J]. International journal of speech technology， 2017， 20（6）： 1?14.

作者簡(jiǎn)介：張婷婷（1983—），女，甘肅平?jīng)鋈?，碩士，講師，主要研究方向?yàn)橐魳?lè)教育理論。