信息的爆炸反而使得信息的利用率降低，造成了信息超载现象.信息的增长使得人们难以从海量资讯中选择自己感兴趣的新闻.新闻个性化推荐系统被广泛用于解决信息超载问题，为不同的用户提供个性化体验来提高用户阅读满意度.

协同过滤算法是推荐系统的经典算法之一，目前已有学者将协同过滤算法应用到新闻推荐中，并取得了一些成果^[1-3].但基于协同过滤算法的新闻推荐系统仍存在冷启动问题，同时可解释性较差^[4-5].在基于内容的推荐算法中，解决了冷启动问题并有较强的解释性^[6-7]，但其对新闻的分类上采用的是编辑分类，导致存在2个问题：一是编辑很难控制分类的粒度；二是编辑的意见不能代表各种用户的意见.针对新闻分类问题，古万荣等^[8]提出了一个基于二次聚类的新闻推荐算法，李佳珊^[9]对目前数据挖掘领域的聚类算法进行了总结与分析，但这些方法仅对新闻聚类问题进行了分析与改进.

针对上述问题，为了能保留基于内容的推荐算法的可解释性的优势，同时尽量避免编辑分类存在的问题，提出了一种基于向量空间模型(VSM，vector space model)和Bisecting K-means聚类的新闻推荐方法.实验结果表明，与传统的协同过滤算法相比，其预测准确度得到了提高.

1 算法思想和流程框架

推荐系统的经典构建流程主要包括用户建模模块、推荐对象建模模块、推荐算法模块^[9].推荐算法(见图 1)主要包括：新闻文本向量化、构建用户兴趣模型、相似度计算3个流程.

1) 新闻文本向量化(见第2节).首先将新闻文本向量化，即使用一个多维向量来表示新闻的内容(d=(w₁, w₂, …, w_m))，将新闻文本向量化的结果称为新闻特征向量.

2) 构建用户兴趣模型(见第3节).用户兴趣模型构建是本文方法中最关键的一步，首先对已进行向量化处理的新闻集进行自动聚类，接着对每个用户和其已经浏览过的新闻构建三层结构的用户兴趣模型：用户—新闻类别—新闻.

3) 相似度计算.相似度计算方法很多，最常用的主要有Pearson相似性和余弦相似性.余弦相似性通过计算2个向量之间的夹角余弦来衡量两者之间的相关性，由于该方法计算简单，本文中用户兴趣模型和新闻最终都采用向量表示，所以采用余弦相似性方法，如式(1)所示.计算用户兴趣模型和候选新闻集之间的相似度，选取相似度靠前的N条新闻推荐给用户.

$ {\rm{sim}}\left( {i,j} \right) = \cos \left( {i,j} \right) = \frac{{ij}}{{\left| i \right|\left| j \right|}} $

(1)

2 新闻文本向量化

向量空间模型是信息检索领域最为经典的计算模型，在该模型中，每个文档用一个特征向量来表示该文档中的多维信息.考虑到新闻数据的高维性以及为便于新闻聚类从而构建用户兴趣模型，笔者采用向量空间模型来表示新闻特征向量.

给定新闻集D={d₁, d₂, …, d_n}，新闻集的VSM表示为

$ \mathit{\boldsymbol{M}} = \left[ {\begin{array}{*{20}{c}} {{w_{11}}}& \cdots &{{w_{1m}}}\\ \vdots &{}& \vdots \\ {{w_{n1}}}& \cdots &{{w_{nm}}} \end{array}} \right] $

(2)

其中w_ij表示为关键词j在新闻i中的权重.构建VSM的关键有2个方面：一是确定关键词集的维度m；二是权重w_ij的计算.

1) 关键词集的维度m：关键词用于表征该文档特性，文献[10]对比分析了多种关键词提取方法，实验得出当关键词个数在(5, 8)之间时效果最好.但关键词数量增加会导致M的维度m增大，从而引起时间复杂度增加.在保证文档表征效果前提下，为减少时间开销，提取每篇新闻中的前5个关键词来表征该新闻特性，接着采用TF-IDF算法得出新闻集中关键词集的维度m.

