融合KPCA與改進KNN的蒙古族音樂分類方法

宋 揚,王海龍,柳 林,裴冬梅

(內蒙古師范大學 計算機科學技術學院,內蒙古 呼和浩特 010022)

近年來,隨著信息技術的成熟及互聯(lián)網(wǎng)的發(fā)展,海量數(shù)字音樂信息迅速涌現(xiàn)并呈現(xiàn)爆發(fā)式增長[1],如何高效地從浩瀚媒體資源中快速檢索到用戶喜愛的音樂,對檢索數(shù)字音樂資源具有重要意義。面對大規(guī)模的網(wǎng)絡音樂數(shù)據(jù),數(shù)字音樂的檢索與分類成為當前的研究熱點,尤其是針對音樂流派/曲風(Music genre/style)的分類成為其中的重要分支[2]。在眾多不同曲風的音樂中,有關民族音樂的研究受到了研究者的廣泛關注。2008年,蒙古族民歌被列入國家第二批非物質文化遺產,但由于蒙古族音樂傳承方式較為落后,其生存空間日益減小。如何依托音樂分類技術,對蒙古族音樂進行有效、數(shù)字化的分類研究成為傳承保護蒙古族文化的迫切需要[3]。

在音樂分類領域中,音樂的種類和形式繁多,并存在差異性[4],因此,音樂分類是一項極其復雜的任務,往往存在分類準確率較低、周期性長、噪聲影響較大、魯棒性較差等問題[5-6]。音樂流派/曲風分類方法主要采用支持向量機(Support Vector Machine,SVM)、K近鄰(K-Nearest Neighbors,KNN)、隱馬爾可夫模型(Hidden Markov Model,HMM)、人工神經(jīng)網(wǎng)絡(Artificial Neural Network,ANN)等模型進行分類,其中KNN在音樂分類中的應用較為廣泛。目前特征提取在音樂分類研究中占據(jù)重要地位,特征數(shù)量的增加并不一定會提高模型的性能,通常反而會顯著增加模型訓練所需的樣本量,而足夠的樣本量往往很難獲取。為了避免特征過多造成分類性能差的問題,有必要對特征進行篩選,選擇重要特征并消除無關和冗余特征。現(xiàn)有的KNN分類方法對過濾掉冗余、無關特征并不適用,所以如何有效進行特征選擇,提升音樂分類準確率是進一步需要解決的問題。針對此問題,本文在分析現(xiàn)有的音樂分類研究成果的基礎上,提出一種適用于蒙古族音樂資源的分類方法,著重對蒙古族音樂進行分類與整理。

1 研究背景

音樂特征提取是分類任務中至關重要的一部分,對最終的音樂分類效果起到了關鍵作用。Trabelsi等[7]在對音樂分類的過程中提取了Mel頻率倒譜系數(shù)(Mel Frequency Cepstrum Coefficient,MFCC),證實了MFCC是區(qū)分音樂類型的重要特征參數(shù)。Baniya等[8]提取了MFCC和節(jié)拍直方圖兩類特征參數(shù)作為音樂的相關特征對音樂進行分類。楊曉宇等[9]通過提取短時能量、短時平均過零率和短時平均幅度作為特征值,對音樂進行了較為準確的分類。但文獻[7-9]均存在所采用的特征參數(shù)較少、提取特征較單一等問題。為了解決上述問題,雷文康[10]抽取音樂信號的特征(音色特征、節(jié)奏特征、音高特征)與聲譜圖特征(短時傅里葉變換得到的時頻圖、Mel譜、常數(shù)Q聲譜)輸入到循環(huán)神經(jīng)網(wǎng)絡中對音樂曲風進行分類。劉雨亭[11]通過基于內容的音樂特征(音色特征、聽感特征和節(jié)拍特征)對音樂進行分類。但文獻[10-11]所用方法的特征向量維數(shù)過多,導致分類所需的時間較長?；谏鲜鎏卣魈崛〈嬖凇熬S數(shù)災難”的問題,本文引入了對提取的特征采取降維和進行特征選擇的方法。

