基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類研究

謝搶來 楊威

摘 ?要： 為從海量音頻信息中快速準(zhǔn)確地獲取所需文件，研究基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類方法。以數(shù)據(jù)立方體下具有多維屬性的多軌道數(shù)字音頻文件為研究對象，采用FP_Growth關(guān)聯(lián)規(guī)則挖掘算法排序多軌道數(shù)字音頻文件數(shù)據(jù)集的頻繁1?相集，采用FP tree挖掘頻繁項集獲取多維關(guān)聯(lián)規(guī)則集。識別并提取多軌道數(shù)字音頻文件中某類型音頻文件中的音頻內(nèi)容，使用刪除停用詞結(jié)合TF/IDF的計算方式獲取清潔的音頻文件，應(yīng)用音頻文件數(shù)據(jù)集的多維關(guān)聯(lián)規(guī)則集，綜合考慮匹配規(guī)則數(shù)和置信度，搜索規(guī)則集，獲取該類型音頻文件最相配類別，完成多軌道數(shù)字音頻文件分類。實驗結(jié)果表明，所提方法能夠直觀有效地分類多軌道數(shù)字音頻文件，且分類結(jié)果準(zhǔn)確率和召回率平均值分別達(dá)到96.60%和96.54%，顯著高于對比方法。

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則; 數(shù)據(jù)挖掘; 多軌道; 數(shù)字音頻; 文件分類; 數(shù)據(jù)立方體

中圖分類號： TN911.72?34; TP301.6 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）01?0179?04

Research on multi?track digital audio file classification

based on FP_Growth association rule mining

XIE Qianglai， YANG Wei

Abstract： A multi?track digital audio file classification method based on FP_Growth association rule mining is studied to get the required files quickly and accurately from the massive audio information. By taking multi?track digital audio files with multidimensional attributes under the data cube as the research object， FP_Growth association rules mining algorithm is adopted to sort the frequent 1?phase sets of multi?track digital audio file data sets， and FP tree mining frequent item sets are adopted to obtain multidimensional association rules. The audio content in a certain type of audio file in multi?track digital audio files is identified and extracted， the calculation method of deleting stop words combined with TF/IDF is adopted to obtain clean audio files. The multidimensional association rules set of audio file data set is applied to take into account comprehensively the matching rule number and degree of confidence， search the rule sets， obtain the most suitable type of audio file categories and complete the classification of multi?track digital audio files. The experimental results show that the proposed method can intuitively and effectively classify multi?track digital audio files， and the averages of accuracy and recall rate of classification result reach 96.60% and 96.54% respectively， significantly higher than the comparison method.

Keywords： association rule; data mining; multi?track; digital audio; file classification; data cube

0 ?引 ?言

不同類型音頻信號經(jīng)采集、量化編碼壓縮、多軌錄入等數(shù)字化處理后，以文件形式存儲在計算機硬盤等存儲媒體內(nèi)，最終形成多軌道數(shù)字音頻文件。從多軌道數(shù)字音頻文件中快速準(zhǔn)確地獲取所需類型音頻文件，在視頻編輯、影像分析等領(lǐng)域具有重要的應(yīng)用價值[1]。

數(shù)據(jù)挖掘是挖掘并分析項集之間某種潛在關(guān)系，這種潛在關(guān)系稱為關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則可劃分為維間、單維、多維、量化等不同類型[2]。由于多軌道數(shù)字音頻文件具有多維屬性[3]，因此在分類文件之前需將多軌道數(shù)字音頻文件數(shù)據(jù)集內(nèi)海量多維數(shù)據(jù)以數(shù)據(jù)立方體的形式存儲起來，這種存儲方式不僅簡單，且基于數(shù)據(jù)立方體挖掘數(shù)據(jù)間關(guān)聯(lián)規(guī)則不僅能夠節(jié)省挖掘時間，還可提升數(shù)據(jù)挖掘準(zhǔn)確率。FP_Growth算法是當(dāng)前挖掘頻繁項集算法中應(yīng)用最廣，且不產(chǎn)生候選項集的關(guān)聯(lián)規(guī)則挖掘算法[4?5]。因此，本文研究基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類方法，在數(shù)據(jù)立方體基礎(chǔ)上采用FP_Growth多維關(guān)聯(lián)規(guī)則挖掘算法挖掘多軌道數(shù)字音頻文件中不同類型音頻間關(guān)聯(lián)規(guī)則，根據(jù)挖掘到的關(guān)聯(lián)規(guī)則對不同類型的數(shù)字音頻文件進行分類。