2) 权重w_ij的计算：最常用和有效的权重的计算方法为TF-IDF表示法，该方法是信息检索领域的成熟技术.

TF-IDF算法的计算可以分成词频(TF，tevm frequency)和逆文档频率(IDF，inverse document frequency)两部分，由这两部分的乘积共同决定文档词语的权重. TF-IDF算法有多种变种形式，笔者采用的计算方法为

$ {\rm{TF}}\left( {i,j} \right) = \frac{{{\rm{count}}\left( {i,j} \right)}}{{{\rm{size}}\left( j \right)}} $

(3)

count(i, j)表示关键词i在新闻j中的频数，size(j)表示新闻j的总数. IDF计算公式为

$ {\rm{IDF}}\left( i \right) = \log \frac{N}{{n\left( i \right)}} $

(4)

N表示新闻集总数，n(i)表示关键词i出现过的新闻数量.权重由TF和IDF计算为

$ {w_{\left( {i,j} \right)}} = {\rm{TF}}\left( {i,j} \right){\rm{IDF}}\left( i \right) $

(5)

为使权重值处于[0, 1]区间内且新闻能够用等长向量表示，使用余弦归一化的方式对权重进行归一化处理，词语的权重计算公式为

$ {w_{\left( {i,j} \right)}} = \frac{{{\rm{TF}} - {\rm{IDF}}\left( {i,j} \right)}}{{\sqrt {\sum\limits_{i = 1}^T {\rm{TF}} - {\rm{IDF}}{{\left( {i,j} \right)}^2}} }} $

(6)

3 构建用户兴趣模型 3.1 基于Bisecting K-means算法的新闻分类

目前在数据挖掘领域的聚类算法主要包括基于模型的算法、基于网格的算法、基于密度的算法、基于距离的算法4种^[9].笔者研究的数据为新闻数据，具有海量、高维等特点，同时采用了向量空间模型来表示新闻的文本特征，因此基于以上考虑，采用基于距离的算法作为新闻聚类方法. Abuaiadah D^[11]研究得出K-means聚类算法的改进算法——Bisecting K-means聚类算法收敛速度更快，聚类效果更优.综上，在向量空间模型基础上，采用Bisecting K-means聚类算法可实现新闻的分类.

Bisecting K-means聚类算法类似于一种层次聚类算法，具有不需要先验簇数量的优点，改善了K-means聚类算法中初始质心位置对聚类结果产生影响的问题.该算法中采用误差平方和S来衡量簇的质量，S的计算如

$ S = \sum\limits_{m = 1}^k {\sum\limits_{}^{{p_i} \in {C_i}} {{\rm{distance}}{{\left( {{p_i},{c_i}} \right)}^2}} } $

(7)

其中：c_i为C_i簇的质心点，p_i为C_i簇中的其他数据点，distance(p_i, c_i)²为p_i与c_i之间的欧氏距离.在该算法中，关键一步在于选取需要进行二分的簇，该判断规则为：对目前存在的k个簇，从第一个簇开始运用K-means聚类算法进行二分，计算该簇的总误差S₁值以及剩余簇的总误差S₂值，得出S₁+S₂的误差和，接着循环遍历这k个簇，最终选取S₁+S₂的误差和最小的簇进行二分.

3.2 用户兴趣模型构建

通过用户已经浏览过的新闻数据构建用户兴趣模型，用户兴趣模型采用3层层次结构表示：用户-新闻类别-新闻.如图 2所示，第1层节点为用户，第2层节点为用户浏览的新闻类别，第3层节点为用户浏览过的新闻.

若用户浏览过m个不同的新闻类别，则用户兴趣模型可用如下模型表示：

