基于状态转移的奖励值音乐推荐算法

摘要

本发明公开了一种基于状态转移的奖励值音乐推荐算法，与现有技术相比，本发明针对当前音乐推荐算法的不足，本发明以巧妙引入奖励值的概念，将音乐顺序纳入研究范围，将用户选择怎样的音乐列表视作马尔可夫决策过程，推荐音乐列表的每一首音乐，都视作决策过程中状态的变化，因此，不同状态会对当前局面产生不同的奖励值，算法选择奖励值最大的状态序列，在此即为奖励值最大的音乐列表。同时，将用户个人历史数据与整体用户数据做均衡，优化推荐效果，创新地加入音乐流行度和用户从众度，提出了基于状态转移的奖励值算法，具有推广使用的价值。

说明书

技术领域

本发明涉及计算机及音频技术领域，尤其涉及一种基于状态转移的奖励值音乐推荐算法。

背景技术

听音乐已成为大众娱乐的一种重要方式，随着“信息过载”问题的日益严重，各大公司平台纷纷推出了针对音乐的推荐系统,现有传统的推荐系统并不能保证用户体验，用户对精准推荐的需求仍是强烈。随着互联网技术的发展以及个人智能设备的普及，“信息过载”[1]问题日益严重。据估计，Facebook每日有3000万张以上的照片从后台被上传，后台日志数据每天就能生成300TB；国内的某电子商务网站，每天达成的交易在千万笔级别，每日日志文件超过50TB[2,3]。面对如此情况，各大平台纷纷推出搜索功能，但在某些情况下，用户并没有明确的搜索对象，例如，想看一部电影或者听几首歌，但没有明确要看哪一部或者听哪一首，这时，搜索技术就不能满足用户此时需求，在此情景下，推荐算法应运而生，极大便利了用户在此类情景下的信息选择。推荐算法在社交、电子商务、影音娱乐、新闻筛选等领域得到了广泛应用，并在市场范围内有不俗的表现[4]。

目前的推荐算法，无论是基于内容的推荐、协同过滤亦或是混合推荐，利用用户的历史数据，分析用户的喜好，找到邻近用户，预测用户未来的选择。Liebman E等人[5]在强化学的框架中，基于音乐的35维特征向量提出一种搜索方法，每一个声学特征又被量化为100段，加入了音乐列表奖励机制，根据反馈值推荐音乐列表。该方法将每一类特征统一量化为100段，可能导致某些维度上会出现数据稀疏性问题，同时该模型忽略了特征权重；Sánchez-Moreno D等人[6]将播放计数引入到CF算法中，建立用户的模糊集群，该算法基于用户播放次数和艺术家特点来度量用户喜好，这种度量准则不够全面。总体来讲，前人音乐推荐算法存在以下四个方面的问题：一，基于内容的推荐单一地考虑用户的偏好与用户偏好相近的音乐，并未对用户整体喜好与整个音乐库的分布联系起来，导致难有新的喜好的认知发现。二，对特征离散化较为固定，没有对每一维特征做分析；三，过度依赖音乐评分信息，每位用户对项目的认知不同，对项目的打分标准就不同；四，用户冷启动和项目冷启动。

参考文献

[1]Zhou Z,Liu M,Zhang F,et al.A data processing framework for IoTbased online monitoring system[C]//IEEE,International Conference on ComputerSupported Cooperative Work in Design.IEEE,2013:686-691.

[2]Chen W,Niu Z,Zhao X,et al.A hybrid recommendation algorithmadapted in e-learning environments[J].World Wide Web,2014,17(2):271-284.

[3]Crespo R G,Martínez O S,Lovelle J M C,et al.Recommendation Systembased on user interaction data applied to intelligent electronic books[J].Computers in Human Behavior,2011,27(4):1445-1449.

[4]张玉洁,杜雨露,孟祥武.组推荐系统及其应用研究[J].计算机学报,2016,39(4):745-764.

[5]Liebman E,Saartsechansky M,Stone P.DJ-MC:A Reinforcement-LearningAgent for Music Playlist Recommendation[J].Computer Science,2014.

[6]Sánchez-Moreno D,González A B G,Vicente M D M,et al.Acollaborative filtering method for music recommendation using playingcoefficients for artists and users[J].Expert Systems with Applications,2016,66:234-244.

