一种二次加权的KNN音乐流派分类方法

摘要

一种二次加权的KNN音乐流派分类方法，在传统的KNN算法的近邻计算和类属判断两个步骤上进行了加权，分别解决了传统KNN算法认为每个属性的作用都是相同的，忽略其与类别的相关程度的问题和类属判断策略在判断待分类样本类属时仅考虑了每个类别中最近样本数目，而忽略了各类中近邻和待分类样本之间相似性的差异，并将其应用到音乐流派分类工作中。本发明的二次加权的KNN音乐流派分类方法比传统KNN算法在音乐流派分类方面有着更高的分类准确率，并且对与音乐类域的交叉或重叠较多的待分样本集来说，分类效果更佳。

说明书

技术领域

本发明涉及音乐分类方法，具体涉及一种二次加权的KNN音乐流派分类方法。

背景技术

KNN(K-Nearest Neighbor)是一种经典的分类算法，然而和一般性的分类算法不同，KNN算法是一种懒惰学习算法，它与其他的分类算法存在着显著的不同，像SVM，HMM等分类算法都是先对训练集数据进行机器学习，建立分类模型，然后在分类模型的支持下进行分类工作。KNN是一种被动的分类过程，边测试边训练建立分类模型，它基于统计方法，先为测试样本在特征空间中找到k个最近邻样本，然后遵循少数服从多数的原则，根据k个最近邻中多数样本的类别来确定测试样本的类别。

KNN算法的优点主要表现在原理简单、实现方便、支持增量学习。能对超多边形的复杂决策空间建模，并且对于类域交叉的情况有着较好的分类效果。但其存在的问题主要体现在两方面，一是传统KNN算法进行相似性度量时，认为每个属性在距离计算的过程中作用都是相同的，而忽略其与类别的相关程度的问题，因而影响分类的准确率，二是类属判断过程中只考虑了每类中近邻的个数，而忽略了各类中近邻和待分类样本之间相似性的差异。

KNN分类器多用于文本分类，很少有研究者将其用于音乐分类。然而研究发现KNN对于类域的交叉或重叠较多的待分样本集来说，较其他方法更为适合，而该现象在音乐流派分类中尤为突出。

发明内容

本发明从音乐流派分类的角度出发，创新的提出了一种二次加权的KNN音乐流派分类方法，主要针对传统KNN分类算法的两个问题：一是传统KNN分类算法认为在分类过程中每个属性的对分类的决定作用都是相同的，忽略了其与类别的相关程度，这样在计算相似度时会出现误差；二是传统的类属判断策略在判断待分类样本类属时仅考虑了每个类别中最近样本数目，而忽略了各类中近邻和待分类样本之间相似性的差异。提供了一种二次加权的KNN音乐流派分类方法，具体技术实施方案如下：

本发明的一种二次加权的KNN音乐流派分类方法，具体步骤如下：

步骤一、音乐描述及特征提取；

本步骤总结了音乐流派分类领域中主要的声学特征量，选择了短时能量、短时能量均方值、每秒音符初始数量、节拍速度、高频能量、频谱质心、平整度、梅尔倒谱系数、梅尔倒谱系数差分、过零率、音高、无谐性、音调这13个能充分表征音乐的力度、节奏、音色、音高和音调五大要素的声学特征量，共59维对音乐进行描述，然后使用Mirtoolbox工具包对这些特征量进行提取；

步骤二、将数据集用59维特征量矩阵表示；

将数据集中的1000首歌曲，每首歌曲都按照步骤一中介绍的特征提取方法提取其59维特征，得到一个59列1000行的特征矩阵；

步骤三、使用粗糙集理论计算决策属性对条件属性的属性依赖度k＝γ_p(Q)，将k＝0的属性去掉，形成特征选择后的特征向量矩阵；

在计算近邻的过程中，先计算决策属性对每个条件属性的属性依赖度，如式1所示，然后去掉属性依赖度等于零的特征；

步骤四、计算未知样本x和每个训练样本y_j的距离；

根据公式2计算未知样本x和每个训练样本y_j的距离；

步骤五、在y_j中选择与x距离最小的k个最近邻样本；

步骤六、类属判断；

类属判断时首先统计k个最临近样本在每个类中出现的次数，如果在次数最大的类中近邻数目超过k值的60％，则直接按照原始KNN的类属判断方法判断类别，如果没有超过60％，则在k出现的所有类中通过样本的加权距离和进行类属判断，如式3，