在分類模型的構建上,為了解決音樂分類過程中存在分類準確率較低等問題,邵曦等[12]對傳統(tǒng)的SVM進行改進,利用改進后的SVM對音樂進行分類,驗證了SVM主動學習方法的有效性。但SVM模型對參數(shù)的依賴較為嚴重,參數(shù)往往會影響音樂分類的結果。除此之外,肖曉紅等[13]將提取的特征輸入到HMM中,從中找到最佳HMM參數(shù)。HMM作為一種線性分類技術,它認為音樂類型與特征之間存在線性關系,但大多數(shù)情況下,音樂類型與特征之間存在著非線性關系。因此,HMM的局限性很明顯,得到的音樂分類結果也并不穩(wěn)定。除上述模型外,神經(jīng)網(wǎng)絡也是音樂分類中常用的模型之一。它可以使音樂類型與特征之間進行有效的擬合,但仍存在一些明顯的缺陷,例如需要大規(guī)模的音樂訓練樣本,如果訓練樣本較少,會影響音樂分類的準確率;神經(jīng)網(wǎng)絡的結構也較為復雜,使得音樂分類模型的收斂效率較低且分類時間較長[14-15]。因此,應用上述傳統(tǒng)分類方法去解決音樂分類問題時會存在不足,大多數(shù)情況下采用混合或者改進的方法來提升分類準確率。KNN作為經(jīng)典的分類方法之一,與其他分類算法相比,優(yōu)勢在于它可以充分利用訓練樣本的鄰域信息,在一定程度上提高算法的分類準確率。雖然KNN方法具有易實現(xiàn)、魯棒性高等優(yōu)點,但在具體應用中也存在不足: 一方面計算開銷大,分類效率低;另一方面,在進行相似性度量和類別判斷時,等同對待各個特征項和近鄰樣本,從而影響分類準確率[16]。因此,辛欣等[17]提出結合KNN算法與潛在概率語義分析(Probabilistic Latent Semantic Analysis,PLSA)模型進行音樂分類,與單一的傳統(tǒng)KNN分類算法相比,分類效果上得到了明顯的提高。蒙古族音樂由于其本身的“長、短調”具有鮮明的民族風格和自身的獨特性,對蒙古族音樂的分類研究相對于其他音樂的分類研究較少,因此,蒙古族音樂的自動分類是一項非常具有挑戰(zhàn)性的任務。本文主要將KNN算法應用到蒙古族音樂分類中,并針對目前音樂分類工作中存在的特征易出現(xiàn)冗余導致分類準確率較低等問題,提出一種核主成分分析(Kernel Principal Components Analysis,KPCA)與改進的KNN算法進行融合的分類方法,即KPCA-FSKNN(Kernel Principal Components Analysis-Feature Selection K-Nearest Neighbor)分類方法,通過該方法篩選出最佳特征子集,并進行更有效的蒙古族音樂分類。

2 研究方法

經(jīng)典的子空間學習方法例如主成分分析(Principal Component Analysis,PCA)、線性判別分析(Linear Discriminant Analysis,LDA)等通過尋找投影矩陣從而得到低維魯棒特征,在降低維度的同時,沒有進行有效的特征選擇,在一定程度上影響了特征表示的準確性[18]。因此,不同于傳統(tǒng)的子空間學習方法,本文引入核的主成分分析降維方法并將核主成分分析與改進的基于特征選擇的KNN算法進行融合。利用核主成分分析對輸入的時域特征、頻域特征和倒譜域特征進行篩選,在此基礎上,將篩選過后的新的特征集輸入到改進后的KNN分類模型中,從中尋找最佳特征子集,通過應用最佳特征子集,提高KNN算法的分類準確率。

2.1 核主成分分析

