融合双聚类技术的新型协同过滤算法*

左东石

(内蒙古农业大学 计算机与信息工程学院，内蒙古 呼和浩特 010018)

随着第三方支付业务的普及，在互联网交易平台上时刻进行着大量的交易行为.对于用户来说，如何选择合适的商品/项目和低廉的价格，是其最关心的问题.协同过滤[1]技术是电子商务平台广泛采用的系统推荐方法，其通过数据挖掘和信息检索技术来实现自动化推荐，可以根据用户行为智能地选择符合客户要求的商品.目前，协作过滤技术主要分为两类[2]：最近邻算法和基于模型的算法.由于最近邻算法[3]具有更高的计算精度，因此该方法获得了更多的关注，发展较快.文献[4]研究了参数k对k-最近邻算法性能的影响，并提出了获取最佳预测性能的k值选取方法.文献[5]将矩阵分解与用户最近邻点相结合，实现了用户之间的相似度信息与矩阵模型的有机整合，大幅度提高了算法性能.文献[6]分析了传统协同过滤算法的数据稀松问题，设计了考虑用户与项目特征的自适应协同过滤算法，并利用评分相似模型计算出了用户和项目的最近邻集合.

本文提出一种同时考虑用户和项目特性的双聚类协同过滤算法，通过构建双聚类相似度来获得推荐服务与用户之间的局部邻近度，并将局部度量和全局距离度量相结合，从而为每个网络服务创建均衡排名，达到提升协同过滤精度的目的.

1 双聚类协同过滤算法

1.1 相似度计算

皮尔森相关系数(Pearson correlation coefficient，PCC)是一种计算用户和项目之间相似性的有效方法，已在许多推荐系统中被广泛应用[7].当PPC被用来测量两个用户之间的相似度时，其标准表达式为：

为了将网络服务的个体属性并入用户相似度计算中，需要设计相应的权重系数.第i个网络服务的服务质量权重计算过程包括：服务质量值归一化，标准偏差计算，权重生成.

① 服务质量归一化.通过与最大、最小网络服务值进行比较，将用户的第i个网络服务值变换为区间[0, 1]的实数.具体的归一化计算方法为

式中：ri为第i个网络服务对应的网络服务值的集合.

② 标准偏差计算.对于网络服务i来说，其网络服务值归一化的标准偏差为

在经过以上三步后，我们提出一种基于网络服务权重重构的用户(仍用用户a、b来表示)间相似度的改进方法，其计算公式为：

上式可以将网络服务的个性化影响纳入用户相似度测量中，从而使得具有较大权重的网络服务将对用户间的相似性影响更大.为了实现协同过滤，还需采用下式所示的用户服务质量值的预测方法(以用户a为例)：

为了避免因用户与项目之间的对偶性而产生的数据稀疏问题，需要对用户与项目之间的相似性进行优化处理.因此，下面给出项目之间的相似度计算及其改进方案.最后再对用户、项目进行聚类计算.网络服务(项目)i、j之间的PCC计算公式为：

与用户间服务质量值的权重修改方法类似，项目间的相似度改进计算公式为：

1.2 双聚类技术

采用双聚类方法实现用户和服务间的协同过滤，从而实现网络服务的有效推荐.

对于用户x(对应的用户集为X)和网络服务y(对应的项目集为Y)，双聚类方法包括三个基本步骤：① 将用户x映射到最小双聚类Z=(X,Y)上；② 搜索项目集Y的双聚类近邻，确认其作为有效网络服务的推荐候选集；③ 基于全局相似度和双聚类邻域相似度，评估Y中的网络服务.

Top-n推荐技术[8]是近年来信息服务领域的一个研究热点，它可以从研究对象中得到所需的n个数据，并从排序列表中选取最大或最小的n个数据，从而完成推荐过程.本文将Top-n推荐与双聚类算法相结合，用来提高推荐的准确性和快速性.该方案的具体算法流程为：

1.开始；

2.设置变量：ui为用户，M为所有数据构成的矩阵，n为期望的网络服务推荐数；

3.搜索最小双聚类Z：减小Z的邻域，最小化uiZ，得到用户-项目集(X,Y)；

4.对Z中所有元素进行同属化，得到最小同属双聚类Zs；

5.对于所有的Zs，将Y中对应的Ys设置为候选项目；

6.对于所有的包含于候选项中的y，计算Pm_x,y；

7.结合全局和双聚类相似度对候选网络服务进行排列，返回Pm_x,y中的前n个网络服务；

8.结束.

上述计算流程中的全局相似度和局部相似度的计算方法如下.