1 ?基本概念

1.1 ?關(guān)聯(lián)規(guī)則

假設(shè)[I]和[D]代表項的集合和全體事務(wù)集合，而事務(wù)[T]是集合[I]的一個子集，則[T?I]。每個事務(wù)都有獨立的標(biāo)識，每個標(biāo)識用[TID]表示。假設(shè)[A]是一個項集，[A]在事務(wù)[T]之中，則[A?T]，關(guān)聯(lián)規(guī)則就是類似于[A?B]的蘊涵式，當(dāng)項集[A]屬于事務(wù)[T]，項集[B]屬于項的集合[I]，且[A?B=][?]。全體事務(wù)集[D]支持規(guī)則[A?B]，支持度為[s]，[s]是全體事務(wù)集[D]包含[A?B]的百分比，其條件概率可表示為[PA?B]。[c]為規(guī)則[A?B]在全體事務(wù)集[D]中的置信度，[c]是全體事務(wù)集[D]中同時包含[A]和[B]的事務(wù)占[D]總量的百分比，此時條件概率為[PBA]，表達(dá)式為：

[supportA?B=PA?B] （1）

[confidenceA?B=PBA] （2）

支持最小支持度的同時也支持最小置信度的閾值（min?conf）規(guī)則叫做強規(guī)則[6]。

1.2 ?多維關(guān)聯(lián)規(guī)則

假若規(guī)則不僅只有一個維度，而是具有兩個以上的維度，則該規(guī)則叫做多維關(guān)系規(guī)則。例如規(guī)則：

[agex，″32…41″∧income x，″43Κ…47Κ″ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?buysx，″?highresolutionTV″] （3）

1.3 ?數(shù)據(jù)立方體

使用數(shù)據(jù)立方體構(gòu)建多軌道數(shù)字音頻文件數(shù)據(jù)集中數(shù)據(jù)和[OLAP]多維數(shù)據(jù)模型，數(shù)據(jù)立方體構(gòu)建數(shù)據(jù)模型前需要從多維角度對數(shù)據(jù)實行角度[7]觀察，對數(shù)據(jù)特定角度的觀察、分析所采用的一類特殊屬性稱為維，數(shù)據(jù)屬性的集合就能形成一個維。數(shù)據(jù)立方體由維和事實定義，其中事實由數(shù)值衡量獲取。

數(shù)據(jù)集中的數(shù)據(jù)立方體是多維數(shù)據(jù)存儲的一種形象化比喻，且維度不僅限于2維或者3維，它可以是多維的，用[n]維描述，任意[n]維立方體都是[n-1]維立方體的序列。數(shù)據(jù)立方體中每一個方格記錄的都是相應(yīng)維成員的頻繁衡量值[8]，可用[count]表示，數(shù)據(jù)立方體的每一個方格都能夠提供預(yù)計算的匯總數(shù)據(jù)，使得多維關(guān)聯(lián)規(guī)則支持度以及置信度的計算更加簡便。

2 ?FP_Growth多維關(guān)聯(lián)規(guī)則挖掘算法

通過Apriori算法變換可獲得基于數(shù)據(jù)立方體的多維關(guān)聯(lián)規(guī)則挖掘算法，但Apriori算法在挖掘關(guān)聯(lián)規(guī)則時會受兩種非平凡開銷影響，導(dǎo)致挖掘結(jié)果存在偏差。FP_Growth關(guān)聯(lián)規(guī)則挖掘算法是一種在挖掘頻繁項集過程中不產(chǎn)生候選項集的算法，該算法構(gòu)建一個壓縮度較高的數(shù)據(jù)結(jié)構(gòu)（FP），壓縮原來的事務(wù)數(shù)據(jù)集。FP_Growth關(guān)聯(lián)規(guī)則挖掘算法采用模式增長方式挖掘多軌道數(shù)字音頻文件中數(shù)據(jù)集的頻繁項集，該算法步驟如下：