$ {\rm{user}} = \left\{ {\left( {{\mathit{\boldsymbol{T}}_1},{w_1},{n_1}} \right),\left( {{\mathit{\boldsymbol{T}}_2},{w_2},{n_2}} \right), \cdots ,\left( {{\mathit{\boldsymbol{T}}_m},{w_m},{n_m}} \right)} \right\} $

(8)

其中：T_i表示第i个新闻类别特征向量，w_i表示第i个新闻类别的权重，n_i表示第i个新闻类别包含的用户浏览过的新闻的数量.

某个新闻类别的特征向量根据该类别所包含的所有已浏览过的新闻特征向量根据兴趣度加权平均求出，即第i个新闻类别特征向量T_i的计算公式为

$ {\mathit{\boldsymbol{T}}_i} = \frac{{\sum\limits_{{{e}_j} \in {E_j}} {{\mathit{\boldsymbol{e}}_j}{I_j}} }}{{\sum\limits_{{\mathit{\boldsymbol{e}}_j} \in {E_j}} {{I_j}} }} $

(9)

其中：E_j为新闻类别i中的用户浏览过的新闻集合，e_j为新闻特征向量，I_j为该类别中第j个新闻的用户兴趣度，用户浏览过某新闻即表示用户对该新闻有兴趣，因此将I_j设为1，则式(9)可简化为

$ {\mathit{\boldsymbol{T}}_i} = \frac{{\sum\limits_{{\mathit{\boldsymbol{e}}_j} \in {E_j}} {{\mathit{\boldsymbol{e}}_j}} }}{{{n_i}}} $

(10)

w_i的值根据第i个新闻类别中用户浏览过的新闻数量占总共浏览过的新闻数量的权重来计算，如

$ {w_i} = \frac{{{n_i}}}{{\sum\limits_{i = 1}^m {{n_i}} }} $

(11)

在计算时，用户兴趣模型表示为

$ {\mathit{\boldsymbol{V}}_{{\rm{user}}}} = {\left( {{w_1}{\mathit{\boldsymbol{T}}_1},{w_2}{\mathit{\boldsymbol{T}}_2}, \cdots ,{w_m}{\mathit{\boldsymbol{T}}_m}} \right)^{\rm{T}}} $

(12)

最终，使用余弦相似度计算候选新闻d_i与用户之间的相似性，计算公式如

$ {\rm{sim}}\left( {{\rm{user}},{\mathit{\boldsymbol{V}}_{{d_i}}}} \right) = \cos \left( {{w_i}\mathit{\boldsymbol{T}}_i^{\rm{T}},{\mathit{\boldsymbol{V}}_{{d_i}}}} \right) $

(13)

w_iT_i^T为候选新闻d_i所属新闻类别的特征向量，V_di为d_i的特征向量.

4 实验及对比分析 4.1 实验环境与数据

使用DataCastle提供的用户浏览新闻数据集，该数据集从国内某著名财经新闻网站——财新网随机采集，总共包括1万名用户在2014年3月的所有新闻浏览记录，共116 225条.每条浏览记录包括用户编号、新闻编号、浏览时间以及新闻文本内容等.实验采用python的第三方库——jieba分词器进行分词，根据实际新闻内容采用改进的哈尔滨工业大学信息检索中心的停用词表去除停用词.

在实验数据预处理阶段，首先将数据集中用户浏览记录少于40条的用户删除，共获得279名用户的30 865条浏览记录；接着使用python中的scikit-learn库将数据集切分为训练集和测试集，训练集和测试集之间的比例选择为5:1.为增强结果的可靠性，每种方法都重复试验5次取平均值作为实验结果.

4.2 实验评估指标

采用准确率、召回率和F值作为实验的评估指标，准确率和召回率使用混淆矩阵表示，见表 1.

准确率P、召回率R的计算公式为

$ P = \frac{{TP}}{{TP + FP}} $

(14)

$ R = \frac{{TP}}{{TP + FN}} $

(15)

$ F = \frac{{2PR}}{{P + R}} $

(16)

4.3 实验结果与分析