[7]Trevarthen C,Delafield-Butt J T,B.Psychobiology of MusicalGesture:Innate Rhythm,Harmony and Melody in Movements of Narration[J].NewPerspectives on Music&Gesture,2011,6(6):754-764.

[8]Ventura M D.The Influence of the Rhythm with the Pitch on MelodicSegmentation[M]//Intelligent Data Analysis and Applications.SpringerInternational Publishing,2015:191-201.

[9]Sina.浅说Davies-Bouldin指数.http://blog.sina.com.cn,2012.

[10]Thierry Bertin-Mahieux,Daniel P.W.Ellis,Brian Whitman,and PaulLamere.The Million Song Dataset.In Proceedings of the 12th InternationalSociety for Music Information Retrieval Conference(ISMIR 2011),2011.Chen S,Moore J L,Turnbull D,et al.Playlist prediction via metric embedding[C]//ACMKnowledge Discovery and Data Mining.2012:714-722.

发明内容

本发明的目的就在于为了解决上述问题而提供一种基于状态转移的奖励值音乐推荐算法。

本发明通过以下技术方案来实现上述目的：

本发明算法如下：

输入：用户u的历史播放列表HL，音乐集中歌曲的流行度，音乐集M，音乐集M大小T，推荐列表长度X，聚类个数C，定时器clock

输出：推荐音乐列表L*；

(1)初始化用户偏好及音乐特征向量权重

(2)计算两个状态转移概率矩阵

(3)将音乐集M筛减成M*并聚类；

(4)生成候选列表L；

(5)针对列表L对用户偏好在线更新，得到

(6)计算L中每首音乐到各个聚类中心c_j的欧式距离ο(song,c_i)

(7)

if R(L)＞maxR(L)then

maxR(L)＝R(L)

L*＝L

End if

Until clock＝0

(8)返回L*。

本发明的有益效果在于：

本发明是一种基于状态转移的奖励值音乐推荐算法，与现有技术相比，本发明针对当前音乐推荐算法的不足，本发明以巧妙引入奖励值的概念，将音乐顺序纳入研究范围，将用户选择怎样的音乐列表视作马尔可夫决策过程，推荐音乐列表的每一首音乐，都视作决策过程中状态的变化，因此，不同状态会对当前局面产生不同的奖励值，算法选择奖励值最大的状态序列，在此即为奖励值最大的音乐列表。同时，将用户个人历史数据与整体用户数据做均衡，优化推荐效果，创新地加入音乐流行度和用户从众度，提出了基于状态转移的奖励值算法，具有推广使用的价值。

附图说明

图1是本发明的算法框架图；

图2是本发明的聚类后的音乐集示意图；

图3是本发明的播放列表中音乐位置示意图；

图4是本发明的状态s₀示意图；

图5是本发明的状态s₁示意图；

图6是本发明的状态s₂示意图；

图7是本发明的部分特征属性聚类DBI值曲线图；

图8是本发明的参数ω_u对推荐效果的影响曲线图；

图9是本发明的参数ω_z对推荐效果的影响曲线图；

图10是传统算法与本发明算法在用户组1的结果对比图；

图11是现有算法与本发明算法在用户组1的结果对比图；

图12是传统算法与本发明算法在用户组3的结果对比图；

图13是现有算法与本发明算法在用户组3的结对比图；

图14是传统算法与本发明算法在用户组3的结果对比图；

图15是现有算法与本发明算法在用户组3的结果对比图。

具体实施方式

下面结合附图对本发明作进一步说明：

1特征选择及数据离散化

通过对音乐声学特征的研究，文献[7]和[8]都通过节奏、音色、响度、音高这几个声学特征将一首音乐分类。考虑到不同年龄层次的用户会对某些年代的歌曲会有更强烈的喜好，本发明算法另外加入音乐的年代特征。

本发明借用the Echo Nest专业分析工具得出音乐的声乐特征，并将之量化，同时得到音乐的年代属性。本发明选择节奏、音色、响度、音高这四种声学特征以及歌曲的年代属性这一特征组成一首音乐的34维特征向量。特征向量具体组成如表1所示。