1） 頻繁1?項集排序。獲取頻繁1?項集[L]和相應(yīng)的支持度，掃描多軌道數(shù)字音頻文件中數(shù)據(jù)集[L]。

2） 構(gòu)建[FP tree]。使用“[null]”標(biāo)記[FP tree]構(gòu)建的基本點[9]，假設(shè)[k?]謂詞集屬于全體事務(wù)集合[D]，則按照頻繁謂詞集[L]對[k?]謂詞集進行由大到小排列，并用[gG]代表排列后的[k?]謂詞集列表。[g]代表第一個謂詞元素，[G]代表剩余元素的列表，使用[insert?treegG?T]表示，以下為[FP tree]基本點構(gòu)建過程執(zhí)行情況：假設(shè)[T]有孩子[N]，并設(shè)置[N]=[g]，即[N.item?name=g.item?name]，那么[N]的數(shù)量多1;如果[N]≠[g]，則需要構(gòu)建新節(jié)點[N]，并設(shè)置[N]=[g]，計數(shù)設(shè)置為1，與其父節(jié)點[T]產(chǎn)生鏈接，并與具有同[item?name]節(jié)點相串聯(lián)，該串聯(lián)過程要通過使用節(jié)點鏈結(jié)構(gòu)實現(xiàn)。若剩余元素的列表[G]并不為空[10]，則可以調(diào)動自身的[insert?treeG.N]。

3） FP tree挖掘。從長度為1的頻繁模式開始，構(gòu)造相應(yīng)條件模式基。模式基構(gòu)建完成后，開始構(gòu)建FP tree，且在FP tree上遞歸實行[FP tree]挖掘。

FP_Growth關(guān)聯(lián)規(guī)則挖掘算法基本包括上述三個步驟，重點是構(gòu)建FP tree的過程。給定一個事務(wù)數(shù)據(jù)集后，依據(jù)FP_Growth關(guān)聯(lián)規(guī)則挖掘算法構(gòu)建FP tree，可對數(shù)據(jù)集頻繁項信息實行反饋，挖掘承載體由數(shù)據(jù)集變?yōu)镕P tree，可簡化數(shù)據(jù)集頻繁項挖掘過程。表1為給定的事務(wù)數(shù)據(jù)集，圖1為根據(jù)表1所示數(shù)據(jù)并在支持度計數(shù)為2時構(gòu)建的FP tree。

對事物數(shù)據(jù)集的每個事務(wù)分別調(diào)用[insert?treegG?T]算法過程就是構(gòu)建FP tree的過程。假設(shè)[Li]是頻繁表項，[T]是FP tree，[Lij]代表[Li]的第[j]項，則[g=Li1，G=Li2，…，G=Lin]，調(diào)用[insert?tree]算法，假設(shè)[Lij]代表頻繁表項，現(xiàn)將[Lij]嵌入到頻繁模式樹FP tree中，以算法原理為依據(jù)首先判定[T]是否有子節(jié)點[N]，且設(shè)置[N]=[g=Li1]，若相同則計數(shù)加1，如果不相同則需要構(gòu)建一個[T]的新子節(jié)點，即每一步[insert?treegG?T]算法調(diào)用都將遍及[T]的子節(jié)點，且遍及子節(jié)點的時間復(fù)雜度越高，[T]的子節(jié)點個數(shù)就越多。

