基于用户聚类的图书推荐算法设计与实现

高伊腾 张雅迪 唐宁 李云云 周国栋

摘   要：个性化推荐算法中一直存在新用户的冷启动问题，文章通过引入ID3算法来预测、分析新用户的类别选择。首先，根据实验数据特征对ID3算法加以改进;其次，根据分析数据表中各字段的属性确定试验参数;最后，得出实验结果。

关键词：推荐算法;冷启动;决策树;聚类分析

推荐系统是一种向目标用户建议可能感兴趣物品的软件和技术，主要服务于缺乏经验和能力的用户，他们通常无法从大量可供选择的物品中选取感兴趣的物品，如无法从某网站中选取感兴趣的商品。目前，电商的推荐大多是个性化的，即不同用户或用户组所接收的建议不同。当然，也存在非个性化推荐，但大都非常简单，通常出现在报纸或杂志上。

推荐系统中遇到的问题有很多，包括新用户与新图书的冷启动问题，即如何向新用户进行个性化推荐。目前，针对冷启动问题进行研究的文章，大多基于电子商务协同过滤推荐中的用户和项目属性[1]、新用户回答问题[2]、特征匹配等方法。其中，赵盼盼[3]采用聚类、关联规则的新图书推荐方法以解决新图书的推荐问题，吕红霞等[4]采用划分类别的方式为新读者进行推荐。

为提高向新用户个性化推荐图书的质量，本文就新用户的冷启动问题，提出一种基于用户聚类的图书推荐算法的解决办法，采用决策树中的ID3算法作为数据分析工具。首先，根据实验数据特征需要，对ID3算法进行改进;其次，通过实验分析确定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等参数。最后，使用决策树得出实验结果。

1    基于用户聚类的图书推荐算法

1.1  简要介绍

基于用户聚类的图书推荐算法主要用于解决图书推荐系统方面的冷启动问题。本文使用ID3算法来解决系统冷启动问题，通过实验分析，需要确定COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等参数，以达到最佳聚类的效果。

本文通过确定描述属性、类别属性、实验指标等得出预测分析表，预测新用户的喜好，进行个性化推荐。“实验分析用户”可以定义为：依据新用户的描述属性经过一轮决策树预测，向该用戶进行图书推荐，收藏推荐图书的用户即为实验分析用户。基于用户聚类的图书推荐算法，既完成了新用户到实验分析用户的转变，提升用户体验，又新增加了实验分析用户，更有利于后续对新老用户进行准确的聚类分析。

1.2  ID3算法

1.2.1  ID3算法的定义及构造方法

ID3算法在构造决策树时，对于数据集S，根据其中信息增益最大的属性Ai划分成若干个子区域，其中，某个子区域停止划分样本的方式是：如果Sj中所有样本的类别相同（假设为aij），则停止划分样本（以aij类别作为叶子结点）。如果没有剩余属性可以用来进一步划分数据集，则使用多数表决，取Sj中多数样本的类别作为叶子结点的类别。如果Sj为空，以S中的多数类别作为叶子结点的类别。

1.2.2  信息增益

假设训练数据集是关系数据表S，共有n个元组和m+1个属性，其中，描述属性有A1，A2，…，Am。类别属性C的类别数为u，其值域为（c1，c2…，cu），类别属性C取值为ci（1≤i≤u）的元组个数为si。对于描述属性Ak（1≤k≤m），它的不同取值个数为v，其值域为（a1，a2，...av）。在类别属性C取值为ci（1≤i≤u）的子区域中，描述属性Ak取aj（1≤j≤v）的元组个数为sij。

定义1：类别属性C的无条件熵E（C）定义为：

其中，p（ci）为C=ci（1≤i≤u）的概率。E（C）反映了属性C取值的不确定性，当所有p（ci）相同时，E（C）最大，呈现最大的不确定性;当有一个p（ci）=1时，C（X）最小即为0，呈现最小的不确定性。

定义2：对于描述属性Ak（1≤j≤m），类别属性C的条件熵E（C，Ak）定义为：

条件熵E（C，Ak）表示在已知描述属性Ak的情况下，类别属性C对训练数据集S的分类能力。

定义3：给定描述属性Ak（1≤k≤m），对应类别属性C的信息增益定义为：

G（C，Ak）表示在已知描述属性Ak的情况下，类别属性C对训练数据集S分类能力增加的程度。

1.2.3  算法执行步骤

建立决策树的ID3算法Gennerate_decision_tree（S，A）如下：

输入：训练数据集S，描述属性A和类别属性C。

输出：决策树（以Node为根节点）。

step1：如果S中的样本属于同一类别c，则以c标识Node并将它作为叶子结点。

step2：如果A为空，则以S中占多数的样本类别c标识Node并将它作为叶子结点。

step3：for（属性集合A中每个属性Ak）计算G（C，Ak）=E（C）-E（C，Ak）。

Ai=MAX{G（C，Ak）}，Ai的Node数大于等于MINIMUM_SUPPORT则继续拆分。

step4：for（Ai的每个可能取值aij） 产生S的一个子集Sij。

