徐秀芳徐森徐静安晶

摘 要：提出一种新颖的基于谱聚类的音频聚类算法，首先对音频数据进行预处理，得到三维音频向量，然后根据向量之间的距离计算音频相似度，最后设计谱聚类算法获得音频数据聚类结果。在网易云音乐数据上的对比实验表明，与Kmeans算法和快速查找密度峰值聚类算法相比，该算法获得的聚类结果更加优越。

关键词关键词：音频聚类；音频特征；谱聚类；Kmeans；聚类分析

DOIDOI：10.11907/rjdk.162088

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011003603

基金项目基金项目：国家自然科学基金项目（61105057）；江苏省自然科学基金项目（BK20151299）；江苏省科技支撑计划（社会发展）项目（BE2014679）；江苏省政策引导类计划（产学研合作）—前瞻性联合研究项目（BY2015057-33， BY2016065-01）

作者简介作者简介：徐秀芳（1973-），女，江苏盐城人，硕士，盐城工学院信息工程学院高级实验师，研究方向为机器学习和数据挖掘；徐森（1983-），男，江苏盐城人，博士，盐城工学院信息工程学院副教授，研究方向为数据挖掘、智能信息处理和深度学习；徐静（1981-），女，江苏盐城人，盐城工学院信息工程学院副教授，研究方向为网络安全和智能信息处理；安晶（1982-），女，江苏盐城人，博士，盐城工学院机械优集学院副教授，研究方向为数据挖掘、聚类分析。

0 引言

随着互联网的快速发展，音乐创作速度也随之迅速提高，如何将众多音频进行分类并推荐给用户成为一个关键问题[13]。早期的音频分类方法通常是唱片公司工作人员为其添加类型标签供买家选择，或者是由专门收录音乐的网站添加标签供用户浏览检索。然而由于不同人对同一首歌曲的感觉可能有差异，因此可能给同一首歌添加了不同标签。显然对用户而言，这种分类方式不够合理。如果通过机器学习的方式自动将音频分类并根据用户的喜好推荐音乐，必然会在很大程度上提升音乐推荐软件的用户体验。

聚类分析是机器学习中常用的一种数据挖掘工具，可以自动将数据进行归类，使相似数据归为同一类型，而不同部分归为不同类型，并根据类型不同找出类型间的隐含关系[4]。在诸多聚类算法中，谱聚类算法建立在图论中的谱理论基础上，具有能在任意形状的样本空间上聚类且收敛于全局最优解的特点[5]。

考虑到谱聚类算法的诸多优点，本文首次引入谱聚类对音频数据进行聚类分析，并将聚类结果与其它聚类方法进行比较。结果显示，利用谱聚类算法对音频数据进行聚类分析是行之有效的，较之于其它算法，谱聚类的聚类效果更为理想。

1 音频数据预处理

如果想要得到一个比较理想的聚类结果，预处理方法尤为重要。不仅需要大量先验知识，还需要根据聚类的对象特征选择不同算法。本文的音频聚类主要是根据音频的情绪特征进行分类，因此预处理主要提取了能表示音频情绪的特征。

关于音频的情绪特征，Thayer[6]提出了一种AV模型，即建立一个平面直角坐标系，以V（Valence）为横轴，以A（Arousal）为纵轴。横轴的坐标值反映了积极性大小，纵轴的值反映了音频的安静程度。该模型直接将音频清晰地划分为4个区域，分别对应了快乐、紧张、悲伤以及平静4大情绪类别。AV模型的坐标系如图1所示。

根据Thayer的模型，本文将纵轴的影响因素归为每帧功率和序列方差的对数值，横轴的影响因素归为帧频谱图峰值最大处的频率序列方差，即：A=log（var（w）），V=var（fd），其中w为每帧的功率和序列，fd为两帧频谱差序列中最大值对应的频率序列，var为方差函数。此处fd取频率的差值作为主要特征，主要是考虑到人对变化的频率比不变的频率更敏感。例如，在听歌时，往往会忽略背景音乐中的鼓点部分，而专注于歌曲中变化的部分。

另外，本文增加一个Z轴，Z=log（mean（w）），即功率和的平均值作为影响音频的第3个特征。对于每首音乐，有向量（a，v，z），据此画出496首音乐的3维分布图像，如图2所示。

可以看出，左上部分频率变化很小，而功率变化很大，此类音频可以归为摇滚、慢摇等类别；而左下部分频率变化与功率变化都很小，此类音频可以归为轻音乐、纯音乐等类别；而右上部分则属于频率变化与功率变化都很大的音频，这类音频属于DJ、电音等类别。

2 聚类分析

音频预处理后每个音频特征点处于一个三维空间中，在音频相似度的计算上取数据点间的欧式距离，距离越近相似度越高，反之则越低。

聚类算法有很多种，通常根据数据集的特征进行选取，本文采用以下聚类算法进行研究。

2.1 K均值聚类