假設(shè)[Li]有[m]個節(jié)點（[Li1，Li2，…，Lim]）與[T]的子節(jié)點（[T1，T2，…，Tm]，[Tm]是[Tm-1]的子節(jié)點）對應(yīng)相同，設(shè)定[brotherTm]代表樹節(jié)點[Tm]兄弟節(jié)點個數(shù)，由于函數(shù)每一步[insert?treegG?T]算法調(diào)用都將遍及[T]的子節(jié)點[11]，因此[Li]嵌入頻繁模式樹FP tree的時間復(fù)雜度與遍及每一個[Tk]，[1≤k≤m]子節(jié)點的時間復(fù)雜度[O]相乘后的結(jié)果相等，即[k=1mObrotherTk]。

通過上述過程基于數(shù)據(jù)立方體獲取多軌道數(shù)據(jù)音頻文件數(shù)據(jù)集的多維關(guān)聯(lián)規(guī)則集。

3 ?多軌道數(shù)字音頻文件分類關(guān)聯(lián)規(guī)則

目前對數(shù)字型多軌道音頻文件分類時經(jīng)常使用關(guān)聯(lián)規(guī)則方法，以多軌道數(shù)字音頻文件數(shù)據(jù)集中的最強關(guān)聯(lián)規(guī)則為分類依據(jù)[12]。為實現(xiàn)優(yōu)質(zhì)的多軌道數(shù)字音頻文件分類，需結(jié)合上文所述的FP_Growth多維關(guān)聯(lián)規(guī)則挖掘算法，研究基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類方法。

3.1 ?多軌道數(shù)字音頻文件的關(guān)聯(lián)規(guī)則表示和預(yù)處理

識別并提取多軌道數(shù)字音頻文件中某類型音頻文件的音頻內(nèi)容，每個音頻主題數(shù)據(jù)使用數(shù)據(jù)立方體表示。設(shè)定某類型數(shù)字音頻文件的類標(biāo)簽和音頻分別為[C]和[TT=t1，t2，…，tm]，該類型數(shù)字音頻文件可采用全體事務(wù)集[D]的表示方法[D：C，t1，t2，…，tm]描述。多軌道數(shù)字音頻文件中不同類型音頻文件可表示成事務(wù)集，某一類型的音頻文件由音頻和音頻文件所屬類別共同組成該類型音頻文件事務(wù)集合的項集，每一條關(guān)聯(lián)規(guī)則都從表示該類型音頻文件集的事務(wù)集中產(chǎn)生。當(dāng)清理數(shù)據(jù)時，刪除對構(gòu)造關(guān)聯(lián)分類器作用很小甚至沒有作用的音頻，為提高多軌道數(shù)字音頻文件中某一類型音頻文件的清潔度[13]，通常使用刪除停用詞結(jié)合TF/IDF的計算方式清理音頻文件。TF/IDF值獲取的計算公式為：

[TFIDFi=TFWi，Doc?log DDFWi] （4）

式中：[TFWi，Doc]代表單音頻[Wi]在音頻文件中出現(xiàn)的頻率;[D]代表數(shù)字音頻文件總數(shù);[DFWi]代表單音頻[Wi]在其中出現(xiàn)至少一次的數(shù)字音頻文件數(shù)目。以下為對TF/IDF權(quán)歸一化處理公式：

[dij=TFIDFij=1nTFIDF2i] （5）

設(shè)置TF/IDF閾值，為獲取一個清潔的數(shù)字音頻文件事務(wù)集，需要在該數(shù)字音頻文件事務(wù)集中清除低于該閾值的音頻，并基于FP_Growth關(guān)聯(lián)規(guī)則挖掘算法對該清潔的數(shù)字音頻文件事務(wù)集進行多維關(guān)聯(lián)規(guī)則挖掘，挖掘過程在第2節(jié)中有詳細(xì)描述，此處不再重復(fù)。

3.2 ?利用關(guān)聯(lián)規(guī)則進行多軌道數(shù)字音頻文件分類