核主成分分析是解決維數(shù)災難的一種有效方式,它的優(yōu)勢在于利用兩個向量之間的點積——核函數(shù),通過核函數(shù)的方法直接實現(xiàn)非線性變換[19]。核主成分分析是主成分分析的非線性擴充,可以發(fā)現(xiàn)數(shù)據(jù)集中隱匿的非線性信息。實質上,核主成分分析利用非線性函數(shù)φ將原始輸入空間的數(shù)據(jù)映射到高維特征空間中,隨后在該空間中進行主成分分析變換。

首先,將樣本映射到高維特征空間中,設變量X為音樂樣本訓練集,X={x1,x2,…,x i,…,x n}是所有樣本點的集合,x i∈X為樣本點。X中共有n個樣本。

非線性映射的定義如下所示:

將樣本通過非線性映射φ映射到高維空間RF中,其中: 樣本數(shù)據(jù)矩陣為Xφ=(φ(x1),φ(x2),…,φ(x n))。

將訓練樣本映射到高維空間后,采取數(shù)據(jù)中心化,即映射后的協(xié)方差矩陣

式(2)的特征值為λ,則Cφw=λw,其中w是特征向量。對于所有滿足λ≠0的特征向量w,它位于所在的空間中。存在系數(shù)a i(i=1,2,…,n)滿足

代入式(2)中,得

定義n×n的核矩陣K,且

代入式(5)得出:

即nλa=Ka。λ1,λ2,…,λn是式(7)的特征值,a1,a2,…,a n是對應的特征向量。這時只需簡單地計算核函數(shù)K(x i,x j)就可以進行核主成分分析,而不需要具體了解非線性映射φ的形式。

核主成分分析常用的核函數(shù)有線性核函數(shù)、多項式核函數(shù)、Sigmoid核函數(shù)和高斯核函數(shù)[19]。高斯核函數(shù)可以將樣本映射到一個更高維的空間,對于多項式核函數(shù)來說,高斯核函數(shù)需要確定的參數(shù)較少;線性核函數(shù)只能用于線性可分的情況;Sigmoid核函數(shù)的表現(xiàn)與高斯核函數(shù)類似[20]。因此,本文選取的核函數(shù)為高斯核函數(shù),高斯核函數(shù)如下所示:

式中:x i、x j為樣本點;σ是高斯核函數(shù)半徑。

2.2 改進的KNN算法

傳統(tǒng)的KNN算法計算開銷大,等同對待各個特征項和近鄰樣本,因此導致分類準確率低[16]。本文通過引入特征選擇的思想對傳統(tǒng)KNN算法進行改進,并將改進的KNN算法應用到蒙古族音樂分類中。

該算法的改進思路為: 當提取的特征輸入到KNN分類模型中,對于KNN來說,由于其同等對待各個特征項和近鄰樣本,導致每一維度的特征對其距離的貢獻都相同。若存在某n維特征對音樂分類無影響,那么它們的存在則會降低音樂分類的準確率?；谝陨霞僭O,設原始輸入的特征集合為I,是否存在一個I的子集I′,利用I′里的特征在KNN分類算法上能夠達到更好的分類效果,從而提高KNN算法的分類準確率。因此,本文通過引入特征選擇對KNN算法進行改進。改進KNN使得KNN可以選擇出對分類算法更有價值的特征屬性。同時,也可以選擇真正相關的特征來簡化模型,使得數(shù)據(jù)生成過程更容易理解。

首先,從完整的特征集中隨機生成一個特征子集,然后使用評價函數(shù)對特征子集進行評價,比較評價結果與停止準則,如果評價結果優(yōu)于停止準則,則停止;否則,繼續(xù)生成下一組特征子集。繼續(xù)保持特征選擇,所選出來的特征子集需要去驗證它的有效性。

本文的改進KNN基于特征選擇的過程包括4個部分: 生成子集、采用評價函數(shù)、停止準則和驗證結果。