假设Xy、Xy′分别表示与网络y、y′进行交互的所有用户的集合，则J(x,y)的表达式为：

双聚类相似度的计算方法如下，令Z=(X,Y)和Z′=(X′,Y′)为两个不同的双聚类，这两个双聚类的联合Φ和零诱导相似度B分别为：

式中：zeros(·)代表求取矩阵中零值的数量，零值的数量越少，Z和Z′就越相似.假设Z是初始聚类，Z′是较低的领域或者Z的同类聚类，则在矩阵(X∪X′)·(Y∪Y′)中至少有一个零值.

2 实验分析

为验证算法的有效性，我们将算法与传统的基于项目的协同过滤算法相比较.此外，实验中的网络服务数据选取淘宝某日交易的部分数据，该数据集包含来自400个用户的12 000个网络服务的服务质量调用记录.为了便于计算，将这些数据集转换为用户服务矩阵，用户服务矩阵的每个项目是由响应时间和吞吐量构成的.因此，原始用户服务矩阵可以分解成两个更简单的矩阵，即响应时间矩阵和吞吐量矩阵.这两个矩阵用于计算用户和服务的相似度.在该数据集上进行了对比实验，用来验证所提出算法相较于传统算法在精度κ和召回率σ等方面的优势.衡量推荐算法性能的主要技术指标(即精度和召回率)的计算方法为：

式中：D为待检索文档；D′为被成功检索的文档；si(·)代表求取文档中所有元素对应的分数之和.

图1、图2为推荐数量分别取不同的值时，基于项目的服务质量值预测的方法和基于双聚类的方法在精度和召回率方面的性能比较结果.由实验结果可知，随着推荐数量的增加，两种算法的精度和召回率都在增加，而提出的方法在这两项指标上明显优于传统的方法.

除了精度和召回率，算法占用的CPU运算时间也是评价算法优劣的重要指标：较大的CPU运算时间所对应的算法的用户数量也比较大；CPU运算时间越大，其所对应的算法效率越低.对两种算法的CPU占用时间进行对比，其结果如图3所示.由该图可知，本文提出的方法具有更低的CPU占用时间，表明提出的方法具有更高的计算效率.

3 结束语

提出了一种基于双聚类技术和Top-n推荐的新型协同过滤算法.当使用网络服务数据集对所提算法进行测试时，基于双聚类技术的协同过滤算法推荐准确率较高.此外，提出的协同过滤方法具备更好的计算性能，在处理数据集时具有更高的灵活性，这是因为提出的双聚类协同过滤算法既涉及用户属性，又涉及项目特征.由此可知，与已有的方法相比，双聚类协同过滤算法可以缓解稀疏问题，大幅度提高了网络服务的推荐质量.

参考文献

[1] 占渊, 肖蓉, 缪仲凯,等. 基于改进的协同过滤相似性度量算法研究[J]. 计算机测量与控制, 2017, 25(9): 287-290.

[2] HUANG Z,ZENG D,CHEN H. A comparison of collaborative-filtering algorithms for ecommerce[J]. Intelligent Systems IEEE, 2015, 22(5): 68-78.

[3] 赵喜玲, 张晓惠. 基于动态特征和静态特征融合的步态识别方法[J]. 湘潭大学自然科学学报, 2017, 39(4): 89-91.

[4] VIMALKUMAR B,HIMALAY H P. Optimization of the neighbor parameter of k-nearest neighbor algorithm for collaborative filtering[C]//International Conference on Communication and Networks, 2017: 87-93.

[5] WANG Z,YU N,WANG J. Collaborative filtering recommendation algorithm based on matrix factorization and user nearest neighbors[C]//Asian Simulation Conference, 2016: 199-207.

[6] PENG Y,CHENG X P. A collaborative filtering recommendation algorithm based on adaptive nearest neighbor selection[J]. Computer Knowledge & Technology, 2016, 16(4): 33-41.

[7] LY A,MARSMAN M,WAGENMAKERS E J. Analytic posteriors for Pearson’s correlation coefficient[J]. Statistica Neerlandica, 2017, 12(3): 108-116.

[8] 刘云, 王颖, 亓国涛, 等. 时间上下文的协同过滤Top-N推荐算法[J]. 计算机技术与发展, 2017, 27(7): 79-82.

[9] NITOBE T,YASUNO T,KANEKO S. Firearm classification based on extensive jaccard index of 3D cross-sectioned shape of firing pin impression on fired cartridge cases[J]. Journal of the Japan Society for Precision Engineering, 2017, 83(4): 355-360.