經(jīng)過FP_Growth關(guān)聯(lián)規(guī)則挖掘算法挖掘清潔的多軌道數(shù)字音頻文件事務(wù)集獲取多維關(guān)聯(lián)規(guī)則后，依據(jù)該關(guān)聯(lián)規(guī)則分類數(shù)字音頻文件[14]，通過搜索規(guī)則集獲取與該類型音頻文件最相配類別的過程，稱為多軌道數(shù)字音頻文件的分類處理過程。通常情況下將多軌道數(shù)字音頻文件中不同類型音頻文件分配到與之規(guī)則匹配最多的類別，或是分配給與其第一個規(guī)則相匹配的類別。但這種分配方式有一個缺陷，就是在分配過程中沒有考慮置信度作用，為解決這一缺陷要綜合考慮匹配規(guī)則數(shù)和置信度的作用。

現(xiàn)給定多軌道數(shù)字音頻文件中的某一類型數(shù)字音頻文件，以數(shù)字音頻文件的音頻為依據(jù)生成規(guī)則列表。將該規(guī)則列表按類標(biāo)簽分組，設(shè)置一個固定的置信度閾值，刪除該類型音頻文件分組中低于該置信度閾值的匹配規(guī)則，并將所有分組按照置信度的和排序[15]。以下為類識別規(guī)則：選擇置信度和最大分組的標(biāo)簽作為該類型數(shù)字音頻文件的類標(biāo)簽;當(dāng)置信度的和均相等時，將匹配規(guī)則最多組的標(biāo)簽作為該類型數(shù)字音頻文件類標(biāo)簽。具體過程如下：

輸入：待分類多軌道數(shù)字音頻文件中的某類型數(shù)字音頻文件[Doc=t1，t2，…，tm];關(guān)聯(lián)分類器;置信度閾值[τ]。

輸出：待分類多軌道數(shù)字音頻文件中的某類型數(shù)字音頻文件[Doc]的類標(biāo)簽

方法：

1） [Count=0]

2） 初始化音頻文件事務(wù)集[S←Φ]

3） 檢索規(guī)則庫中的每個規(guī)則

//以規(guī)則前件和[Doc]數(shù)字音頻文件音頻為依據(jù)，生成規(guī)則列表

4） [ifr Doc ∧r.confidence>τ]

5） [S←S?r]

6） 以類標(biāo)簽為依據(jù)將入選規(guī)則集分成多個子集，該子集可表示為[S1，S2，…，Sn]

7） 檢索子集[S1，S2，…，Sn]

8） 匯總規(guī)則信任度，統(tǒng)計規(guī)則數(shù)

9） 根據(jù)置信排序子集[S1，S2，…，Sn]

10） 將類分配給新音頻文件

4 ?仿真測試

采用本文提出的基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類方法對某類型音樂廣播電臺多軌道數(shù)字音頻文件中不同類型的音頻文件進行分類，得到分類結(jié)果如圖2所示。

圖2中，上面的音頻波（綠色）為MP3歌曲音頻文件，下面的音頻波（紅色）為WAV語音廣播音頻文件，不同類型音頻文件使用不同顏色標(biāo)注，且從圖中可看出兩種音頻波形并不一致，說明本文方法可以有效地分類出實驗多軌道數(shù)字音頻文件中不同類型的音頻文件。

為驗證本文方法對多軌道數(shù)字音頻文件分類方面的優(yōu)越性能，對上一實驗中的實驗對象進行關(guān)聯(lián)規(guī)則挖掘識別。實驗對象中包含MP3，WMA，MIDI，WAV，CDA，AU，AIF，RM，VOC等格式數(shù)字音頻文件共計4 296份，隨機抽取其中95%作為訓(xùn)練集，余下5%作為測試集。采用三種方法挖掘訓(xùn)練多軌道數(shù)字音頻文件數(shù)據(jù)集中的音頻文件，并將挖掘到的關(guān)聯(lián)規(guī)則運用到測試數(shù)據(jù)集中完成數(shù)字音頻文件分類，分類結(jié)果見表2。

由表2可知，采用本文方法分類多軌道數(shù)字音頻文件中不同類型音頻文件的分類結(jié)果準(zhǔn)確率最高，平均值達(dá)到96.60%，且召回率也是三種方法中最高的，平均值達(dá)到96.54%，說明本文方法分類多軌道數(shù)字音頻文件的性能較好。