本发明提取的原始数据，由于数值趋于连续，不利于分类聚类等操作，因此，需要将特征向量的每一维进行离散化处理。离散化具体步骤为：

(1)对音乐库中所有音乐特征向量的每一维数据进行K-Means聚类，确定离散化段数K。

(2)每一维数据排序后按照数目均匀划分成K段。

(3)计算每一段的均值，作为该段所有数据的离散化数值。

其中，段数K的取值依据聚类算法的评估指数——Davies-Bouldin指数(DBI)[9]。DBI通常用于评价无监督聚类时聚类个数对聚类效果的影响，DBI值越小，类内距离越小，类间距离越大，聚类效果越好。本发明采用使DBI值最小的聚类个数K为该维属性的离散段数。

表1特征向量中属性的选择和索引

2考虑状态转移的奖励值函数

参照强化学习中奖励函数的作用，奖励值在本发明算法中是挑选音乐的数值依据。本发明的奖励函数定义如公式1所示。

R＝R_s(song_i)+R_t(s_i-1,song_i)>

(1)第一部分的R_s(song_i)为基于用户偏好形成的奖励值，由R_s(song_i)＝φ_s(u)·ω_s·θ_s(song_i)+α·c_u·TP(song_i)确定，是用户u的个性化偏好，由用户的历史数据迭代分析而来，θ_s(song_i)是音乐song_i的特征向量，β是θ_s(song_i)每一维的权重，用来度量θ_s(song_i)每一维特征属性对奖励值的贡献度，c_u是用户u的从众度，由用户个性化自定义，TP(song_i)同样表示音乐song_i的流行度，α是TP(song_i)的放大因子，在训练模型中是个可调参数。

(2)第二部分R_t(s_i-1,song_i)，度量的就是音乐间状态转移过渡对当前局面产生的影响。由公式2定义：

其中，ο(song_i,c_j)是song_i与c_j的欧氏距离，c_j指j簇的聚类中心，P_u(song_i|song_i-1)和P_u(song_i|song_i-1)分别指用户u个性化的song_i-1到song_i的转移概率和用户总体song_i-1到song_i的转移概率。

3状态转移概率和状态转移奖励值

在有限的状态空间中，从状态s₀转移到状态s₁的概率是一定的，用P(s₁|s₀,song₁)表示。本发明中，该概率描述用户听完上一首音乐后，听下一首音乐的可能性。

由于音乐集中音乐数目大，相比较下用户历史播放列表中的音乐数据小，若在推荐中一一考虑用户在听完历史列表音乐状态下，听音乐集中某首音乐的转移概率，这个数据无疑是稀疏的。因此，本发明考虑在音乐集M聚类后簇与簇间的转移概率，基于这个假设，本发明提出了基于音乐集M的簇间状态转移模型。

簇间状态转移概率模型遍历用户历史播放列表后得到。聚簇个数在模型训练时是可调参数，按照公式2的定义P(song_i|song_i-1)表示song_i-1到song_i的转移概率，实则，其具体取值为song_i-1所属的簇到song_i所属簇的簇间转移概率。本发明除了计算用户个人的状态转移概率之外，还考虑用户总体的状态转移概率模型，以此均衡个人状态转移的偏差。

假设用户u的历史播放列表为：{song₁,song₂,…,song₁₂}，根据聚类后的音乐集M，如图2所示(假设此时聚类个数K＝5)。一一计算用户历史列表中的12首音乐与聚类中心的距离，选择距离近的划分到相应的簇中。如图3所示。

考虑音乐的播放顺序，即song₁→song₂→…→song₁₂，那么根据播放顺序而发生的簇间的转移情况如表2所示。由此可以计算出，用户u在该聚类情况下簇间的转移概率如表3所示。

表2簇间转移情况

音乐播放顺序簇间转移音乐播放顺序簇间转移song₁→song₂Ⅰ→Ⅰsong₇→song₈Ⅳ→Ⅴsong₂→song₃Ⅰ→Ⅱsong₈→song₉Ⅴ→Ⅴsong₃→song₄Ⅱ→Ⅲsong₉→song₁₀Ⅴ→Ⅰsong₄→song₅Ⅲ→Ⅲsong₁₀→song₁₁Ⅰ→Ⅲsong₅→song₆Ⅲ→Ⅰsong₁₁→song₁₂Ⅲ→Ⅱsong₆→song₇Ⅰ→Ⅳ