step5：if（Sj为空） 创建对应的sj的结点Nodej; 以S中占多数的样本类别c标识Nodej。

将Nodej作为叶子结点形成Node的一个分支。

step6：else Gennerate_decision_tree（Sj，A-{Aj}）。

1.3  获取推荐结果

经过在Microsoft Visual Studio 2008中导入数据表S和预测分析表S1，定义数据源视图，建立挖掘结构，设置COMPLEXITY_PENALTY，MINIMUM_SUPPORT，SCORE_METHOD，SPLIT_METHOD等参数，部署一系列步骤。最终在挖掘模型查看器得出一张预测分析表，表中描述了类别属性与描述属性之间的关系。

2    数据测试及结果分析

2.1  实验环境配置

本文使用SQL Server 2008作为数据源，使用Microsoft Visual Studio 2008作为决策树分析工具，在JetBrains PyCharm 5.0.3+Microsoft Excel 2010编程环境中实现了ID3算法，用于得到决策树模型。

2.2  获取数据源

实验开始前，通过采用数据仿真模拟的方法获得所需要的数据，创建一个Users表，包含编号、姓名、性别、年级、学院、专业、书名、书类等8个字段。表中数据来源通过以下两种途径进行获取。

从咸阳师范学院图书馆获取计算机学院、资历学院、建筑学院、经管学院4个学院的2015级、2016级学生及教师（为了能够显著分析实验结果，在表中定义教师为2000级）的姓名、性别、年级、学院、专业。根据实验设备条件，在实验分析阶段，将所到的数据同比例缩小。

上述學院包含的专业有：计算机学院（所属专业有：计科、软件、物联），资历学院（所属专业有：地理科学、历史学），建筑学院（所属专业有：建筑学、城乡规划、城市规划），经管学院（所属专业有：经济学、财务管理、经管学）。

书籍名称以及书籍类别以正当途径通过当当网来爬取。

2.3  实验参数设置指标及参数的选取

根据Microsoft决策树算法技术参考，在使用ID3算法进行决策树分析时，需要设置以下3个主要算法参数。

2.3.1  COMPLEXITY_PENALTY

COMPLEXITY_PENALTY控制决策树的增长。该值较低时，会增加拆分数;该值较高时，会减少拆分数。默认值基于特定模型的属性数，参照3个范围设置参数：（1）对于1～9个属性，默认值为0.5。（2）对于10～99个属性，默认值为0.9。（3）对于100或更多个属性，默认值为0.99。本文实验数据集有4个属性，因此，根据上述规则，本文的ID3算法COMPLEXITY_PENALTY设置为0.5。

2.3.2  MINIMUM_SUPPORT

MINIMUM_SUPPORT确定在决策树中生成拆分所需的叶实例的最少数量。一般而言，MINIMUM_SUPPORT的值是描述属性的个数。因此，将MINIMUM_SUPPORT设置为3。

2.3.3  SCORE_METHOD

SCORE_METHOD确定用于计算拆分分数的方法。可用选项包括：（1）Entropy。（2）Bayesian with K2 Prior。（3）Bayesian Dirichlet Equivalent（BDE） with uniform prior（默认值），其中，Entropy为信息熵。本文采用信息熵作为属性选择的启发信息，因此，将SCORE_METHOD设置为1。

2.3.4  SPLIT_METHOD

SPLIT_METHOD确定用于拆分节点的方法。可用选项包括：（1）Binary：指无论属性值的实际数量是多少，树都拆分为两个分支。（2）Complete：指示树可以创建与属性值数目相同的分叉。（3）Both：指定Analysis Services可确定应使用binary还是complete，以获得最佳结果（默认值）。本文将SPLIT_METHOD设置为2。

2.4  实验结果

本文选取部分挖掘模型预测分析表，如图1所示，由于篇幅限制，这里只对部分实验结果进行展示，对满足专业属性对应的各类别属性进行统计整理。实验发现：70%的类别属性与所属院系教学内容高相关。30%的类别属性与所属院系低相关。

在JetBrains PyCharm 5.0.3+Microsoft Excel 2010编程环境下编写的ID3算法构造出来的决策树如图2所示，其分类的效果达到预期目的。可以看出，3个描述属性很好地对类别属性进行样本空间的划分。

3    结语

本文针对新用户冷启动问题，综合考虑性别、年级、专业等主要描述属性，依据ID3算法提出一种基于用户聚类的图书推荐算法。实验结果表明，本算法能够充分解决新用户的图书推荐问题。

[参考文献]

[1]李转运，孙翠敏.基于项目属性权重的协同过滤推荐算法[J].新乡学院学报，2019（3）：30-33.

[2]邓明通，刘学军，李斌.基于用户偏好和动态兴趣的多样性推荐方法[J].小型微型计算机系统，2018（9）：2029-2034.

[3]赵盼盼.基于云填充和蚁群聚类的协同过滤技术在图书推荐中的应用研究[D].阜新：辽宁工程技术大学，2016.

[4]吕红霞，王文宪，蒲松，等.基于聚类分析的铁路出行旅客类别划分[J].交通运输系统工程与信息，2016（1）：129-134.