1) 生成子集是指搜索特征子集,然后為評價函數(shù)提供生成好的特征子集。

2) 評價函數(shù)是用來評價特征子集質量的標準,本文中采用準確率來評價該生成子集的質量。

3) 停止準則,其決定什么時候停止搜索,即結束算法的執(zhí)行。本文的改進算法設定的停止準則為評價次數(shù),設置算法需要運算多少次,用于規(guī)定隨機搜索的次數(shù),尤其當算法運行的結果不穩(wěn)定的情況下,通過若干次的運行結果找出其中穩(wěn)定的因素。當達到設定的搜索次數(shù)后,停止搜索。

4) 驗證結果,驗證所選特征子集在驗證數(shù)據(jù)集中是否有效。

改進KNN的算法步驟如下:

1) 設訓練集為X={x i|i=1,2,…,n},對訓練集進行歸一化處理。

2) 初始化Best_Score=0,Local_Score=0。

3) 設原始的定義特征屬性集合為I={I1,I2,I3,…,I M}。

4) 設最佳的特征屬性集合為Best_I={I1,I2,I3,…,I N},N≤M。

5) 將訓練集X={x i|i=1,2,…,n}進一步劃分,用于尋找最佳特征集合。

6) 隨機創(chuàng)建一個子集Local_I={I1,I2,I3,…,I L}。

7) 生成步驟6)中隨機從特征集合選取N個特征屬性的特征子集。

8) 并對各個特征子集Local_I={I1,I2,I3,…,I L}運行分類算法。

9) 使用部分數(shù)據(jù)集X′={x i|i=1,2,…,m}進行測試,其中m＜n。

10) 從中選取分類準確率最高的特征子集作為最佳特征子集的集合,計算樣本點之間的距離公式如下:

式中:p為可變參數(shù);x k和y k分別是x和y的第k個屬性值(分量)。當p=1時,式(9)被稱之為曼哈頓距離(Manhattan distance);當p=2時,式(9)被稱之為歐式距離(Euclidean distance);當p→∞時,式(9)被稱之為切比雪夫距離(Chebyshev distance)。

11) 更新Best_I=Local_IifBest_Score=Local_Score。

12) 利用步驟7)選取的特征子集對所有數(shù)據(jù)集進行訓練和測試。

13) 得到一個最優(yōu)的特征子集Best_I,最終完成分類預測工作。

2.3 KPCA-FSKNN分類方法

傳統(tǒng)的線性降維方法在提取特征時,存在樣本間非線性相關性有可能會丟失的問題。而核主成分分析利用核化的思想,一方面可以將特征映射到高維空間,便于捕捉特征與類別的非線性關系;另一方面,最終的特征之間為正交關系,距離計算可以更加有效。針對之前所描述KNN分類算法受某些特征影響導致分類準確率降低的問題,結合核主成分分析的優(yōu)勢,本文對KNN算法進行了改進,可以有效尋找到最佳特征子集,從而提高分類準確率。綜上所述,本文構造了一種融合核主成分分析與改進的KNN算法的分類方法,即KPCA-FSKNN分類方法,并將其應用到蒙古族音樂分類中。

KPCA-FSKNN分類方法主要分為兩個階段: 核主成分分析特征轉換階段和改進KNN算法分類階段。兩階段的過程具體描述如下:

1) 核主成分分析篩選特征。首先通過核主成分分析可以將特征映射到高維空間然后降維的原理,將提取到的共26維特征的組合用來描述一首音樂的特征信息,隨后將其升為30維,最終顯示的特征為正交關系,從而更有效地進行KNN距離計算。