表3簇间转移概率

同理，整体用户的状态转移概率矩阵P_z(song_i|song_i-1)。

如图4所示，是当前音乐集M及用户历史列表的状态s₀，候选推荐列表为L，song_L1和song_L2是L的第一首音乐和第二首音乐，如图5和图6所示。

在局面状态为s₀时，考虑添加song_L1后的状态转移奖励：

其中，表示song_L1与各聚类中心点的欧氏距离的倒数，距离值越小，与该簇相关联产生的状态转移奖励越大。

所谓状态叠加，是指将song_L1做推荐后，局面由s₀变为s₁，由于在此聚类情况下属于Ⅴ簇，因此，在计算song_L2的状态转移奖励时，状态转移概率带入第Ⅴ簇的簇间转移概率。

同理，基于整体用户的状态转移奖励值也可根据P_z(song_i|song_i-1)计算得到，用户个人状态转移奖励值与基于整体用户的状态转移奖励值由ω_u和ω_z两个权重均衡。

4用户偏好的初始化和在线更新

本发明模型的最终输出是一个长度为X的音乐推荐列表，用户偏好是衡量用户喜好的标准，为了体现用户对不同候选列表的感知，在用历史列表初始化后，根据不同的候选列表将用户偏好进行在线更新，以便响应对应的候选列表，便与精准计算每个候选列表的总奖励值。

按照奖励函数定义公式，本章模型首先需要对用户偏好进行初始化，初始化模型如公式2和公式3所示。

遍历历史列表中每一首音乐：

遍历音乐库中每首音乐的每一维特征属性：

初始化的用户偏好代表了用户最初的喜好，该喜好根据不同的候选推荐列表做以更新。本算法公式1定义的奖励值函数，计算每首音乐的奖励值，根据R(song_i)排序，按照从大到小顺序，选取0.3T大小的音乐集M*作为候选音乐集。

用户偏好会根据每个候选推荐列表L分别在线更新，候选推荐列表的生成方法如下步骤：

1：按照历史列表中训练数据的最后一首音乐所属类，检索P_u(song_i|song_i-1)和P_z(song_i|song_i-1)，在转移概率非0的簇内选择奖励值最大的音乐，作为候选推荐列表L的第一首音乐。

2：如果用户u的历史播放列表HL长度m>20，检索P_u(song_i|song_i-1)在转移概率非0的簇内选择奖励值最大的音乐，作为候选推荐列表L的第i首音乐；如果用户u的历史播放列表HL长度m≤20，检索P_z(song_i|song_i-1)在转移概率非0的簇内选择奖励值最大的音乐，作为候选推荐列表L的第i首音乐。

3：以此类推，得到长度为X的候选推荐列表L。

得到候选推荐列表L后，用户偏好进行在线更新，更新方法如下步骤：

遍历候选推荐列表L：

r_i＝R_s(song_i)

其中，r_i为在当前状态下用户听完song_i产生的立即奖励，即算法4-3中计算得到的R_s(song_i)，为目前为止的平均奖励，本发明定义该变量可以决定下一首音乐的选择对当前更新是否有增益，例如，若则r_ince是个负数，对参数更新产生负影响。最后，模型为更新分配的权值之和为1，综上所述，本发明的算法总体为：

输入：用户u的历史播放列表HL，音乐集中歌曲的流行度，音乐集M，音乐集M大小T，推荐列表长度X，聚类个数C，定时器clock

输出：推荐音乐列表L*；

(1)初始化用户偏好及音乐特征向量权重

(2)计算两个状态转移概率矩阵

(3)将音乐集M筛减成M*并聚类；

(4)生成候选列表L；

(5)针对列表L对用户偏好在线更新，得到

(6)计算L中每首音乐到各个聚类中心c_j的欧式距离ο(song,ci)

(7)if R(L)＞maxR(L)then

maxR(L)＝R(L)

L*＝L

End if

Until clock＝0

(8)返回L*。

5实验

5.1实验数据

本发明理论，选择哥伦比亚大学整理的Million Song Dataset开源音乐数据^[10]。Million>