步骤七、可扩展性分析；

该方法也适用于分布式计算方式,由于该算法对各特征的权重计算是一次性的，每个待分类样本计算距离时不用重复计算。曲库中的样本按计算结点数n平均分为若干子集L₁-L_n分布到各结点上。对每个待分类样本进行计算时，由各结点并行计算，计算过程中选出k个最近邻,各结点的计算结果合并后有k*n个最近邻，再在其中选取k个最近邻用于确定待分类样本的分类。

本发明的一种二次加权的KNN音乐流派分类方法,该方法的先进性如下：一是改进了传统KNN算法进行相似性度量时，认为每个属性在距离计算的过程中作用都是相同的，而忽略其与类别的相关程度的问题；二是改进了传统KNN算法类属判断过程中只考虑了每类中近邻的个数，而忽略了各类中近邻和待分类样本之间相似性的差异；三是该方法在容易产生类域交叉的音乐流派分类情况下，可以提高分类准确率。

附图说明

图1是分布式二次加权的KNN方法示意图，图2是传统KNN和二次加权的KNN方法分类准确率比较图，图3是SVM和二次加权的KNN分类准确率比较图。

具体实施方式

具体实施方式一：本实施方式的一种二次加权的KNN音乐流派分类方法是由下列步骤实现的：

步骤一、音乐描述及特征提取；

本步骤总结了音乐流派分类领域中主要的声学特征量，选择了短时能量、短时能量均方值、每秒音符初始数量、节拍速度、高频能量、频谱质心、平整度、梅尔倒谱系数、梅尔倒谱系数差分、过零率、音高、无谐性、音调这13个能充分表征音乐的力度、节奏、音色、音高和音调五大要素的声学特征量，共59维对音乐进行描述,见表1，然后使用Mirtoolbox工具包对这些特征量进行提取；

步骤二、将数据集用59维特征量矩阵表示；

设未知样本集X＝(x₁,x₂,...,x_n)，训练样本集Y，Y＝(y₁,y₂,...,y_n)，将训练集用59维特征量矩阵表示；

1、生成特征矩阵：将数据集中的1000首歌曲，每首歌曲都按照步骤一中介绍的特征提取方法提取其59维特征，得到一个59列1000行的特征矩阵；

2、形成训练集与测试集：采用4分交叉试验法，将样本集中的数据分为4等份，取其中的3份为训练集，1份为测试集，轮流进行循环测试，测试算法准确率，最后取准确率的平均值为测试结果；

3、数据归一化：由于用于表示各特征量由的数据单位不一致，因而须对数据进行归一化处理，样本集中的数据统一归一化到[-1,1]区间，归一化采用MATLAB自带的归一化函数mapminmax，将训练集和测试集归一化到[-1,1]区间；

步骤三、使用粗糙集理论计算决策属性对条件属性的属性依赖度k＝γ_p(Q)，将k＝0的属性去掉，形成特征选择后的特征向量矩阵；

粗糙集理论是一种利用知识库中的近似知识对不精确或不确定的未知知识进行刻画的方法，它的一种重要的应用是可以去除冗余属性和冗余数据；

粗糙集理论中属性依赖度的概念：令K＝(U,R)为知识库，且当k＝γ_p(Q)＝card(pos_p(Q))/card(U)；x∈U/ind(P)时，称知识Q是k度依赖于P的(0≤k≤1),记作这里card(pos_p(Q))表示根据属性P,U中所有一定能归入Q的元素数目。当k＝1,称Q是完全依赖于P的；当0＜k＜1，称Q是粗糙(部分)依赖于P的；当k＝0，称Q是完全独立于P的。属性依赖度可理解为属性对对象分类的能力。当k＝1时，论域中的全部元素都可通过P划入U/Q的初等范畴；当k≠1时，只有属于正域的元素才可以通过P划入知识Q的范畴；而当k＝0时，则论域中没有元素能通过P划入Q的初等范畴；

本步骤引入粗糙集理论中的属性依赖度主要起到两方面的作用，一是使用粗糙集理论中的属性约简，起到特征选择的作用，然后再将属性依赖度作为权重引入KNN算法样本之间距离的计算公式；

在计算近邻的过程中，先计算决策属性对每个条件属性的属性依赖度，如式1所示，然后去掉属性依赖度等于零的特征；

步骤四、计算未知样本x和每个训练样本y_j的距离；

