论文部分内容阅读
[摘要] Web数据挖掘是从Web文档和Web活动中发现并抽取感兴趣的、潜在的有用模式和隐藏的信息。基于Web数据挖掘的电子商务推荐系统可以满足电子商务未来发展趋势的需要。在本文中依据效率和准确性，建立了一个推荐系统模型，并对系统中各个模块功能及它们之间相互协调工作做了详细的描述；深入研究了电子商务推荐系统所使用的推荐算法，重点讨论了目前使用最为广泛的协同过滤推荐算法；在上述研究的基础上设计了基于聚类的协同过滤推荐系统，并对k-means聚类算法进行了改进；给出了系统试验结果，并对结果做出解释和评价。
[关键词] Web日志 数据挖掘 电子商务 关联规则 聚类算法
Web数据挖掘是数据挖掘的一个重要分支，是随着数据库技术、人工智能技术和网络技术的发展而提出的。尤其是随着电子商务的不断运作，信息总量不断增加，更迫切需要有效的信息分析工具。
当今，电子商务正以其成本低廉、快捷、不受时空限制等优点而逐步全球流行。在这种新型的商务模式下，却遇到了网络信息量和基于Web的应用的一些阻碍。一方面，没有针对性地提供信息，访问者不能快捷地获得所需；另一方面，不能快捷地在站点上寻找到感兴趣的商品，用户容易转向访问其他站点，造成客户流失，这些对站点企业来说都是致命的。
基于上述原因，商务站点“个性化”营销孕育而生。而个性化所涵盖的内容中，针对用户的推荐服务是最为重要的，因为它能够改变这种“大众化”的方式，向用户提供个性化的信息。推荐系统模拟商店销售人员向用户提供商品推荐，帮助用户找到所需商品，从而顺利完成购买过程，因此可以有效保留用户，提高电子商务系统的销售；商家也可以通过推荐系统保持与客户的联系，重建客户关系。
本文将对电子商务推荐系统中的若干关键技术进行有益的探索和研究。
一、电子商务推荐算法及改进
电子商务推荐算法是整个推荐系统的核心，其推荐精度和推荐效率直接影响推荐系统的整体性能。目前典型的推荐算法有基于关联规则的推荐算法和基于用户的协同过滤推荐算法。
1.基于关联规则的推荐算法
基于关联规则的推荐算法可以分为离线的关联规则推荐模型建立阶段和在线的关联规则推荐模型应用阶段。离线阶段使用各种关联规则挖掘算法建立关联规则推荐模型，这一步比较费时，但可以离线周期进行;在线阶段根据建立的关联规则推荐模型和用户的购买行为向用户提供实时的推荐服务。
2.协同过滤推荐算法
协同过滤推荐是目前最成功的电子商务推荐技术，被应用到很多领域中。协同过滤根据用户的行为（如用户注册信息、用户评分数据、用户购买行为等）建立用户的行为模型，然后利用建立的行为模型向用户推荐有价值的商品。用户数据的收集在协同过滤推荐算法中占有重要地位，如何有效收集高质量的用户数据直接关系到推荐算法的推荐效果。
3.基于聚类的协同过滤算法概述
随着电子商务系统的进一步扩大，协同过滤推荐算法的实时性要求遇到了巨大挑战。在一个用户和商品均数以万计的系统中，同时为数以万计的用户提供实时的推荐服务越来越困难。
为了解决推荐系统中存在的上述问题，進行实时推荐，那么就需要提高推荐的速度。因此，提出了基于聚类的协同过滤推荐算法。将整个用户空间根据用户的购买习惯和评分特点划分为若干个不同的聚类，从而使得聚类内部用户对项的评分尽可能相似，而不同聚类间用户对商品的评分尽可能不同。根据每个聚类中用户对商品的评分信息生成一个虚拟用户，虚拟用户代表了该聚类中用户对商品的典型评分，将所有虚拟用户对商品的评分作为新的搜索空间，查询当前用户在虚拟用户空间中的最近邻居，产生对应的推荐结果。
4.改进的k-means聚类算法
(1)k-means聚类算法。k-means聚类算法是最简单同时也是非常有效的聚类算法。采用k-means聚类算法对整个用户空间进行聚类的主要步骤如下：
①随机选择k个用户作为初始的簇中心，将k个用户对项的评分数据作为初始的聚类中心。
②对剩余的用户集合，计算每个用户与k个聚类中心的相似性，将每个用户分配到相似性最高的聚类中。
③对新生成的聚类，计算聚类中所有用户对项的平均评分，生成新的聚类中心。
④重复以上2到3步，直到聚类不再发生改变为止。
(2)改进的k-means聚类算法。在k-means算法中，k个中心的选取一般为随机选取或依赖于领域知识。为了更好地选取k个中心以提高聚类的质量，需要对k-means算法进行改进。算法2-1给出了改进后的算法描述。
算法2-1改进k-means算法。定义：（推荐池T）设站点共有m个页面，共有n次用户的访问，由于采用协作推荐方法，那么推荐池T就是内存中的一个n×(m+l)的矩阵。其中每一行代表一个用户访问的页面集;在前m列中，每一列表示用户对该页面的访问时间长度;每一个矩阵项表示个用户在一个页面上的访问时间，即该用户对该页面的访问兴趣度大小。第m+l列表征该行被加入到推荐池中的时间，这是为了对该推荐池保持一个按时间新旧程度运行的替换策略。
输入：初始簇K，推荐池T
输出：推荐池的中心集合CenterSet
①k=[K/2];//起始时取「K/2」值作为k-means算法的初始k值。
②将评分项为0的各项以某一均值(或者设定的值)θ代替;//避免出现大规模稀疏矩阵影响推荐质量。
③initialize(T,CenterSet,k);//随机选取k个初始的中心。
④WHILE k<=K DO BEGIN
⑤CenterSet=k-means(T,k,CenterSet);//进行聚类操作得到k个中心//找到一个新中心
⑥max=0;newcenter=null
⑦FOR each c∈T DO BEGIN
⑧d=0;
⑨FOR each c∈CenterSet DO BEGIN
⑩d=d+distance(T,t,c);
END
IF d>max THEN BEGIN
max=d;
Newcenter=t;
END
END
CenterSet=CenterSet∪{newcenter}
k=k+1;
END
RETURN CenterSet;
5.对改进的k-means算法进行分析
在每一遍k-means算法执行后，选取一个距离各中心距离和最大的元素作为新的中心。该算法的改进之处有三点：
(1)改变了传统的k-means算法要求用户必须事先给出k(要生成的聚类数目)值，以及对于设定的不同k值导致不同聚类结果的缺点。
(2)避免了某些页面因为没有被访问得到评分为0而形成的大规模稀疏矩阵问题。
(3)改进的k-means算法由于在每一次算法执行后是选取一个距离各中心距离和最大的元素作为新的中心，这个元素来自原来的样本数据库，原来的距离矩阵数据仍然可以重用，因此不需要重新计算每一个对象与新的平均值点间的距离。
该算法的缺点是：只有当聚类数目远小于项数目时，计算目标项与聚类中心相似性的时间代价相对于最近邻查询才可以忽略不计，当聚类数目很大的时候，计算目标项与聚类中心相似性的代价并不能忽略不计。
二、电子商务推荐系统的实现
我们将系统分为三个模块：数据预处理模块、模式挖掘模块和模式分析及应用模块。
1.实现模型
由此，基于Web日志挖掘的电子商务推荐系统的结构分成在线和离线两个部分，三个模块。如图1所示：
图1电子商务推荐系统结构图
2.离线模块
一般情况下，推荐系统的离线部分主要针对的是注册用户，根据用户提供的关键信息对推荐集合进行净化，从而在推荐页面集合上体现精确的用户感兴趣的信息，如笔者参与设计的某搜饭网，对于注册用户“馋嘴鸭”，在注册过程中，提交的用户所在地关键字是“市南区”，那么一旦该用户登录系统，则直接将跟市南区有关的推荐页面展示在用户窗口，如图2所示:
图2 地区来源是市南区的注册用户推荐页面
3.在线模块
在线模式下又分成两种情况，一是注册用户登录，二是随机非注册用户。对于注册用户来讲，可以任意变更兴趣项，而推荐系统会根据用户的选择，形成推荐集合并展示精确的推荐页面，如果变更的兴趣项不包含注册用户的关键信息，则推荐集合在原推荐集中产生，这样用户得到的推荐页面更加精确。
对于随机用户，推荐页面与用户兴趣关系密切，同时其精确程度很大程度上依赖用户的兴趣项的选取。即用户的兴趣项约束越多则推荐页面越精确，这种情况是以牺牲用户时间为代价的。经过用户的一系列选择后，推荐系统最后生成推荐页面，如某随机用户对菜品类别（咖啡）、地区（市南）进行选择后生成的推荐页面。如图3所示。
图3 随机用户选择后的推荐页面
三、结论
目前Web数据挖掘己逐步成为网络研究、数据挖掘、知识发现、软件代理等领域的热点问题。研究日志挖掘，对于优化Web站点、电子商务、远程教育、信息检索等领域，都有着十分重要的意义。然而，如何将这些技术深入、完善，并尽快运用到Internet各种应用中，是摆在我们面前的新课题。
参考文献:
[1]邹显春等:电子商务与Web数据挖掘[J].计算机应用,2000.4
[2]P.Buono,M.F.Costabile,S.Guida,A.Piccinno,G.Tesoro,Integrating UserData and Collaborative Filter in a Web Recommendation System,UM2001-Proc.Third Workshop on Adaptive Hypertext HypermediaSonthofen,Germany,July 2001，129-140
[3]Fayyad U,Piatetsky-Shapiro G,and Smyth P.Knowledge discovery anddata mining:Towards a unifying framework
[4]Grdon S.Linoff，Michael J.A.Berry著,沈均毅等譯.Web数据挖掘:将客户数据转化为客户价值[M].电子工业出版社,2004.3
[5]赵艳霞梁昌勇:基于关联规则的推荐系统在电子商务中的应用[J].价值工程,2006年第5期
[6]林瑞娟侯德文:Web挖掘及其在电子商务中的应用研究[J].计算机技术与发展,2006(8):178-191
[关键词] Web日志 数据挖掘 电子商务 关联规则 聚类算法
Web数据挖掘是数据挖掘的一个重要分支，是随着数据库技术、人工智能技术和网络技术的发展而提出的。尤其是随着电子商务的不断运作，信息总量不断增加，更迫切需要有效的信息分析工具。
当今，电子商务正以其成本低廉、快捷、不受时空限制等优点而逐步全球流行。在这种新型的商务模式下，却遇到了网络信息量和基于Web的应用的一些阻碍。一方面，没有针对性地提供信息，访问者不能快捷地获得所需；另一方面，不能快捷地在站点上寻找到感兴趣的商品，用户容易转向访问其他站点，造成客户流失，这些对站点企业来说都是致命的。
基于上述原因，商务站点“个性化”营销孕育而生。而个性化所涵盖的内容中，针对用户的推荐服务是最为重要的，因为它能够改变这种“大众化”的方式，向用户提供个性化的信息。推荐系统模拟商店销售人员向用户提供商品推荐，帮助用户找到所需商品，从而顺利完成购买过程，因此可以有效保留用户，提高电子商务系统的销售；商家也可以通过推荐系统保持与客户的联系，重建客户关系。
本文将对电子商务推荐系统中的若干关键技术进行有益的探索和研究。
一、电子商务推荐算法及改进
电子商务推荐算法是整个推荐系统的核心，其推荐精度和推荐效率直接影响推荐系统的整体性能。目前典型的推荐算法有基于关联规则的推荐算法和基于用户的协同过滤推荐算法。
1.基于关联规则的推荐算法
基于关联规则的推荐算法可以分为离线的关联规则推荐模型建立阶段和在线的关联规则推荐模型应用阶段。离线阶段使用各种关联规则挖掘算法建立关联规则推荐模型，这一步比较费时，但可以离线周期进行;在线阶段根据建立的关联规则推荐模型和用户的购买行为向用户提供实时的推荐服务。
2.协同过滤推荐算法
协同过滤推荐是目前最成功的电子商务推荐技术，被应用到很多领域中。协同过滤根据用户的行为（如用户注册信息、用户评分数据、用户购买行为等）建立用户的行为模型，然后利用建立的行为模型向用户推荐有价值的商品。用户数据的收集在协同过滤推荐算法中占有重要地位，如何有效收集高质量的用户数据直接关系到推荐算法的推荐效果。
3.基于聚类的协同过滤算法概述
随着电子商务系统的进一步扩大，协同过滤推荐算法的实时性要求遇到了巨大挑战。在一个用户和商品均数以万计的系统中，同时为数以万计的用户提供实时的推荐服务越来越困难。
为了解决推荐系统中存在的上述问题，進行实时推荐，那么就需要提高推荐的速度。因此，提出了基于聚类的协同过滤推荐算法。将整个用户空间根据用户的购买习惯和评分特点划分为若干个不同的聚类，从而使得聚类内部用户对项的评分尽可能相似，而不同聚类间用户对商品的评分尽可能不同。根据每个聚类中用户对商品的评分信息生成一个虚拟用户，虚拟用户代表了该聚类中用户对商品的典型评分，将所有虚拟用户对商品的评分作为新的搜索空间，查询当前用户在虚拟用户空间中的最近邻居，产生对应的推荐结果。
4.改进的k-means聚类算法
(1)k-means聚类算法。k-means聚类算法是最简单同时也是非常有效的聚类算法。采用k-means聚类算法对整个用户空间进行聚类的主要步骤如下：
①随机选择k个用户作为初始的簇中心，将k个用户对项的评分数据作为初始的聚类中心。
②对剩余的用户集合，计算每个用户与k个聚类中心的相似性，将每个用户分配到相似性最高的聚类中。
③对新生成的聚类，计算聚类中所有用户对项的平均评分，生成新的聚类中心。
④重复以上2到3步，直到聚类不再发生改变为止。
(2)改进的k-means聚类算法。在k-means算法中，k个中心的选取一般为随机选取或依赖于领域知识。为了更好地选取k个中心以提高聚类的质量，需要对k-means算法进行改进。算法2-1给出了改进后的算法描述。
算法2-1改进k-means算法。定义：（推荐池T）设站点共有m个页面，共有n次用户的访问，由于采用协作推荐方法，那么推荐池T就是内存中的一个n×(m+l)的矩阵。其中每一行代表一个用户访问的页面集;在前m列中，每一列表示用户对该页面的访问时间长度;每一个矩阵项表示个用户在一个页面上的访问时间，即该用户对该页面的访问兴趣度大小。第m+l列表征该行被加入到推荐池中的时间，这是为了对该推荐池保持一个按时间新旧程度运行的替换策略。
输入：初始簇K，推荐池T
输出：推荐池的中心集合CenterSet
①k=[K/2];//起始时取「K/2」值作为k-means算法的初始k值。
②将评分项为0的各项以某一均值(或者设定的值)θ代替;//避免出现大规模稀疏矩阵影响推荐质量。
③initialize(T,CenterSet,k);//随机选取k个初始的中心。
④WHILE k<=K DO BEGIN
⑤CenterSet=k-means(T,k,CenterSet);//进行聚类操作得到k个中心//找到一个新中心
⑥max=0;newcenter=null
⑦FOR each c∈T DO BEGIN
⑧d=0;
⑨FOR each c∈CenterSet DO BEGIN
⑩d=d+distance(T,t,c);
END
IF d>max THEN BEGIN
max=d;
Newcenter=t;
END
END
CenterSet=CenterSet∪{newcenter}
k=k+1;
END
RETURN CenterSet;
5.对改进的k-means算法进行分析
在每一遍k-means算法执行后，选取一个距离各中心距离和最大的元素作为新的中心。该算法的改进之处有三点：
(1)改变了传统的k-means算法要求用户必须事先给出k(要生成的聚类数目)值，以及对于设定的不同k值导致不同聚类结果的缺点。
(2)避免了某些页面因为没有被访问得到评分为0而形成的大规模稀疏矩阵问题。
(3)改进的k-means算法由于在每一次算法执行后是选取一个距离各中心距离和最大的元素作为新的中心，这个元素来自原来的样本数据库，原来的距离矩阵数据仍然可以重用，因此不需要重新计算每一个对象与新的平均值点间的距离。
该算法的缺点是：只有当聚类数目远小于项数目时，计算目标项与聚类中心相似性的时间代价相对于最近邻查询才可以忽略不计，当聚类数目很大的时候，计算目标项与聚类中心相似性的代价并不能忽略不计。
二、电子商务推荐系统的实现
我们将系统分为三个模块：数据预处理模块、模式挖掘模块和模式分析及应用模块。
1.实现模型
由此，基于Web日志挖掘的电子商务推荐系统的结构分成在线和离线两个部分，三个模块。如图1所示：
图1电子商务推荐系统结构图
2.离线模块
一般情况下，推荐系统的离线部分主要针对的是注册用户，根据用户提供的关键信息对推荐集合进行净化，从而在推荐页面集合上体现精确的用户感兴趣的信息，如笔者参与设计的某搜饭网，对于注册用户“馋嘴鸭”，在注册过程中，提交的用户所在地关键字是“市南区”，那么一旦该用户登录系统，则直接将跟市南区有关的推荐页面展示在用户窗口，如图2所示:
图2 地区来源是市南区的注册用户推荐页面
3.在线模块
在线模式下又分成两种情况，一是注册用户登录，二是随机非注册用户。对于注册用户来讲，可以任意变更兴趣项，而推荐系统会根据用户的选择，形成推荐集合并展示精确的推荐页面，如果变更的兴趣项不包含注册用户的关键信息，则推荐集合在原推荐集中产生，这样用户得到的推荐页面更加精确。
对于随机用户，推荐页面与用户兴趣关系密切，同时其精确程度很大程度上依赖用户的兴趣项的选取。即用户的兴趣项约束越多则推荐页面越精确，这种情况是以牺牲用户时间为代价的。经过用户的一系列选择后，推荐系统最后生成推荐页面，如某随机用户对菜品类别（咖啡）、地区（市南）进行选择后生成的推荐页面。如图3所示。
图3 随机用户选择后的推荐页面
三、结论
目前Web数据挖掘己逐步成为网络研究、数据挖掘、知识发现、软件代理等领域的热点问题。研究日志挖掘，对于优化Web站点、电子商务、远程教育、信息检索等领域，都有着十分重要的意义。然而，如何将这些技术深入、完善，并尽快运用到Internet各种应用中，是摆在我们面前的新课题。
参考文献:
[1]邹显春等:电子商务与Web数据挖掘[J].计算机应用,2000.4
[2]P.Buono,M.F.Costabile,S.Guida,A.Piccinno,G.Tesoro,Integrating UserData and Collaborative Filter in a Web Recommendation System,UM2001-Proc.Third Workshop on Adaptive Hypertext HypermediaSonthofen,Germany,July 2001，129-140
[3]Fayyad U,Piatetsky-Shapiro G,and Smyth P.Knowledge discovery anddata mining:Towards a unifying framework
[4]Grdon S.Linoff，Michael J.A.Berry著,沈均毅等譯.Web数据挖掘:将客户数据转化为客户价值[M].电子工业出版社,2004.3
[5]赵艳霞梁昌勇:基于关联规则的推荐系统在电子商务中的应用[J].价值工程,2006年第5期
[6]林瑞娟侯德文:Web挖掘及其在电子商务中的应用研究[J].计算机技术与发展,2006(8):178-191