2) 特征選擇?；谔卣鬟x擇的KNN通過設定子集范圍,可以更好地搜索特征子集。由于搜索全部子集的開銷很大,而且子集太大,接近全集,那么計算量則偏大,導致運行速度變慢,達不到搜索的效果;反之,若子集大小太接近0則會丟失過多信息,則找不到好的子集。因此,實驗設置迭代次數(shù)為2 000次的效果最佳,測試2 000個隨機集合。最后驗證特征子集,為了進一步評估子集的合理性,通過多次計算交叉驗證是否為最優(yōu)特征子集。先將訓練集劃分,在訓練集上搜索達到最優(yōu)的子集,再到測試集上測試,最后2 000次搜索后結束。上述過程重復10次,取這10次運行結果的平均值,得出最終的特征子集分類結果。

KPCA-FSKNN分類方法具體實現(xiàn)的流程如圖1所示,實現(xiàn)的偽代碼如下所示:

圖1 KPCA-FSKNN方法流程圖Fig.1 Flow chart of KPCA-FSKNN method

3 實驗結果與分析

3.1 實驗數(shù)據(jù)

實驗中使用的數(shù)據(jù)集是公開數(shù)據(jù)集GTZAN與蒙古族音樂資源數(shù)據(jù)庫[3]中的蒙古族音樂的組合,實驗數(shù)據(jù)集主要包括11類不同曲風音樂,每類包含100首,共1 100首音樂。由于公開數(shù)據(jù)集GTZAN中每段音頻都為30 s時長,為了確保實驗的有效性,蒙古族音樂同樣從音樂中間的人聲部分截取30 s的音頻,實驗中所有音頻均采用統(tǒng)一格式(.wav)。

特征集通過特征提取實驗預處理輸入每段長30 s的音頻信號,分析提取出的3類特征主要包括譜質心、RMS(Root Mean Square)能量包絡、帶寬、譜滾降、色度特征、過零率、前20個MFCC,總共26個特征的組合來描述一首音樂的特征信息,對訓練數(shù)據(jù)的每一列進行歸一化預處理。

3.2 實驗結果與分析

為了評價本文提出的KPCA-FSKNN分類方法的有效性,與以下幾種方法進行了對比實驗。

1) 傳統(tǒng)分類方法: 在本文中的音樂數(shù)據(jù)集下訓練得到的傳統(tǒng)KNN、隨機森林(Random Forest,RF)和SVM分類模型用于蒙古族音樂分類(Our group 1)。

2) 基于PCA與SVM、KNN分類模型融合的方法用于蒙古族音樂分類(Our group 2、Our group 3)。

3) 基于核主成分分析與SVM、KNN分類模型融合的方法用于蒙古族音樂分類(Our group 4、Our group 5)。

4) 本文提出的KPCA-FSKNN方法用于蒙古族音樂分類(Our group 6)。

圖2給出了針對傳統(tǒng)分類模型的蒙古族音樂分類結果。本文首先驗證了KNN、RF和SVM的分類效果對比,數(shù)據(jù)顯示KNN具有更高的分類效果,其平均準確率達到了69.83%,其余兩個分類模型的平均準確率分別為53.87%、62.21%。由圖2可以看出,KNN在蒙古族音樂數(shù)據(jù)上的分類性能較SVM與RF模型表現(xiàn)得更好,但分類效果仍不理想,因此,本文主要針對KNN分類模型存在的問題,從特征的角度出發(fā),對KNN分類模型進行改進,通過驗證蒙古族音樂分類的準確率得出改進后模型的好壞。

圖2 傳統(tǒng)分類模型的蒙古族音樂分類準確率Fig.2 Accuracy of Mongolian music classification based on traditional classification model

表1給出了在上述不同分類方法下的音樂分類結果。由表1可以看出: 相對于傳統(tǒng)方法,1) 核主成分分析降維相對于主成分分析降維更適用于蒙古族音樂分類;2) 降維與KNN分類器融合的效果和SVM分類器融合效果相比,融合KNN分類器的分類效果更好;3) 本文提出的核主成分分析降維與基于特征選擇改進的KNN分類器融合的方法可以獲得更好的分類效果,這說明了融入特征選擇的必要性,在對蒙古族音樂進行分類時,將特征選擇考慮進去可以顯著提升蒙古族音樂分類的準確率。