5 ?結(jié) ?論

快速準(zhǔn)確地從海量多軌道數(shù)字音頻文件數(shù)據(jù)中找到有用的信息是網(wǎng)絡(luò)技術(shù)發(fā)展的必然要求。本文研究基于FP_Growth關(guān)聯(lián)規(guī)則挖掘的多軌道數(shù)字音頻文件分類方法，該方法不僅降低了多軌道數(shù)字音頻文件數(shù)據(jù)挖掘過程中候選項目集的產(chǎn)生數(shù)量，還減少了數(shù)字音頻文件數(shù)據(jù)掃描次數(shù)，提高多軌道數(shù)字音頻文件分類效率。本文方法在對多軌道數(shù)字音頻文件分類方面具有較好的發(fā)展前景。

參考文獻(xiàn)

[1] 呂璐成，趙亞娟，王學(xué)昭，等.基于關(guān)聯(lián)規(guī)則挖掘的研發(fā)團隊識別方法[J].科技管理研究，2016，36（17）：148?152.

[2] 張雪萍，李圍成，祝玉華.基于 FP?樹的時空關(guān)聯(lián)規(guī)則挖掘算法研究[J].微電子學(xué)與計算機，2016，33（8）：130?133.

[3] 張穩(wěn)，羅可.一種基于Spark框架的并行FP_Growth挖掘算法[J].計算機工程與科學(xué)，2017，39（8）：1403?1409.

[4] 申彥，朱玉全，劉春華.基于磁盤存儲1項集計數(shù)的增量FP_Growth算法[J].計算機研究與發(fā)展，2015，52（3）：569?578.

[5] 王建明，袁偉.基于節(jié)點表的FP_Growth算法改進[J].計算機工程與設(shè)計，2018，39（1）：140?145.

[6] 李維娜，任家東.軟件群體中基于交互序列的頻繁模式挖掘算法研究[J].小型微型計算機系統(tǒng)，2018，39（5）：1046?1051.

[7] 王艷輝，王淑君，李曼，等.基于改進FP_Growth算法的CRHX型動車組牽引系統(tǒng)關(guān)聯(lián)失效模型研究[J].鐵道學(xué)報，2016，38（9）：72?80.

[8] 程廣，王曉峰.基于MapReduce的并行關(guān)聯(lián)規(guī)則增量更新算法[J].計算機工程，2016，42（2）：21?25.

[9] 唐曉東.基于關(guān)聯(lián)規(guī)則映射的生物信息網(wǎng)絡(luò)多維數(shù)據(jù)挖掘算法[J].計算機應(yīng)用研究，2015，32（6）：1614?1616.

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

[11] 劉軍煜，賈修一.一種利用關(guān)聯(lián)規(guī)則挖掘的多標(biāo)記分類算法[J].軟件學(xué)報，2017，28（11）：2865?2878.

[12] 王雯，趙衎衎，李翠平，等.Spark平臺下的短文本特征擴展與分類研究[J].計算機科學(xué)與探索，2017，11（5）：732?741.

[13] 王莉莉.多維多層數(shù)據(jù)的無冗余跨層挖掘算法[J].微電子學(xué)與計算機，2018，35（2）：113?117.

[14] 李洪成，吳曉平，俞藝涵.基于多維頻繁序列挖掘的攻擊軌跡識別方法[J].海軍工程大學(xué)學(xué)報，2018，30（1）：40?45.

[15] 郭燁，海霞，趙長青，等.數(shù)字音頻廣播與航空無線電導(dǎo)航業(yè)務(wù)兼容性研究[J].電視技術(shù)，2017，41（6）：62?67.

作者簡介：謝搶來（1984—），湖南人，工程碩士，講師，研究方向為數(shù)據(jù)挖掘、數(shù)據(jù)庫信息優(yōu)化。

楊 ?威（1985—），湖北人，工程碩士，講師，研究方向為計算機應(yīng)用。