基于奇异值分解算法的聚类协同过滤推荐系统

1.基于奇异值分解算法的聚类协同过滤推荐系统，其特征在于，在计算用户相似度之前，首先将系统中的每个用户根据特定的聚类算法划分到不同的聚类中去，这样可以有效的降低用户-商品评分矩阵的维度，提高系统的推荐效率；其次将常用于图像处理与自然语言处理技术中的奇异值分解(SVD)算法改进后应用到推荐系统中去，将用户-商品矩阵分解之后再聚合，从而得出第一次预测后的商品评分，来计算用户间的相似度，这样可以有效的解决推荐系统中常见的矩阵稀疏问题；
其中，实现方案共分为两个步骤，聚类和利用SVD算法填充用户-商品矩阵；聚类负责利用用户的属性特征值将系统中原有的大量用户-商品信息分类到多个小的聚类中去，用户特征值包括：性别，年龄以及职业，通过多次试验数据分析，取出每个特征值所占的权重，从而得出一个最佳计算综合属性特征值的聚类公式；利用SVD算法填充用户-商品矩阵负责将该用户所在聚类中的用户-商品评分矩阵中未评分的项通过分解后聚合填充，利用以上两个步骤可以降低系统计算维度，解决系统稀疏性问题，从而大大提高推荐的效率与准确率；
利用SVD算法填充用户-商品矩阵包括以下步骤：
S1，求出初始评分矩阵R每一列中的商品评分的平均分ri；其中，所述初始评分矩阵R是m×n的二维矩阵，m表示用户的个数，n表示商品的个数，未评分的项目填充为0；
S2，将所述初始评分矩阵R中每一个具有非0评分值rui的项全部替换成所述非0评分值减去所述初始评分矩阵R每一列中的商品评分的平均分而得到的值，得到矩阵R’；
S3，利用SVD算法，将所述矩阵R’分解成U、S、V三个矩阵；
S4，将所述矩阵S中小于1的值全部设为0，然后将所有数值为0的行和列删除，生成矩阵Sk；将所述矩阵U中小于1的值全部设为0，然后将所有数值为0的行和列删除，生成矩阵Uk；将所述矩阵V中小于1的值全部设为0，然后将所有数值为0的行和列删除，生成矩阵Vk；其中，所述矩阵Sk为k×k的二维矩阵，所述矩阵Uk为m×k的二维矩阵，所述矩阵Vk为k×n的二维矩阵；
S5，计算所述矩阵Sk的平方根Sk1/2，分别求出两个矩阵A＝Uk×Sk1/2，B＝Sk1/2×Vk；
S6，将每一个所述初始评分矩阵R中未评分的项目Rui进行预测评分后所得的项目PRui填充到所述初始评分矩阵R中，得到矩阵PR；其中， Ru为用户u评分的平均值，Am表示矩阵A的第m行，Bn表示矩阵B的第n列。
2.根据权利要求1所述的基于奇异值分解算法的聚类协同过滤推荐系统，其特征在于，利用SVD算法填充用户-商品矩阵负责将该用户所在聚类中的用户-商品评分矩阵中未评分的项通过分解后聚合填充；该步骤首先找出用户所在聚类，将聚类中的用户-商品评分矩阵利用SVD算法进行分解，通过处理后在聚合，从而得到第一次预测的商品评分，利用这些预测评分可以计算出同一个聚类之间用户的相似度，降低系统数据稀疏性问题；在计算完指定用户所在聚类用户间相似度后，利用已得相似度，对原有的用户-商品评分矩阵进行第二次评分预测，从而得出最后的推荐结果。
3.根据权利要求1所述的基于奇异值分解算法的聚类协同过滤推荐系统，其特征在于，当一个用户注册登录之后，系统通过他的性别，年龄和职业计算出用户的属性特征值找到该用户所在聚类，利用SVD算法得出与该用户兴趣爱好最相似的k个用户，并且通过计算商品的预测评分，最后对该用户做出准确的推荐。

