基于协作过滤的Web智能信息方法

基于协作过滤的Web智能信息推荐方法

[分类号]TP18修回日期：2010-04-141引言随着Internet的迅猛发展，全球Web站点数目迅速增长，如何为Web站点的用户提供优质的服务成为一个重要的研究课题。在许多探索性研究中，个性化信息服务(PersonalizedInformationService，PIS)[1]是一种崭新的智能信息服务方式。PIS的特征是信息服务系统根据每个用户的信息需求和用户的个性化模式，主动搜寻相关信息，并且利用在线智能推荐服务[2]或者推送(push)技术，准确地将用户所需的信息传送到相应的用户。在智能个性化信息服务中，最重要的服务是个性化信息推荐，目前已有一些个性化信息推荐方法。比较有代表性的方法有Schechter等人[3]提出的根据用户的访问路径模式进行推荐的方法；CooleyR等人[4]提出的从访问日志文件中提取用户的访问模式进行推荐的方法；Nasraoui[5]等人提出的采用聚类用户访问模式进行推荐的方法。这些方法能够实现对用户的信息推荐，但仍存在一些问题，主要包括：①多数个性化信息推荐方法没有考虑利用用户访问页面的时间特性。而时间特性是一种可利用的重要资源，即如果用户对某页面感兴趣，那么就会在该页面停留较长时间；反之，就会停留较短时间。②多数个性化信息推荐方法针对的是注册用户，较少考虑非注册用户的信息推荐。③多数个性化信息推荐方法没有考虑用户是否有新颖信息需求的偏好。针对现有个性化信息推荐方法存在的问题，本文设计了一种协作过滤方法，并将其应用到个性化信息推荐，提出了一种基于协作过滤的Web智能信息推荐方法(WIIRM)。2基于协作过滤的Web智能信息推荐方法处理流程本文提出的Web智能信息推荐方法(WIIRM)利用协作过滤实现信息推荐，其处理流程分为离线处理和在线推荐两部分。离线处理可分为两个步骤：①对日志文件进行数据预处理，获得各个用户带有时长的用户模式；②根据用户模式，利用协作过滤方法建立评价矩阵，计算各用户之间的相似度，选择一些具有较大相似度的用户作为相似用户。在线推荐可分为三个步骤：①监听并得到当前用户访问操作序列；②根据离线处理得到的用户间相似度、评价矩阵和在线推荐部分计算出的链接距离因子来计算候选页面的推荐值；③选择推荐值大于阈值的页面推荐给用户。WIIRM的处理流程图如图1所示。图1WIIRM流程WIIRM考虑了用户访问页面的时间特性，不需要用户注册，在推荐时考虑了页面的新颖性，同时实现了离线处理与在线推荐的结合。3离线处理3.1数据预处理[6]日志文件的数据预处理是进行离线处理和更新的基础，主要步骤包括：数据净化、用户识别、用户访问操作识别、路径完善和用户模式识别等。经过数据预处理后，可获得用户模式，并且生成每个用户的事务模式文件，每一个用户模式文件包含了若干个用户模式。由于WIIRM要考虑用户访问页面的时间特性，所以得到的是带有时长的用户模式。设L为用户访问操作集合，每一条访问记录l∈L包括：用户主机地址l.ip，用户ID号l.uid，被访问Web页的URL地址l.url，访问时间戳l.time和访问Web页的时长l.timelength。定义1：带有时长的用户模式定义为三元组，形式化表示如下：3.2协作过滤方法协作过滤[7]是一种共享用户间的兴趣和评价的重要技术，采用的方法是收集用户对评价项目的兴趣偏好，匹配出具有相似兴趣偏好的用户，对这些相似用户共享彼此的兴趣和评价。它能够为相似用户提供协作推荐。协作过滤方法的要素：①评价项目：用户进行评价的项目；②评价值：用户对评价项目的评价值，反映了用户对评价项目的偏好程度；③评价矩阵：多个用户对所有项目评价的二维矩阵，其中每列表示多个用户对一个评价项目的评价值，每行表示一个用户对所有评价项目的评价值。本文设计的协作过滤方法主要有三个步骤：①获取用户对评价项目的评价值，建立评价矩阵；②根据评价矩阵计算用户之间的相似度；③选择一些具有较大相似度的用户作为相似用户以用于协作推荐。3.2.1自动获取用户评价传统的协作过滤方法的主要问题是需要人为地提供评价，而本文设计的协作过滤方法对其进行了改进，根据用户模式自动获取用户评价，构建评价矩阵[8]。用户对一个页面的评价值由用户页面访问次数、页面相对时长、访问新鲜程度和页面重视程度多个因素决定，这些因素由定义2-5分别表示。这些因素都可以根据带有时长的用户模式来计算得出。用户对一个页面的评价值由定义6表示，评价矩阵的由定义7表示。评价矩阵是由多个评价值组成，而评价值是根据带有时长的用户模式计算获得。因此不需要人为地进行评价，实现了评价矩阵的自动获取。定义2：一个用户u访问一个页面WP的次数C(u，WP)定义为：在一个固定的时间段N内，一个用户访问页面WP的次数。定义3：一个用户u访问一个页面WP的页面相对时长TL(u，WP)用公式(1)表示。定义7：评价矩阵是各个用户对所有页面的p×q二维矩阵，其中p为用户数，q为所有页面的数量；每个列表示多个用户对一个页面的评价值，每个行表示一个用户对所有页面的评价值，每个行列交叉的评价值为一个用户对特定页面的评价值。如果一个用户没有访问某个页面WP，则该用户对WP的评价值为0。3.2.2计算用户间的相似度对于评价矩阵它的每一个列为多个用户对一个页面的评价(共q个页面)，它的每一行为一个用户对所有页面的评价(共有p个用户)，那么用户a和用户u的相似度s(u，a)采用Pearson相关性系数来计算，用公式(5)表示。3.2.3选择相似用户当计算出一个用户与其他所有用户的相似度后，选择一些具有较大相似度的用户作为该用户的相似用户。常用的选择相似用户的方法有两种：①阈值法：设置一个用户相似度阈值τ，选择与一个用户的相似度大于或等于τ的用户作为相似用户。设置高的阈值，将得到相似度较大的相似用户，但是也往往导致相似用户很少或没有，不利于协作推荐。②最优k个相似法：从大到小选择k个与用户相似度较大的用户作为相似用户。如果k值选择过大，会造成某些相似用户与该用户的相似度过小，降低协作推荐的准确度。本文采用阈值可调的阈值法或k值可调的最优k个相似法来选择相似用户，以便得到较为准确的相似用户。4在线推荐[9]要进行在线推荐，首先需要监听当前用户访问操作序列，通常采用URL重写、暂存Web服务器的日志文件等方法来进行监听，获取当前用户访问操作序列。在收集到当前用户访问操作序列以后，需要评估相似用户访问过的所有页面，选择适合的页面作为推荐项。评估候选页面需要考虑三个因素：①当前用户与候选页面对应用户的相似度。它反映了当前用户和其他用户的相似程度，是进行协作推荐的最重要因素，相似度越大越应该优先考虑。根据离线处理部分得到了用户间的相似度，就可直接获取当前用户与候选页面对应用户的相似度。②相似用户对候选页面的评价值。它反映了相似用户对候选页面的评价情况，由用户页面访问次数、页面相对时长、访问新鲜程度和页面重视程度多个因素决定，是进行协作推荐的重要因素，评价值越大越应该优先考虑。根据离线处理得到了评价矩阵，就可直接获取相似用户对候选页面的评价值。③候选页面与当前用户访问操作序列的物理距离。从新颖性的角度看，推荐一个物理链接上远离当前用户访问操作序列的页面是优先考虑的对象，论文定义链接距离因子表示这种选择策略。定义8：链接距离因子：给定页面拓扑有向图G=(V，E)，设r为当前用户访问操作序列，vr为当前的一个候选页面；d(v，r，G)表示v到r中的URL之间最小物理链接路径距离，v关于r链接距离因子计算公式为：设u为当前访问用户，r为当前用户访问操作序列，a为u的一个相似用户，vr为a访问过的一个候选页面，根据评估候选页面需要考虑的三个因素，候选页面v的推荐值计算公式如下：如果v属于当前用户访问操作序列，则链接距离因子为0，因而其推荐值也为0。设定最小推荐值阈值δ，对所有候选页面都计算推荐值，将大于或等于δ的候选页面作为推荐项，由所有推荐项构成的集合称为推荐集。推荐集由下式表示：在线推荐的完整算法如下所示，该算法采用阈值法确定相似用户。在线推荐的完整算法：输入：当前用户u的访问操作序列r，用户u和其他用户a的相似度s(u，a)，用户a对访问过的候选页面v的评价值E(a，v)，最小推荐值阈值δ，用户相似度阈值τ；输出：推荐集Recommend(u，r)。5实验结果与分析实验的平台是DELL服务器，其配置为P42.4G，内存512M，Windows2000Server操作系统，SQLServer2000数据库管理系统。编程工具是C++Builder5.5。实验数据取自建立站点的访问Log文件，总的数据量是一个月的访问记录。经过预处理，获得大约800个用户模式。实验的评价标准：从表1可以看出：设置各种参数得到的精度值都较小，而阈值为0.3时精度值最小，相对最好。这说明WIIRM给出的预测值与用户的实际评价值相差不大，WIlRM采用的选择相似用户方法是有效的。对在线推荐算法进行实验，得到的结果如图2所示。图2在线推荐算法的实验从图2可以看出：随着推荐过程的深入，推荐集的页面数没有减少，反而稍微增加。推荐集页面数的增加意味着推荐范围的拓宽，增加了用户选择新信息的可能性。这说明WIIRM给出的在线