分，具体如表4和表5所示。

表4用户数据划分

训练集测试集23941197

表5测试集分组

组别用户组1用户组2用户组3样本数目384325488

本发明将数据按照2:1的方式划分为训练集和测试集，测试集又分为3组子集，以供多组测试实验。

5.2算法实验

5.2.1数据离散化

一首音乐由一个34维特征向量唯一表示，需要对每一维做离散化处理。图7所示的是关于节奏，音乐30分位、70分位处响度大小，平均响度及响度方差的DBI值。聚类个数均为2到20，K-Means迭代次数为100。节奏这一特征在K＝14时取得最小值0.471，说明该维特征分为14类时效果最好，因此，本发明将该维特征离散化成14段，每一段值取该段的均值。以此类推，如表6所示，为每一维的离散化段数。

表6特征向量各维度离散段数

5.2.2参数实验

首先定义两个列表间的距离，如公式4。

其中，song_{list1_i}-song_{list2_i}表示两首

音乐间的距离，X是列表长度。2394位用户中，历史播放列表长度≥30的用户共1843个，在此用户集上进行调参实验。对权重ω_u的优化实验如图8所示。纵坐标表示列表距离。

由图8和图9可以看出，当ω_u在(1,200)内变化时，列表距离的变化域大致范围是是(1.95，2.48)，当ω_u＝116时，取得最小值。

对权重ω_z的优化实验如图9所示。由图知当ω_u在(1,200)内变化时，列表距离的变化域大致范围是是(1.89，2.15)，当ω_z＝41之后，波形有震荡，但是总体趋势不再变化，因此，算法中，对ω_z的值设置为41。

同理，参数α和β的取值分别为7.1和0.8·β_初始，聚类个数为28。

5.2.3算法对比和分析

将本发明所提算法与传统推荐算法中随机推荐和K-NN算法以及前人算法文献[5](Liebman)和文献[11](Chen)进行比较，以验证本发明算法的有效性。

在用户组1上进行比较，结果如图10和图11所示。由两组数据看出，本发明算法在用户组1上的表现，优于传统的推荐算法。与前人的算法相比较，RMSE与Liebman算法比较，降低39.8个百分点，与Chen的算法比较，降低29.2个百分点，皮尔逊相似系数优于Liebman的算法8.5个百分点，优于Chen的算法3.2个百分点，呈强相关。

由图10至图13数据看出，本发明算法在用户组2上的表现，优于传统的推荐算法。与前人的算法相比较，RMSE与Liebman算法比较，降低27个百分点，与Chen的算法比较，降低11.2个百分点，皮尔逊相似系数优于Liebman的算法10.7个百分点，优于Chen的算法5.0个百分点，呈强相关。

由图14和图15数据看出，本发明算法在用户组3上的表现，同样优于传统的推荐算法。与前人的算法相比较，RMSE与Liebman算法比较，降低27.6个百分点，与Chen的算法比较，降低11.8个百分点，皮尔逊相似系数优于Liebman的算法11.2个百分点，优于Chen的算法5.1个百分点，呈强相关。

综上数据，基于状态转移的奖励值算法表现强于前人算法，算法改进有效。

总结：

本发明针对当前音乐推荐算法的不足，本发明以巧妙引入奖励值的概念，将音乐顺序纳入研究范围，将用户选择怎样的音乐列表视作马尔可夫决策过程，推荐音乐列表的每一首音乐，都视作决策过程中状态的变化，因此，不同状态会对当前局面产生不同的奖励值，算法选择奖励值最大的状态序列，在此即为奖励值最大的音乐列表。同时，将用户个人历史数据与整体用户数据做均衡，优化推荐效果，创新地加入音乐流行度和用户从众度，提出了基于状态转移的奖励值算法。

本发明基本完成了模型的主要任务。基于时间和实验条件的约束，还有很多地方需要改进。如，除音乐的声乐特征之外，还可考虑歌词的语义特征，加入情感分析，完善对音乐集的聚类及分类。另外，在保证目前的模型训练时间和算法运行时间的同时，未来可以考虑如何更细致分析用户偏好，将用户客观属性加以考虑，提高推荐准确度。

以上显示和描述了本发明的基本原理和主要特征及本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。