表1 不同分類算法準確率的比較Tab.1 Comparison of accuracy of different classification algorithms

表2展示了實驗在搜尋子集時特征選擇的結果。為達到搜索子集的效果,子集范圍為1/2開始搜索并逐漸遞減,當子集維度選取為10～15維度時,分類準確率逐漸遞減;當子集維度選取為7～10維度時,分類準確率逐漸遞增。實驗結果表明,當子集范圍為1/3時,蒙古族音樂分類的準確率相對較好。

表2 特征選擇結果Tab.2 The results of feature selection

為了進一步驗證融合后KNN算法的有效性,表3給出了在不同鄰居數(shù)量K下,傳統(tǒng)KNN、PCAKNN、KPCA-KNN和本文提出的KPCA-FSKNN方法對蒙古族音樂分類的準確率。本文提出的KPCAFSKNN方法由于要尋找最佳特征子集,從而能達到較好的分類準確率,因此,實驗中將本文所提方法的分類結果隨機運行10次,交叉驗證計算平均值得出其分類準確率。

對表3進行分析可知:

表3 不同K下,4種方法對蒙古族音樂分類的準確率Tab.3 Accuracy of four methods for Mongolian music classification under different K

1) 特征降維前,不同K下,使用傳統(tǒng)KNN分類方法對蒙古族音樂分類的準確率較低。

2) 相對于PCA-KNN,KPCA-KNN對蒙古族音樂分類的準確率得到了提高,該組實驗結果驗證了利用KPCA提取的特征可以更加準確地反映蒙古族音樂的曲風類型。

3)PCA-KNN、KPCA-KNN整體上的準確率高于傳統(tǒng)KNN算法,說明引入降維方法可以提高對蒙古族音樂分類的準確率。相對于KPCA-KNN,KPCA-FSKNN方法考慮了特征選擇,因此,對蒙古族音樂分類的準確率得到了進一步的提升,該組實驗方法集成了核主成分分析與改進的基于特征選擇的KNN分類方法的優(yōu)點,能夠更準確地劃分蒙古族音樂的曲風類型。

此外,為了更進一步說明本文所提方法的有效性,在該數(shù)據(jù)集中測試了其他音樂曲風類別的實驗結果,如表4所示。從表4中可以看出,采用KPCA-FSKNN方法對其他非蒙古族音樂分類的準確率也得到了有效的提升。

表4 對其他類別音樂分類的準確率Tab.4 Accuracy of classification of other categories of music

4 結語

本文對蒙古族音樂數(shù)據(jù)分別選取了代表時域特征、頻域特征和倒譜域特征的主要特征,上述3個領域特征包括頻譜質心、帶寬、RMS能量包絡、譜滾降、過零率、色度特征以及MFCC作為衡量蒙古族音樂的特征參數(shù)。通過核主成分分析將特征映射到更高維空間,隨后降維;利用本文改進后的基于特征選擇的KNN算法從中進行特征選取,尋找到最佳特征子集;最后,將核主成分分析與改進的KNN進行融合,提出了KPCA-FSKNN分類方法。最終實驗表明,本文提出的KPCA-FSKNN分類方法,對蒙古族音樂進行分類時可以得到一個較高的準確率。通過與文中列出的其他分類方法的對比可以得出結論,本文提出的KPCAFSKNN方法優(yōu)于傳統(tǒng)KNN、SVM和其他分類算法,使蒙古族音樂分類的準確率得到了大幅度的提升,同時也驗證了該方法對其他音樂分類的有效性。本文提出的KPCA-FSKNN方法能夠在一定程度上將蒙古族音樂從海量的音樂中篩選、分類和整理出來,是蒙古族音樂分類的一種可行方法。