将步骤三计算的属性依赖度作为各特征的权重引入KNN算法的近邻距离计算公式，这样传统的KNN算法中计算两个样本向量x_i和y_i之间距离的计算距离公式就由式4转变为式2，

步骤五、在y_j中选择与x距离最小的k个最近邻样本；

步骤六、类属判断；

在进行类属判断过程中，如果为未知样本x_i找到的近邻的数目在几种分类中的分布较接近，那么在分类时就不能只考虑近邻的个数，而要将未知样本与训练样本之间的距离因素也考虑进来。设最近邻个数为k，y₁,y₂,...,y_k代表为未知样本x找到的k个最近邻，根据x到y₁,y₂,...,y_k的距离值的从小到大，依次为参与类属判断的样本赋予从高低的权重，各权重W_i计算如公式5所示；

W_i＝1/dist(x,y_i)(5)

类属判断时首先统计k个最临近样本在每个类中出现的次数，如果在次数最大的类中近邻数目超过k值的60％，则直接按照原始KNN的类属判断方法判断类别，如果没有超过60％，则在k出现的所有类中通过样本的加权距离和进行类属判断，如式3，最后选择Ci值最大的类标号作为未知样本的类标号；

步骤七、可扩展性分析；

该方法分类时间主要耗费在计算样本向量间距离，该部分的时间复杂度是O(n)，说明计算时间随着样本数目的增加呈线性增长。计算待分类样本与歌曲库中1000首歌曲的距离所用时间是0.0573秒，随着歌曲库中歌曲数目的增多，按线性增长预测，100万首样本计算所需时间约53.7秒，1000万首歌曲计算时间约为9分钟。分类工作主要在线下通过离线计算完成，计算时间可以被系统接受；

该方法也适用于分布式计算方式。由于该算法对各特征的权重计算是一次性的，每个待分类样本计算距离时不用重复计算。曲库中的样本按计算结点数n平均分为若干子集L₁-L_n分布到各结点上。对每个待分类样本进行计算时，由各结点并行计算，计算过程中选出k个最近邻。各结点的计算结果合并后有k*n个最近邻，再在其中选取k个最近邻用于确定待分类样本的分类，见图1。

实验结果：

1、二次加权的KNN音乐流派分类准确见表2，其中，两类分类的最高准确率可达100％，最低准确率为59％，平均准确率为87.15％，分类准确率随着分类数目的增多而下降，当分类数目达到10类时，分类准确率为59.16％。

2、传统KNN算法和二次加权的KNN进行音乐流派分类，分别将样本集中的数据分为2-10类，各算法的分类准确率见图2(图2中用DW-KNN表示二次加权的KNN)。可以看出,二次加权的KNN的分类准确率高于传统KNN算法,并且分类数目越多，分类准确率的差距越明显，这说明二次加权的KNN在分类数目增多，类别间差异不够明显的情况下有着更好的分类准确率。

3、分别使用传统KNN和二次加权的KNN方法进行音乐流派分类，各方法的计算效率见表3。因为二次加权的KNN首先要使用粗糙集计算各特征量权值，然后在确定类属时还要计算距离，所以计算时间必然比KNN要长。传统KNN算法的计算时间主要花费在计算与每个样本的距离并在此过程中找到k个近邻，所以，在样本数为n的情况下，算法的时间复杂度为O(n)。二次加权的KNN的时间复杂度分为两部分，计算权重的时间复杂度和分类时间复杂度。计算权重在整个分类过程中只计算一次,且可以通过离线计算完成,所以时间复杂度可以忽略不计。分类过程与传统KNN相比只是在计算距离的过程中增加了权重，时间复杂度没有改变。

4、通过SVM的实验发现，SVM分类准确率较低的情况发生在类别之间差异不明显，以及类域有交叉的情况下。该实验在SVM分类准确率较低的分类上使用二次加权的KNN方法进行了分类，发现二次加权的KNN比SVM在某些两类和三类上分类准确率高，如爵士和雷鬼，雷鬼和摇滚，蓝调和说唱，雷鬼、摇滚和爵士，见图3。事实上许多音乐网站对这些类型的分类也确有交叉。结果可以看出，在几类容易产生类域交叉的情况下，二次加权的KNN(图3中用DW-KNN表示)分类的准确率高于SVM。

表1音乐流派自动分类声学特征表

表2二次加权的KNN音乐流派分类准确率

表3二次加权的KNN与传统KNN算法时间复杂度比较