基于奇异值分解算法的聚类协同过滤推荐系统\n技术领域\n[0001] 本发明属于电子商务推荐系统领域，具体涉及集成多种技术，如数据挖掘技术、机器学习技术、自然语言处理技术等，实现将聚类与奇异值分解(SVD)技术结合的一种推荐方法。\n背景技术\n[0002] 近年来，随着互联网技术的迅猛发展，电子商务已经成为一种新的时尚，在近些年形成飞速增长的趋势。电子商务，它是IT技术与商务行为结合所产生的一种新的商务交易过程，是21世纪市场经济商务运行的主要模式，通过电子商务平台，人们可以享受足不出户选购商品的快捷与方便。随着电子商务平台交易规模的扩大，人们通过浏览器无法在短时间内快速的浏览所有的商品，并且也缺少现实交易中售货员对顾客进行的一些产品介绍，因此人们面临了电子商务时代特有的“信息超载”问题。\n[0003] 针对于“信息超载”问题，推荐系统在20世纪90年代应运而生，如Google的新闻推荐、Email过滤等等。目前几乎所有的电子商务系统，都将推荐技术作为网上销售的必然组成部分，如Amazon，Netflix，豆瓣，淘宝等等。推荐系统的主要作用有：(1)诱导新客户，也就是向一个潜在的新客户推荐产品，将浏览者变成购买者；(2)鼓励老客户，也就是在客户已买的东西的基础上推荐更多产品，提高网络的交叉销售能力；(3)提升顾客对网站的忠诚度。准确率，可扩展性，实时性是评价一个推荐系统好坏与否的重要因素。然而随着人们越来越热衷于网上购物，目前的推荐系统面临着“信息超载”的问题，由于系统中的数据量过于庞大，导致目前的一些推荐技术不能实时快速有效的做出推荐；与此同时，一个一直困扰着推荐系统的问题就是局部数据稀疏性问题，尽管一个系统中的数据量极大，但是对于每个单一用户，其浏览与购买的商品所占系统中总的商品数的比例实在太小，这就导致计算用户相似度的问题上无法做到准确有效，这样大大的影响了推荐的结果。因此如何解决上述两个问题成为了推荐系统亟待解决的主要问题。\n[0004] 本专利采用基于奇异值分解算法的聚类协同过滤推荐技术，通过将用户先分类，降低用户-商品评分矩阵的维度，然后利用奇异值分解(SVD)算法，在用户所在聚类中将评分矩阵分解后聚合，从而填充矩阵中的未评分项的预测得分，最后通过协同过滤技术做出最终的推荐。该技术可以提高系统推荐效率，解决推荐系统数据稀疏性等问题并且可以提高系统的推荐准确率。\n发明内容\n[0005] 本发明提出通过利用聚类算法与奇异值分解(SVD)算法相结合的技术来改善推荐系统的推荐效率与准确率。导致传统推荐系统推荐效率较低的主要原因是由于推荐系统中存在的用户数与商品数量过多，而传统的推荐系统必须通过计算每两个用户或商品之间的相似性，来找出与指定用户或者商品相似度最高的k个最近邻来做出推荐，由于计算量过于庞大，而且不是每一次的计算都是必要的，因此导致推荐效率降低；导致传统推荐系统推荐准确率较低的主要原因是由于尽管一个系统中的数据量很庞大，但是对于每个单一用户，其浏览与购买的商品所占系统中总的商品数的比例实在太小，这种局部数据稀疏性就导致计算用户相似度的问题上无法做到准确有效，这样大大的影响了推荐的准确率。本发明通过聚类算法解决推荐效率问题，而利用SVD算法解决局部数据稀疏性问题，从而改善推荐结果。\n[0006] 本发明技术方案分为如下几个基本的执行步骤：\n[0007] 步骤一：利用用户特征值，包括性别、年龄、职业，将系统中已有用户分到n个聚类中去，并且计算出每个聚类的聚类中心值；\n[0008] 步骤二：对于每个新注册的用户，计算出该用户属性特征值，将该值与每个聚类中心值进行比较，找出最相近的一个聚类，将该新用户加入进去，并且改变该聚类的聚类中心值；\n[0009] 步骤三：对于每个登录用户，找到该用户所在聚类，将该聚类中的用户-商品评分矩阵取出来，并且依照一定得规则，利用SVD算法将该评分矩阵进行分解，将分解后的矩阵进行处理后再聚合，从而得到原有矩阵中每一个未评分商品的预测评分；\n[0010] 步骤四：利用得到的新评分矩阵，计算该登录用户与该矩阵中每个用户的相似度，找出相似度最高的k个用户作为他的最近邻；\n[0011] 步骤五：利用基于用户的协同过滤方法和步骤四中得到的登录用户的最近邻相似度，对原有评分矩阵中的每个未评分商品进行评分预测，最后得到最佳推荐结果，并将该结果推荐给用户。\n[0012] 本发明有以下一些技术特征：\n[0013] (1)步骤1所述的聚类算法是利用数据挖掘中有名的k-means聚类算法原理，在本发明中提出了一种适用于推荐系统的新聚类算法，通过利用用户注册信息中的性别，年龄和职业等属性，利用多次实验数据找出最优的每个属性特征的权值，从而得出一个计算用户综合属性特征值的公式，在根据该用户综合属性特征值进行聚类；\n[0014] (2)步骤2所述的过程其实就是不断向系统数据库中添加新数据的过程，通过注册后的计算新用户综合属性特征值，来对新用户进行聚类，可以在以后每次用户登录的时候，快速的找到该用户所在聚类，提高系统的效率；\n[0015] (3)步骤3所述的SVD算法，主要用来解决系统局部数据稀疏性的问题。SVD算法通常用于图像处理以及自然语言处理等领域，本发明将这一方法改进后，利用到推荐技术中去，通过第一次计算用户-商品评分矩阵中未评分商品的预测评分，来解决系统局部数据稀疏性的问题。\n[0016] (4)步骤4所述的过程，不是单纯的以步骤3中所得到的未评分商品的预测评分来进行推荐，而是通过步骤3中所得到的评分来计算同一个聚类中的用户相似度，通过SVD算法分解聚合后的评分矩阵，使得用户相似度的计算更加准确。\n[0017] (5)步骤5所述的过程，是本发明推荐系统中最后的推荐部分，通过步骤4找到目标用户的k个最近邻，利用传统的基于用户的协同过滤推荐方法，计算出原用户-商品矩阵中未评分商品的预测评分，并将最后的结果推荐给目标用户。\n具体实施方式\n[0018] 为使本发明的目的、技术方案及优点更加清楚明白，以下将举实例对本发明做进一步详细地说明。\n[0019] 1.利用用户属性特征值分类的聚类算法\n[0020] 本发明中，我们利用用户综合属性特征值来对用户进行聚类划分。通常，每个用户都拥有自己的个人特征，如工资、籍贯、性别、职业、年龄等等。根据知名的咨询公司艾瑞对中国网民的消费形态进行了统计，消费者的消费情况可以根据用户的不同属性来划分。而通常用户在注册时候可以收集到的信息包括性别、年龄以及职业，而这3种属性又恰恰可以很好的反映出一个用户的特征。因此我们可以利用以上属性来对用户进行分类，并且通过具体的计算公式为：muc(u)＝aS(u)+βA(u)+γO(u)，来计算用户的属性特征值。其中a+β+γ＝1，它们分别为各个属性的相关系数。muc(u)表示用户u的综合属性特征值，[0021] S(u)表示用户u的性别特征值，\n[0022] A(u)表示用户u的年龄特征值，\n[0023] O(u)表示用户u的职业特征值，\n[0024] 通过以上公式得出用户的n个聚类，并且对于每个新用户，利用公式muc(u)＝aS(u)+βA(u)+γO(u)，其中a+β+γ＝1，来找到该用户所在聚类，以便接下来在该聚类中找到该用户的最近邻，通过大量数据实验表明，当a＝0.2，β＝0.5，γ＝0.3时该方法得到的聚类效果最好。\n[0025] 若一个系统目前有3个聚类A，B，C。A的聚类中心属性特征值是0.32，聚类中用户数为8，B的聚类中心属性特征值是0.65，聚类中用户数为9，C的聚类中心属性特征值是0.89，聚类中用户数为10。一个新用户a在此系统中注册，他的性别是男，年龄是28岁，职业是高中老师，属于文化类职业子树。那么根据上诉公式，我们可以得到用户a的属性特征值muc(a)＝0.2*1+0.5*(28-15)/40+0.3*0.5＝0.51，将该值分别与3个聚类中心值做差后取绝对值，找到最小的一个，发现该值与B聚类中心最为接近，因此将a加入到聚类B中，并且改变B聚类中心的特征值为(9*0.65+0.51)/10＝0.64.\n[0026] 2.奇异值分解(SVD)算法\n[0027] 奇异值分解(Singular Value Decomposition，SVD)是一种矩阵分解技术，它深刻揭露了矩阵的内部结构，奇异值分解在图像压缩、最小二乘法、自然语言处理等方面有着广泛的应用。它可将一个m×n(假设m≥n)的矩阵R分解为三个矩阵U，S，V：R＝U×S×VT，其中U是一个m×m的正交矩阵(UUT＝I)，V是一个n×n的正交矩阵(VVT＝I)，S是一个m×n的对角矩阵，其非对角线上的元素全为0，而对角线上的元素满足σ1≥σ2≥…≥σn≥0，所有的σn大于\n0并按照从大到小顺序排列，称为奇异值(Singular Value)，奇异值可以表示一个给定矩阵与比其秩低的矩阵的接近程度。\n[0028] 3.利用SVD算法分解用户-商品评分矩阵方法\n[0029] 本方法利用SVD算法来解决用户-商品矩阵中未评分项目的稀疏性问题，利用聚合填充之后的评分矩阵来计算用户之间的相似度，从而提高系统的推荐准确性。\n[0030] 算法：\n[0031] 输入：初始评分矩阵R(R是m×n的二维矩阵，m表示有m个用户，n表示有n个商品，未评分的项目填充为0)\n[0032] 输出：将每个用户u对未评分项目i的预测评分加进原有初始评分矩阵的矩阵PR[0033] (1)求出每一列中的商品评分的平均分ri；\n[0034] 大到小排列的，因此将S矩阵中所有数值为0的行和列删除，生成新的Sk对角矩阵(相当于保留前K行和前K列)；\n[0035] (5)根据简化的Sk，相应将U，V矩阵简化为UK，VK矩阵，UK为m×k的二维矩阵，VK为k×n的二维矩阵；\n[0036] (6)计算Sk的平方根Sk1/2，分别求出两个矩阵A＝Uk×Sk1/2；B＝Sk1/2×Vk；\n[0037] (7)填充PR矩阵，对于每一个初始矩阵R中未评分的项目Rui， (\n为用户u评分的平均值，Am表示矩阵A的第m行，Bn表示矩阵B的第n列)；\n[0038] 4.利用传统的基于用户的协同过滤推荐方法计算相似度与预测评分值[0039] 经典的协同过滤算法有以下三种：普通的余弦相似性；Pearson系数以及修正的余弦相似性。本发明采用皮尔逊系数方法来求解用户间相似度。公式如下：\n其中Iuv表示用户u和v共同评分过的项目，PRui，\nPRvi分别表示在PR矩阵中用户u和v对商品i的评分； 和 分别表示PR矩阵中用户u和v对所有商品的平均得分。由于PR矩阵是经过SVD算法分解再聚合产生的，因此用户对商品的评分信息大量增加，有效的解决了数据稀疏性导致的相似性计算不准确问题。根据上式求出的相似度，找出k个和用户u相似度最高的用户，利用预测评分公式对初始矩阵R中的未评分项进行预测评分， 这里，N(u，k)表示和用户u兴趣最相\n似k个用户的集合，U(i)是对物品i评过分的用户集合，Rvi是用户v对物品i的评分， 和分别是用户v和用户u所有评过分物品的评分平均值。最后计算出所有未评分的商品预测评分，将最优的结果推荐给用户。