为验证提出方法的可行性和推荐性能，实验以基于用户的协同过滤算法(user-based CF)、基于物品的协同过滤算法(item-based CF)、结合VSM和K-means聚类推荐算法(简称VSM+K-means算法)为Baseline，对实验结果进行对比分析，推荐结果数量N考虑了(10，15，20，25，30)共5种情况.

1) user-based CF和item-based CF最优评估指标确定

基于用户的协同过滤算法和基于物品的协同过滤算法作为2种经典的个性化推荐算法，其推荐结果的准确度与最近邻的个数紧密相关，实验中，考虑的最近邻个数K为5、10、15、20共4种情况，对应的评估指标如表 2、表 3所示.

观察表 2和表 3可知，在user-based CF中，当最近邻K=10时推荐效果更佳；在item-based CF中，当最近邻K=15时推荐效果更佳.

2) VSM+K-means算法与本文方法最优评估指标确定

VSM+K-means算法与本文方法都使用了聚类算法，新闻集的聚类簇数M对最后算法推荐结果的评估指标会产生影响，笔者考虑的聚类簇数M为10、15、20、25、30共5种情况，对应的评估指标结果如表 4、表 5所示.

观察表 4、表 5可知，当聚类簇数M=20时，2种方法的推荐效果更优于其他聚类簇数.

3) 不同算法下的评估指标比较

在图 3中，4种算法的准确率都呈现由高至低的变化趋势，是由推荐结果中用户喜欢的新闻增长率低于新闻推荐结果数量增长率导致的. 图 4中4种算法的召回率都呈现与图 3相反的趋势，是因为随着推荐结果中新闻数量的增加，其包含的用户喜欢新闻数量也增加，根据召回率的计算规则，可知召回率将呈现增长的趋势.准确率和召回率的排序由高到低依次为本文方法、VSM+K-means算法、user-based CF和item-based CF.因为实验数据中新闻数量比用户数量多数倍，故可能导致user-based CF推荐效果要比item-based CF稍好一点；但可知VSM+K-means算法明显优于前2种协同过滤算法；同时本文方法的准确率和召回率都要优于VSM+K-means算法，这应该是本文算法采用的Bisecting K-means聚类算法聚类效果优于K-means算法导致的，实验结果也符合上文中的原理分析.数据方面，在准确率上，本文方法要比user-based CF和item-based CF 2种协同过滤算法平均优于6%，比VSM+K-means算法平均优于2%；在召回率上，本文方法要比user-based CF和item-based CF 2种协同过滤算法平均优于7%，比VSM+K-means算法平均优于2%.

图 5展示了这4种算法在F值上的变化趋势，F值都表现为先高后低，F值是综合准确率和召回率的一种评价指标，其变化趋势与算法中准确率和召回率的变化速率有关，具体内涵还需深入思考.数据方面，从图中可以看出，当推荐结果个数在15~25之间时推荐效果更好，在此期间本文方法要比user-based CF和item-based CF 2种协同过滤算法平均优于7.8%，比VSM+K-means算法平均优于2.2%.

从准确率、召回率和F值这3种评估指标分析，可见笔者提出的方法要比传统的user-based CF和item-based CF 2种协同过滤算法在推荐效果上有明显提高；与VSM+K-means算法相比略有改善.

5 结束语

个性化新闻推荐技术有了一定的研究基础，笔者在之前研究的基础上，提出了一种融合VSM和Bisecting K-means聚类算法的新闻推荐方法，使用VSM能较好地表征新闻文本特征，根据Bisecting K-means聚类算法对新闻聚类避免产生人为对新闻分类的主观缺陷.实验结果表明，所提出的方法在准确率、召回率和F值等方面与传统的基于用户的协同过滤算法、基于物品的协同过滤算法相比有较好的优越性.与VSM和K-means聚类相结合的推荐方法进行了比较，结果表明，Bisecting K-means聚类算法得出的推荐结果效果更佳.下一步将对用户兴趣模型更新、结合地理位置信息的新闻推荐方法进行研究，进一步提高推荐性能，增强用户满意度.