K均值算法由于实现简单，时间和空间复杂度较低，而且对很多简单的聚类问题可以得到令人满意的结果，因此成为了最常用的聚类算法。算法首先假设每个聚类的均值是固定已知的，问题变为如何为每个样本选择加入一个聚类，使类内距离准则最小。该算法的困难在于如何求出每个聚类的均值，因为在知道每个聚类包含哪些样本之前无法求得样本均值，聚类均值也只能根据该聚类中所有的样本求得。通常，先随机选择k个初始值，然后将每个数据点放入最近的类中，求得每个聚类的均值，根据这些均值再次对数据点进行划分。多次迭代之后，使得聚类中心不再改变，此时的聚类结果为类内距离准则最小的一个较优解。

尽管K均值聚类算法已被证明可以通过有限步骤收敛，但是最终获得的是局部最优解，不能保证类内距离为最小值。另外，根据初始值选择不同，K均值聚类也会收敛于较差的局部极小解，加上k的设定如果与实际问题有偏差，通常很难得到较好的聚类结果。

针对这些问题，也可以选择事先对Kmeans算法进行优化。例如，根据先验知识选取较好的k值，初始值选取k个彼此距离最大的点，选择适当的距离函数等。

2.2 快速查找密度峰值的聚类算法

根据聚类的目标，类间不相似、类内相似的特点，Rodriguez[4]假设每个类的中心点周围都是密度比其低的点，同时这些点又距离该聚类中心最近，据此提出了一种新型算法——快速查找密度峰值的聚类算法，并发表在著名的Science杂志上。

算法的基本思想是：首先计算每个点所处的密度值，这里的密度值指所有与该点距离小于dc的点个数。其中dc是预先设定的阈值，文中使用的是所有点距离中第2%个点的距离大小；再根据每个点的局部密度算出每个点的距离，即比该点密度大的所有点中与该点距离的最小值；关于噪点的剔除，对一个类中的每个点，与其它类中的点计算距离，找出所有满足距离大于dc的距离的最小值，即在该类中找出一个与其它类距离最近的点。接下来视该类中所有小于该点密度的点为噪点，并将其剔除，最后得到的即为聚类结果。

2.3 谱聚类算法

与大部分聚类算法不同，谱聚类算法将聚类分析问题转化为图分割问题，将数据元素构成的无向加权图划分为几个子图，使得分割代价最小，以此达到聚类的目的[5]。

谱聚类的基本步骤为：① 输入数据生成图的邻接矩阵；②归一化拉普拉斯矩阵；③计算最小的k个特征值和对应的特征向量；④用K均值对前k个特征向量进行聚类。

谱聚类的优点在于，如果直接使用K均值算法对无向图进行聚类分析，特征向量的选取并没有理论基础。而谱聚类引入拉普拉斯矩阵，则为图的分割增加了物理上的意义，即对高维空间降维，求拉普拉斯矩阵的特征向量即等价于对高维空间的降维处理。

3 聚类结果比较

本文将第2节介绍的3种聚类方法获得的结果和原始音乐数据的类型分布图进行对比，原音频类型为网易云音乐的歌单类型。例如，某歌单被命名为轻音乐，则将该歌单的所有音乐都设置为轻音乐类型；如果歌单类型为摇滚，则将该歌单的所有歌曲均设为摇滚。最后将每个点着色，画在二维平面上，即为类型分布图。图3是469首音乐的类型分布图。其中正三角为摇滚、rap等兴奋型音乐；倒三角为电音、DJ类的音频；圈表示轻音乐和舒缓类型的音乐。因为摇滚和电音本身的特性，将其归为一类，这样原始音频数据可以看成是包含2个簇（k=2）。3种聚类算法获得的结果分别如图4～图6所示。由图可见，与其它聚类方法相比，谱聚类算法获得的聚类结果与音频数据的实际分布情况更为接近。

具体而言，3种聚类算法的聚类结果与真实结果的对比情况如表1所示。从表1可以看出，快速查找峰值密度算法的类别区分较为准确，但是排除噪点过多；Kmeans算法不剔除噪点，但是聚类效果不太理想；谱聚类的聚类效果在3者中最为理想。

4 结语

本文提出了一种基于谱聚类的音频聚类算法，首先对音频数据进行预处理，得到三维音频向量，然后根据向量之间的距离计算音频相似度，最后根据谱聚类算法获得聚类结果。对比实验验证了基于谱聚类算法的音频聚类的有效性。根据本文的研究，可以将音频聚类算法应用到音乐推荐中，将用户喜欢的某一类型音乐中相似度较高的音乐推荐给用户，能很大程度上提升音乐播放软件的用户体验。

参考文献：

[1] 杨莘，舒鹏.一种音乐速度与节拍类型的自动检测算法[J].数字技术与应用， 2009（8）：3941.

[2] 李志军，尹霞.基于ACF和AMDF的基音检测改进算法[J].电声技术， 2011（1）：5052.

[3] 廖松博， 何震瀛.HDCH：MapReduce平台上的音频数据聚类系统[J].计算机研究与发展， 2011， 48（S3）：472475.

[4] RODRIGUEZ，ALEX，ALESSANDRO LAIO.Clustering by fast search and find of density peaks[J].Science， 2014（6191）：14921496.

[5] ULRIKE VON LUXBURG.A tutorial on spectral clustering[J].Statistics and Computing， 2007（4）：395416.

[6] THAYER R E.The biopsychology of mood and arousal[M].New York：Oxford，1989.

（责任编辑：黄 健）