

18 Web数据挖掘

“数据是一种宝贵的东西，并且会比系统本身持续更长时间。”——蒂姆·伯纳斯·李

18.1 介绍

就其规模，其创建的分布式和非协调性，底层平台的开放性以及由此带来的应用程序的多样性而言，Web在许多方面都有其独特的方面。 这种应用程序的例子包括电子商务，用户协作和社交Web分析。 由于Web既是创建和使用的分布式和不协调的性质，也是各种数据丰富的宝库。 这些数据可以是有关各种主题的知识来源，也可以是有关用户的个人信息。 除了Web上文档中可用的内容之外，Web的使用会以用户日志或Web事务的形式产生大量数据。 Web上有两种主要的数据类型供挖掘算法使用。

1. *Web内容信息：*该信息对应于用户创建的Web文档和链接。这些文件通过超文本链接相互链接。 　　

2. 文档数据：*文档数据是从万维网上的页面提取的。 这些提取方法中的一些在Chap.13. *关联数据：*Web可以看作是一张巨大的图表，其中包含页面对应于节点，并且链接对应于节点之间的边缘. 这种链接信息可以用很多方式使用，例如搜索Web或确定节点之间的相似性。

3. *Web使用数据：*该数据对应于Web应用程序启用的用户活动模式。 这些模式可能有各种类型。

4. *Web交易，评级和用户反馈：*Web用户经常在网上购买各种类型的商品，或者以评级的形式表达他们对特定产品的兴趣。 在这种情况下，可以利用购买行为和/或评级来推断不同用户的偏好。 在某些情况下，用户反馈以文本用户评论的形式提供，称为意见。

5. *Web日志：*用户浏览行为以Web日志的形式捕获，Web日志通常在大多数Web站点上维护。 这个浏览信息可以用来推断用户活动。

这些不同的数据类型自动定义Web上常见的应用程序类型。与不同的数据类型协调一致，这些应用程序也是以内容为中心或以使用为中心的。

1.*以内容为中心的应用程序：*Web上的文档和链接用于各种应用程序，如搜索，聚类和分类。这些应用程序的一些例子如下：

• *数据挖掘应用程序：*Web文档与不同类型的数据挖掘应用程序（如聚类和分类）结合使用。这些应用程序经常被Web门户用于组织页面。
• *Web爬行和资源发现：*Web是一个巨大的资源关于各种主题文件的知识。但是，这种资源在互联网上广泛分布，需要发现并存储在一个地方进行推断。
• *Web搜索：*Web搜索的目标是发现高质量的相关文档，以响应用户指定的一组关键字。如后面将会看到的那样，质量和相关性的概念由文档的链接和内容结构来定义。

•*Web链接挖掘：*在这些应用程序中，Web上的链接结构的实际或逻辑表示被挖掘以获取有用的见解。 Web结构的逻辑表示的示例包括社交和信息Web。社交Web是用户的链接Web，而信息Web是用户和对象的链接Web。

​ 2.*以使用为中心的应用程序：*开发Web上的用户活动以进行推理。 用户活动可以被挖掘的不同方式如下：

• 推荐系统：在这些情况下，使用产品评分或产品购买行为的偏好信息来向其他志趣相投的用户提供建议。
• Web日志分析：Web日志是网站所有者确定用户浏览相关模式的有用资源。 这些模式可用于进行推理，如发现异常模式，用户兴趣和最佳网站设计。

上述许多应用与本书中的其他章节重叠。例如，以内容为中心的数据挖掘应用已经在本书的前几章中介绍过，特别是在第13章关于挖掘文本数据。其中一些方法确实需要修改以考虑附加的链接数据。第19章社交Web分析讨论了许多关联挖掘应用。因此，本章将重点讨论其他章节未涉及的应用。在以内容为中心的应用程序中，将讨论Web爬行，搜索和排名。在以使用为中心的应用程序中，将讨论推荐系统和Web日志挖掘应用程序。

本章安排如下。18.2节讨论了Web爬虫和资源发现。搜索引擎索引和查询处理方法在18.3节。排名算法见18.4节。推荐系统在18.5节进行讨论。有关挖掘Web日志的方法在18.6节进行讨论。总结见18.7节。

18.2 Web爬行和资源发现

Web爬虫也被称为*蜘蛛* 或*机器人*。 Web爬行的主要动机是Web上的资源分布在全球的站点上。虽然Web浏览器提供图形用户界面以交互方式访问这些页面，但可用资源的全部功能不能仅通过浏览器使用。在许多应用中，例如搜索和知识发现，有必要在中心位置下载所有相关页面，以便机器学习算法有效地使用这些资源。

Web爬虫有许多应用程序。最重要和最着名的应用程序是搜索，其中下载的网页被编入索引，以提供对用户关键字查询的响应。所有知名搜索引擎，例如Google和Bing，都会使用搜寻器定期刷新其服务器上下载的Web资源。这些爬虫还被称为*通用爬虫*，因为它们旨在抓取Web上的所有页面，而不管它们的主题或位置如何。Web爬虫还用于商业智能，其中与特定主题相关的网站被抓取或者竞争对手的网站受到监控，并随着它们的变化而逐渐爬行。这些抓取工具也被称为*优先爬虫*，因为它们可以区分不同页面对于手头应用程序的相关性。

18.2.1 一个基本的爬虫算法

虽然爬虫的设计非常复杂，并且是分布式体系结构和许多进程或线程，下面描述了一个简单的顺序和通用爬行程序，它抓住了构建爬行程序的本质。

以一般方式描述的基本爬虫算法使用通用资源定位符（URL）S的种子集合以及选择算法A作为输入。算法A从URL的当前边界列表中决定下一个要爬取的文档。前沿列表表示从网页中提取的URL。这些是最终可以由抓取工具抓取的网页的候选人。选择算法A很重要，因为它规定了爬行程序用于发现资源的基本策略。例如，如果将新URL附加到边界列表的末尾，并且算法A从列表的开头选择文档，则这对应于宽度优先算法。

基本的爬虫算法进行如下。首先，将URL的种子集添加到边界列表中。在每次迭代中，选择算法A从边界列表中选择一个URL。该URL将从前沿列表中删除，然后使用HTTP协议进行提取。这与浏览器用于获取网页的机制相同。主要区别在于现在通过使用自动选择决定的自动化程序完成提取，而不是通过用户使用Web浏览器手动指定链接。抓取的页面存储在本地存储库中，并提取其中的URL。然后，这些网址将被添加到前沿列表中，前提是这些网址尚未被访问过。因此，需要维护哈希表形式的单独数据结构来存储所有访问的URL。在抓取工具的实际实现中，由于Web垃圾邮件，蜘蛛陷阱，主题偏好或仅限于边界列表大小的实际限制，并非所有未访问的URL都添加到边界列表中。这些问题将在稍后讨论。将相关URL添加到边界列表后，下一个迭代将重复该过程，并在列表中显示下一个URL。当前沿列表为空时，该过程终止。如果前沿列表为空，则不一定意味着整个Web已被抓取。这是因为Web没有强连接，并且大多数随机选择的种子集都无法访问许多页面。由于大多数实用搜寻引擎（例如搜索引擎）都是增量搜寻器，可以刷新先前搜寻的页面，因此如果需要，通常可以轻松识别先前搜寻的未访问种子并将其添加到边界列表中。对于较大的种子集（如先前已爬取的Web存储库），可以强大地抓取大多数页面。基本的爬虫算法如图18.1所示。

图18.1 基本的爬虫算法

因此，爬虫是一种图形搜索算法，通过解析网页并提取URL来发现来自节点的输出链接。 选择算法A的选择通常会导致抓取算法存在偏差，尤其是在由于资源限制而无法抓取所有相关页面的情况下。 例如，广度优先搜寻器更有可能抓取包含多个指向它的链接的页面。 有趣的是，这种偏见有时在抓取工具中是可取的，因为任何抓取工具都不可能为整个网页建立索引。 因为网页的不整齐通常与其*PageRank*（衡量网页质量的一种度量）密切相关，所以这种偏见并不一定是不可取的。 爬行程序使用算法A定义的各种其他选择策略。

​ 1.由于大多数通用搜寻器都是用于刷新先前搜寻的增量搜寻器，因此需要抓取频繁更改的页面。 更改频率可以通过重复先前对相同页面的抓取进行估计。 一些资源如新闻门户频繁更新。 因此，经常更新的页面可以由算法A选择。

​ 2.选择算法A可以从边界列表中选择具有高PageRank的网页。 PageRank的计算在18.4.1中进行讨论。

搜索引擎使用的商业爬虫使用一种惯例，多种因素的组合。

18.2.2 优先爬虫

在优先爬虫中，只有满足用户定义标准的页面需要被抓取。 该标准可以以页面中的关键字存在的形式，由机器学习算法定义的主题标准，关于页面位置的地理标准或不同标准的组合来指定。 通常，用户可以指定任意谓词，这构成了爬行的基础。 在这些情况下，主要变化是在爬行期间用于更新边界列表的方法。

​ 1.网页需要符合用户指定的标准，以便将其提取的URL添加到边界列表中。

​ 2.在某些情况下，可能会检查锚文本以确定网页与用户指定查询的相关性。

​ 3.在以上下文为重点的抓取工具中，抓取工具经过培训，可以了解相关页面距页面很近的可能性，即使网页本身与用户指定的标准本身并不直接相关。 例如，即使数据挖掘页面可能与“信息检索”查询不相关，关于“数据挖掘”的网页更可能指向“信息检索”的网页。来自这些页面的URL可能 被添加到边界列表中。 因此，启发式设计需要被设计成学习这种特定于环境的相关性。

也可以对算法A进行改变。例如，可以首先通过算法A选择具有更多相关锚文本的URL或者在Web地址中具有相关令牌的URL。诸如http://www.golf.com的URL ，网址中的“高尔夫”一词可能与“高尔夫”主题更相关，而不是网址中没有单词的网址。 书目注释包含了许多通常用于优先资源发现的启发式指示。

18.2.3 多线程

当爬行程序发出URL请求并等待它时，系统处于空闲状态，爬虫端没有工作。 这似乎是浪费资源。 加速爬行的一种自然方法是利用并发性。 这个想法是使用爬虫的多个线程来更新访问的URL和页面存储库的共享数据结构。 在这种情况下，在更新期间实施锁定或解锁相关数据结构的并发控制机制很重要。 并发设计可以显着加快爬网程序的执行速度，从而更有效地利用资源。 在大型搜索引擎的实际实现中，爬虫在地理上分布，每个“子爬虫”在其地理邻近处收集页面。

18.2.4 打击蜘蛛陷阱

抓取算法总是访问不同的网页的主要原因是它保存了一个以前访问过的URL列表，以便进行比较。 但是，某些购物网站会创建动态网址，其中访问的最后一个网页会附加到用户序列的末尾，以使服务器能够将URL中的用户动作序列记录下来供将来分析。 例如，当用户从http://www.examplesite.com/page1点击第2页的链接时，新动态创建的URL将为http://www.examplesite.com/page1/page2。 进一步访问的页面将继续附加到URL的末尾，即使这些页面之前已经访问过。 解决这个问题的一种自然方法是限制URL的最大大小。 此外，还可以对从特定站点爬网的URL的数量设置最大限制。

18.2.5 用于重复检测的Shingling算法

爬虫收集的网页的主要问题之一是可能会抓取同一页面上的许多重复内容。 这是因为同一网页可能会在多个网站上进行镜像。 因此，检测接近重复的能力至关重要。 被称为shingling的方法通常用于此目的。 文档中的k-shingle就是文档中连续出现的k个字符串。 一个shingle也可以被视为一个*k-gram*。 例如，考虑包含以下句子的文档：

Mary had a little lamb, its fleece was white as snow.

从这句话中提取出来的2-shingles是 “Mary had”, “had a”, “a little”, “little lamb”, “lamb its”, “its fleece”, “fleece was”, “was white”, “white as”, 以及 “as snow”。请注意，从文档中提取的k-shingles数不超过文档的长度，1-shingles仅仅是文档中的单词集。 设$S_1​$和$S_2​$是从两个文档$D_1​$和$D_2​$中提取的k-shingles。 然后，$D_1​$和$D_2​$之间基于shingle的相似度就是$S_1​$和$S_2​$之间的Jaccard系数

$$J(S_1,S_2)=\frac{\left|S_1\cap S_2\right|}{\left|S_1\cup S_2\right|}\tag{18.1}$$

通常，k的值介于5和10之间,取决于文集大小和应用程序域。 使用k-shingles而不是单个词（1-shingles）进行Jaccard系数计算的优点是，在不同文档中，shingles比单词重复的可能性要小。 对于大小为r的词典，有$<span><span class="MathJax_Preview">r^k</span><script type="math/tex">r^k$个shingles。 对于k≥5，在两份文件中重复出现的shingles的几率变得非常小。 因此，如果两个文件有许多共同的k-shingles，他们很可能是接近重复的。 为了节省空间，将单个shingles散列成用于比较目的的4字节（32位）数字。 这种表示还可以提高效率。

18.3 搜索引擎索引和查询处理

文档被抓取后，它们被用于查询处理。 搜索索引构建有两个主要阶段：

​ 1.*离线阶段：*这是搜索引擎预处理抓取的文档以提取令牌并构建索引以实现高效搜索的阶段。 此阶段还为每个页面计算基于质量的评分。

​ 2.在线查询处理：该预处理集合用于在线查询处理。访问相关文档，然后使用它们与查询的相关性及其质量进行排序。

Web文档处理的预处理步骤在13章关于挖掘文本数据有相关描述。相关的记号被提取和阻止。停止单词被删除。这些文档然后被转换为向量空间表示以进行索引。

在文档被转换为向量空间表示之后，在文档集合上构建倒排索引。第5章的5.3.1.2部分描述了倒序索引的构建。倒排列表将每个单词标识符映射到包含它的文档标识符列表。单词的频率也与倒排列表中的文档标识符一起存储。在许多实现中，文档中单词的位置信息也被存储。

除了将单词映射到文档的倒排索引之外，还需要索引来访问与查询词相关的倒排单词列表的存储位置。这些位置然后用于访问倒排列表。因此，*词汇索引*也是必需的。实际上，通常使用许多索引方法，例如哈希和尝试。通常，散列函数应用于查询词中的每个词，以产生相应的反转列表的逻辑地址。

对于一组给定的单词，访问所有相关的反向列表，并确定这些反向列表的交集。此交集用于确定包含全部或大部分搜索项的Web文档标识符。在仅对包含大多数搜索项的文档感兴趣的情况下，执行反转列表的不同子集以确定最佳匹配。通常，为了加速该过程，构建两个索引。仅在网页的标题上构建较小的索引，或者*指向页面*的页面的锚文本。如果在较小的索引中找到足够的文档，则不会引用较大的索引。否则，访问较大的索引。使用较小索引的逻辑是，网页的标题和指向它的网页的定位文本通常高度代表页面中的内容。

通常，为常见查询返回的页面数量可能为数百万或更多。显然，如此大量的查询结果对于用户来说并不容易被吸收。一个典型的浏览器界面只会在搜索结果的单个视图中向用户显示前几个（比如说10个）结果，并可以选择浏览其他不太相关的结果。因此，搜索引擎查询处理中最重要的问题之一就是排名问题。前述倒排索引的处理确实提供了基于内容的分数。这个分数可以用于排名。虽然商业引擎使用的确切评分方法是专有的，但已知影响基于内容的评分的因素有很多：

​ 1.单词被赋予不同的权重，具体取决于它是否出现在标题，正文，URL标记或指向网页的定位文本中。 标题中的术语出现或者指向该页面的网页的锚文本通常被赋予更高的权重。

​ 2.文档中关键字的出现次数将用于分数。 更大数量的事件显然更可取。

​ 3.字体大小和颜色的术语突出可用于评分。 例如，较大的字体大小将得到较大的分数。

​ 4.指定多个关键字时，也会使用它们在文档中的相对位置。 例如，如果两个关键字在Web页面中靠近在一起，则会增加分数。

然而，基于内容的分数还不够，因为它没有考虑页面的*声誉* 或*质量*。由于Web开发的不协调和开放性，使用这种机制非常重要。毕竟，Web允许任何人发布几乎任何东西，因此对结果的质量几乎没有控制。用户可能会发布不正确的材料，这可能是因为对该主题的了解不够，经济激励或故意恶意发布误导性信息的意图。

Web垃圾邮件的影响引发了另一个问题，即网站所有者有意为误导性内容提供更高级别的结果。商业网站所有者有重要的经济激励措施，以确保他们的网站排名更高。例如，高尔夫装备公司的业主将希望确保对*“高尔夫 ”*一词的搜索排名尽可能高。网站所有者使用几种策略将其结果排名更高。

​ 1.*内容垃圾邮件：*在这种情况下，即使这些关键字实际上对用户不可见，Web主机所有者仍会在托管网页中填充重复的关键字。 这是通过控制文本的颜色和页面的背景来实现的。 因此，这个想法是最大化网页与搜索引擎的内容相关性，而不会相应地增加可见的相关水平。 2.*伪装：*这是一种更复杂的方法，网站为抓取工具提供的内容不同于用户的内容。 因此，网站首先确定传入请求是来自搜寻器还是来自用户。 如果传入请求来自用户，则实际内容（例如广告内容）被提供。 如果请求来自抓取工具，则会提供与特定关键字最相关的内容。 结果，搜索引擎将使用不同的内容来响应来自Web用户将实际看到的用户搜索请求。

很明显，这种垃圾邮件会显着降低搜索结果的质量。搜索引擎也有很大的动机来提高他们的结果质量，以支持他们的付费广告模式，在搜索结果栏中显示*明确标记* 的赞助商链接是真正的付费广告。搜索引擎不希望广告（通过垃圾邮件伪装）作为查询的真实结果，特别是当这些结果降低用户体验质量时。这导致了搜索引擎和垃圾邮件制造者之间的敌对关系，其中前者使用基于信誉的算法来减少垃圾邮件的影响。在网站所有者的另一端，*搜索引擎优化（SEO）*行业试图通过使用搜索引擎使用的算法的知识优化搜索结果，无论是通过引擎使用的一般原则还是通过对搜索结果进行逆向工程。

对于给定的搜索，几乎总是有一小部分结果更具信息性或提供更准确的信息。如何确定这些页面？幸运的是，Web提供了几种自然的投票机制来确定页面的声誉。

​ 1.*页面引用机制：*这是用于确定网页质量的最常见机制。当一个页面质量很高时，许多其他网页指向它。引用可以在逻辑上被视为对网页的投票。虽然链接页面的数量可以用作质量的粗略指标，但它并不提供完整的视图，因为它没有考虑指向它的页面的质量。为了提供更全面的基于引文的投票，使用了称为*PageRank*的算法。

​ 2.*用户反馈或行为分析机制：*当用户从对搜索结果的响应中选择网页时，这是该网页与用户相关的明确证据。因此，可以返回其他类似页面或由其他类似用户访问的页面。由于用户识别机制有限，这种方法通常很难在搜索中实现。一些搜索引擎（如Excite）已经使用了各种形式的相关反馈。尽管搜索引擎较少使用这些机制，但它们对商业推荐系统来说非常重要。在商业推荐系统中，推荐是由网站在用户浏览期间而不是由搜索引擎自己做出的。这是因为商业网站具有更强大的用户识别机制（例如，用户注册）以启用用于推断用户兴趣的更强大的算法。

通常，信誉评分是使用类似PageRank的算法确定的。 因此，如果IRScore和RepScore分别是网页的基于内容和信誉的分数，则最终的排名分数是作为这些分数的函数计算的：

$$RankScore=f(IRScore,RepScore).\tag{18.2}$$

商业搜索引擎使用的确切函数$f(·，·)$是专有的，但它总是与IRScore和RepScore单调相关。各种其他因素，例如浏览器的地理位置，似乎也在排名中发挥作用。

应该指出，基于引用的信誉评分并不完全不受其他类型的垃圾邮件攻击的影响，这些垃圾邮件涉及协调创建大量网页链接。此外，在排名分数的内容部分中使用指向网页的定位文本有时会导致有趣的无关搜索结果。例如，几年前，谷歌搜索引擎搜索关键字“悲惨失败”，一位美国前任总统的官方传记作为其最重要的结果返回。这是因为许多Web页面是以协调的方式构建的，以便使用锚文本“悲惨失败”来指向这个传记。这种通过协调一个特定网站的链接建设来影响搜索结果的做法被称为Googlewashing。这种做法不太经常出于动机，但更常用于滑稽或讽刺的目的。因此，搜索引擎使用的排名算法并不完美，但多年来显着改善。用于计算基于信誉的排名分数的算法将在下一节中讨论。

18.4 排序算法

PageRank算法使用Web的链接结构进行基于信誉的排名。 PageRank方法与用户查询无关，因为它只预先计算公式18.2中得分的信誉部分。HITS算法是查询特定的。 它使用许多关于各种主题的权威来源如何在超链接环境中彼此链接的直觉。

18.4.1 PageRank算法

*PageRank*算法通过在Web中使用引用（或链接）结构来模拟网页的重要性。其基本思想是，信誉良好的文档更有可能被其他有信誉的网页引用（或链接）。

Web图上的随机冲浪模型被用来实现这个目标。考虑一个随机冲浪者通过选择页面上的随机链接访问Web上的随机页面。访问任何特定页面的长期相对频率显然受到链接页面数量的影响。此外，如果与其他经常访问的（或有信誉的）页面相关联，则任何页面的长期访问频率将更高。换句话说，PageRank*算法根据随机冲浪者的长期访问频率来模拟Web页面的声誉。这个长期频率也被称为*稳态概率。这个模型也被称为*随机行走模型*。

图18.2 用不同类型的死端进行PageRank计算的转换概率

基本的随机冲浪模型对于所有可能的图形拓扑都不适用。一个关键问题是一些网页可能没有外出链接，这可能导致随机冲浪者陷入特定节点。事实上，概率转换甚至没有在这样的节点上有意义的定义。这样的节点被称为*死端*。图18.2a展示了一个死端节点的例子。显然，死点是不可取的，因为无法在该节点定义PageRank计算的转换过程。为了解决这个问题，在随机冲浪模型中加入了两个修改。第一种修改是添加从死端节点（网页）到所有节点（网页）的链接，包括自身到自身的循环。每个这样的边缘具有1 / n的转移概率。这并不能完全解决问题，因为死角也可以在节点组上定义。在这些情况下，没有从一组节点到图中其余节点的传出链接。这被称为*死端组件*，或*吸收组件*。图18.2b显示了一个死端组件的例子。

死端组件在Web图中很常见，因为Web没有强连接。在这种情况下，可以有意义地定义单个节点处的转换，但是稳态转换仍将停留在这些死端组件中。所有稳态概率将集中在死端组件上，因为在发生转换后，无死端组件可能无法转换。因此，只要存在转换到死端组件的极小概率，所有稳态概率就会集中在这些组件中。从大型Web图表中*PageRank*计算的角度来看，这种情况是不可取的，其中，死端组件不一定是流行度的指标。此外，在这种情况下，各种死端组件中节点的最终概率分布不是唯一的，它取决于启动状态。通过观察从不同的死端组件开始的随机游动将其各自的稳态分布集中在相应的组件内，这很容易验证。

虽然边缘的添加解决了死端节点的问题，但需要额外的一步来解决更复杂的死端组件问题。 因此，除了增加这些边缘之外，在随机冲浪模型中使用*传送* 或*重启* 步骤。 这一步定义如下。 在每次转换时，随机冲浪者可以以概率α跳到任意页面，也可以以概率（1 - α）跟随页面上的其中一个链接。 α使用的典型值是0.1。 由于使用了远距传物，稳态概率变得独一无二，并且与起始状态无关。 α的值也可以被看作*平滑* 或*阻尼概率*。 较大的α值通常会导致不同页面的稳态概率变得更加均匀。 例如，如果选择α的值为1，那么所有页面将具有相同的稳态访问概率。

如何确定稳态概率？令$G=(N,A)$为有向Web图，其中节点对应于页面，边对应于超链接。节点的总数由n表示。假定A还包括从死端节点到所有其他节点的附加边。 i上的节点集合用$In(i)$表示，节点i的输出链路的端点集合用$Out(i)$表示。节点i处的稳态概率用$π(i)$表示。一般来说，网上冲浪者的转变可以被看作是一个马尔科夫链，其中一个n×n转移矩阵P被定义为一个具有n个节点的Web图。在马尔可夫链模型中，节点i的PageRank等于节点i的稳态概率$π(i)$。从节点i过渡到节点j的概率$p_{ij}$被定义为$1 / | Out（i）|$。转移概率的例子如图18.2所示。然而，这些转换概率并不涉及将在下面单独讨论的远距传物。

让我们检查一下给定节点i的转换。 节点i的稳态概率$π(i)$是一个传送到其中的概率和其中一个链接节点直接转换到其中的概率之和。 传送到节点的概率恰好是$α/ n$，因为传送以概率α发生在一个步骤中，并且所有节点同样有可能是传送的受益者。 转移到节点i的概率由$（1-α ) · \sum_{j∈In(i)}π（j）·p_{ji}$给出，作为来自不同链接节点的转换概率的总和。 因此，在稳定状态下，转移到节点i的概率由传送和转移事件的概率总和定义如下：

$$π(i)=α/ n+（1-α ) · \sum_{j∈In(i)} π（j）·p_{ji}\tag{18.3}$$

例如，图18.2a中节点2的等式可写为：

$$π(i2)=α/ 4+（1-α ) · (π(1) + π(2)/4 + π(3)/3 + π(4)/2)$$

每个节点将有一个这样的等式，因此用矩阵形式写出整个方程组是方便的。 令$\overline{π}=(π(1)...π(n))^T$为表示所有节点的稳态概率的$n$维列向量，设$e$为全部1个值的$n$维列向量。 方程组可以按如下矩阵形式重写：

$$\overline{π}=α\overline{e}/ n+(1-α)P^T\overline{π}\tag{18.4}$$

右边的第一项对应于一个传送，第二项对应于一个来自输入节点的直接转换。另外，由于向量$π$表示概率，所以其分量$\sum_{i=1}^nπ(i)$的和必须等于1：

$$\sum_{i=1}^nπ(i) =1\tag{18.5}$$

请注意，这是一个线性方程组，可以使用迭代方法轻松解决。 该算法通过初始化$\overline{π}^{(0)}= \overline{e} / n$开始，它通过重复以下迭代步骤从$\overline{π}^{(t)}$导出$\overline{π}(t + 1)$:

$\overline{π}(t + 1)\Leftarrowα\overline{e}/ n+(1-α)P^T\overline{π}^{(t)}\tag{18.6}$

在每次迭代之后，$\overline{π}(t + 1)$的条目通过将它们缩放到和为1来归一化。重复这些步骤直到$\overline{π}(t + 1)$和$\overline{π}(t)$之间的差值是幅度小于用户定义的阈值。这种方法也被称为*功率迭代法。*了解PageRank计算是非常重要的，并且在Web搜索期间无法为用户查询进行计算。 相反，所有已知网页的PageRank值都是预先计算并存储的。 只有当页面包含在特定查询的搜索结果中才能访问页面的存储*PageRank*值，以便在最终排序中使用，如公式18.2所示。

*PageRank*值可以表示为随机转移矩阵P的最大左特征向量4的n个分量（见习题5），该矩阵特征值为1。随机转移矩阵的最大特征值总是1。左特征向量 的$P$与$P^T$的右特征向量相同。 有趣的是，无向图的随机转移矩阵P的最大右特征向量可以用来构造频谱嵌入（参见第19章第19.3.4节），用于Web聚类。

18.4.1.1 主题性PageRank

主题性ageRank是*为那些希望在排序过程中比其他人更加重视某些话题的案例而设计的。虽然个性化在大型商业搜索引擎中较少见，但在小规模网站特定搜索应用程序中更为常见。通常情况下，用户可能对某些主题组合更感兴趣。 由于用户注册，这些兴趣的知识可能可用于个性化搜索引擎。 例如，特定用户可能对汽车的话题更感兴趣。 因此，当响应该用户的查询时，期望将与汽车相关的页面排在更高的位置。 这也可以被视为排序值的*个性化。这该怎么实现？

第一步是修复基本主题列表，并从这些主题中确定高质量的页面样本。 这可以通过使用诸如*开放目录项目（ODP）*等资源来实现，该资源可以为每个主题提供主题基础列表和示例网页。 *PageRank*方程式现在被修改，所以传送只能在这个样本的Web文档集上执行，而不是在Web文档的整个空间上执行。 让$\overline{e_p}$是一个n维个性化（列）向量，每个页面有一个条目。$\overline{e_p}$中的条目取值为1（如果该页面包含在样本集中），否则为0。 令$\overline{e_p}$中非零项的个数用$n_p$表示。 然后，PageRank公式18.4可以修改如下：

$$\overline{π}=α\overline{e}/ n_p+(1-α)P^T\overline{π}\tag{18.7}$$

相同的功率迭代方法可以用来解决个性化的*PageRank*问题。选择性的远距传送会对随机行走产生偏差，因此抽样页面的结构局部中的页面排序会更高。只要页面样本是Web图的不同（结构）地点的良好代表，其中存在特定主题的页面，则这种方法将运行良好。因此，对于每个不同的主题，可以预先计算并存储一个单独的*PageRank*向量，以便在查询期间使用。在某些情况下，用户对体育和汽车等主题的特定组合感兴趣。显然，可能的兴趣组合数量可能非常大，并且预先存储每个个性化的*PageRank*矢量并不合理可能或不必要。在这种情况下，只计算基本主题的*PageRank*向量。用户的最终结果被定义为主题特定的*PageRank*向量的加权线性组合，其中权重由用户在不同主题中指定的兴趣来定义。

18.4.1.2 SimRank算法

*SimRank*的概念被定义为计算节点之间的结构相似性。*SimRank*确定节点之间的对称相似性。 换句话说，节点$i$和$j$之间的相似度与$j$和$i$之间的相似度相同。在讨论*SimRank*之前，我们定义一个相关但略有不同的不对称排序问题：

给定一个目标节点$i_q$和来自图$G =（N，A）$的节点$S⊆N$的一个子集，按照它们与$i_q$的相似性顺序排列$S$中的节点。

这样的查询在推荐系统中非常有用，其中用户和项目以偏好的二分图的形式排列，其中节点对应于用户和项目，并且边缘对应于偏好。节点iq可以对应于项目节点，并且集合$S$可以对应于用户节点。或者，节点$i_q$可以对应于用户节点，并且集合$S$可以对应于项目节点。推荐系统将在18.5章节中讨论。 推荐系统与搜索密切相关，因为它们也执行目标对象的排名，但同时考虑到用户偏好。

这个问题可以看作是*主题性PageRank*的一个限制性案例，在这个案例中，对单节点$i_q$执行传送。因此，个性化*PageRank*公式18.7可以通过使用传送矢量$\overline{e_p} = \overline{e_q}$，即除了单个1之外的所有0的矢量直接适应，对应于节点$i_q$。此外，在这种情况下$n_p$的值被设置为1：

$$\overline{π}=α\overline{e}+(1-α)P^T\overline{π}\tag{18.8}$$

上述方程的解决方案将为$i_q$的结构局部性中的节点提供高排序值。 这种相似性的定义是不对称的，因为从查询节点i开始分配给节点j的相似性值不同于从查询节点j开始分配给节点i的相似性值。 这种非对称相似性度量适用于以查询为中心的应用程序，例如搜索引擎和推荐系统，但不一定适用于任意基于Web的数据挖掘应用程序。 在一些应用中，需要节点之间的对称配对相似性。 虽然可以将相反方向的两个话题敏感的*PageRank*值进行平均以创建对称度量，但*SimRank*方法提供了一个优雅而直观的解决方案。

*SimRank*的方法如下。 让$In（i）$表示$i$的in-linking节点。*SimRank*方程自然是以递归方式定义的，如下所示：

$$SimRank(i,j)=\frac{C}{|In(i)|·|In(j)|}\sum_{p\in(In(i))}\sum_{q\in(In(j))}SimRank(p,q).\tag{18.9}$$

这里$C$是（0,1）中的一个常量，可以看作是递归的一种衰减率。 作为边界条件，当$i = j$时，$SimRank（i，j）$的值被设置为1。 当$i$或$j$没有连接节点时，$SimRank（i，j）$的值被设置为0。为了计算*SimRank*，使用迭代方法。 如果$i = j$，则$SimRank（i，j）$的值被初始化为1，否则为0。 该算法随后使用方程式18.9迭代更新所有节点对之间的*SimRank*值，直到收敛。

*SimRank*的概念在随机行走方面有一个有趣的直观解释。 考虑两个随机冲浪者从节点$i$和节点$j$向后步进，直到他们相遇。 然后每个人采取的步数是一个随机变量$L（i，j）$。 然后，可以证明$SimRank（i，j）$等于$C^{L（i，j）}$的期望值。 衰减常数$C$用于映射长度为$l$的随机行走到相似度值$C^l$。 请注意，由于$C <1$，较小的距离将导致较高的相似性，反之亦然。

基于随机行走的方法通常比最短路径距离更具鲁棒性以测量节点之间的相似性。这是因为随机行走措施隐含地说明了节点之间的路径数量，而最短路径则没有。关于这个问题的详细讨论可以在第3章第3.5.1.2节找到。

18.4.2 HITS算法

超文本诱导主题搜索（HITS）算法是用于排序页面的查询相关算法。 这种方法背后的直觉在于理解组织为中心和权威的Web的典型结构。

图18.3 说明枢纽和权威

权威 是一个包含许多链接的页面。 通常，它包含关于特定主题的权威内容，因此，许多Web用户可能将该页面作为该主题的知识资源。 这将导致许多页面链接到权威页面。 中心是一个页面，有许多外部链接到当局。 这些代表了特定主题链接的汇编。 因此，中心页面为Web用户提供关于他们可以在哪里找到特定主题资源的指导。 图18.3a举例说明了Web图中的中心和权威的典型的以节点为中心的拓扑结构。

HITS*算法使用的主要观点是良好的中心指向许多良好的权威。相反，许多中心指出了良好的权威页面。图18.3b举例说明了中心和权威的典型组织。*HITS*算法利用这种相互加强的关系。对于用户发出的任何查询，HITS算法都从相关页面列表开始，并将其扩展为具有中心排名和*权威排名。

HITS*算法首先将搜索查询中的前$r$个最相关的结果收集起来。$r$的典型值是200。这定义了*根集R。通常，对商业搜索引擎或基于内容的评估的查询用于确定根集。对于$R$中的每个节点，该算法确定立即连接到$R$的所有节点（或者在链接中或者在外链接中）。这提供了更大的基本集$S$。因为基本集$S$可能相当大，将节点链接到$R$中的，添加到$S$的任何节点都被限制为$k$。使用的$k$的典型值大约为50.请注意，这仍然会导致基本集较大，因为每个可能的200个根节点可能会带来50个链接节点以及外部链接节点。

令$G =（S，A）$为（扩展的）基集$S$上定义的Web图的子图，其中$A$是根集$S$中的节点之间的边的集合。HITS*算法的整个分析限于这个子图。每个页面（节点）$i∈S$被分配了*中心评分$h（i）$和*权威评分*$a（i）$。假设中心和权威分数被归一化，以便中心分数的平方和和权威分数的平方和等于1。分数越高表示质量越好。中心和权威分数通过以下方式相互关联：

$$h(i)=\sum_{j:(i,j)\in A} a(j) , \forall i\in S\tag{18.10}$$

$$h(i)=\sum_{j:(i,j)\in A} h(j) , \forall i\in S\tag{18.11}$$

基本的想法是奖励中心指出良好的权威和奖励由好的中心指出的权威。很容易看出，上述的方程组加强了这种相互促进的关系。这是一个可以使用迭代方法求解的线性方程组。该算法首先初始化$<span><span class="MathJax_Preview">h^0（i）= a^0（i）= 1 /\sqrt{| S |}</span><script type="math/tex">h^0（i）= a^0（i）= 1 /\sqrt{| S |}$。 令$h^t（i）$和$a^t（i）$分别表示第$t$次迭代结束时第$i$个节点的中心和权威分数。 对于每个$t≥0$，算法在第$（t + 1）$次迭代中执行以下迭代步骤：

对于每个$i∈S$，$a^{t+1}（i）⇐\sum_{j:(j,i)∈A} h^t(j)$; 对于每个$i∈S$，$h^{t+1}（i）⇐\sum_{j:(j,i)∈A} a^{t+1}(j)$; 将每个中心和权威矢量的$L2$范数标准化为1;

对于中心矢量$\overline{h} = [h(1)...h(n)] ^T$和权威矢量，$\overline{a} = [a(1)...a(n)] ^T$，当边缘集合$A$被视为$|S|×|S|$的邻接矩阵时，更新可以分别表示为$\overline{a} = A^T\overline{h}$和$\overline{h} = A\overline{a}$。 迭代重复收敛。可以证明，中心矢量$\overline{h}$和权威矢量$\overline{a}$分别与$AA^T$和$A^TA$的主要特征向量成正比的方向收敛（见习题6）。这是因为相关的更新对可以分别等同于$AA^T$和$A^TA$的功率迭代更新。

18.5 推荐系统

自Web交易普及以来，收集有关用户购买行为的数据变得越来越容易。 这些数据包括关于用户个人资料，兴趣，浏览行为，购买行为以及各种项目评分的信息。 利用这些数据向顾客推荐可能的购买兴趣是很自然的。 在推荐问题中，用户选项对有与他们相关的效用值。如果有$n$个用户与$d$个项目，可以生成nXd的效用值构成的矩阵，这也被称作效用矩阵。用户项目对的效用值可以对应于用户对该项目的购买行为或评级。通常，效用值的一小部分以客户购买行为或评级的形式指定。 最好使用这些指定值来提出建议。 效用矩阵的性质对推荐算法的选择有重要影响：

1. 仅包含正面偏好：在这种情况下，指定的实用程序矩阵只包含正面偏好。 例如，社交网站上的“喜欢”选项的说明，在线网站上的项目浏览或购买指定数量的项目对应于积极偏好。 因此，效用矩阵是稀疏的，具有预先设定的一组正面偏好。 例如，效用矩阵可以包含由每个用户购买的物品的原始数量，数量的归一化数学函数或购买和浏览行为的加权函数。 这些功能通常由分析师以特定于应用程序的方式启发式指定。 对应于未被用户购买或浏览的项目的条目可能保持未指定。

2. 正面和负面偏好（评级）：在这种情况下，用户指定代表他们喜欢或不喜欢该项目的评分。 在分析中加入用户不喜欢是有意义的，因为它会使问题更复杂，并且经常需要对底层算法进行一些更改。

   图18.4 实用程序矩阵的例子

图18.4a举例说明了基于评级的效用矩阵，图18.4b举例说明了正偏好效用矩阵的一个例子。在这种情况下，有标记为$U_1$到$U_6$的六个用户和6部指定标题的电影。图18.4a中评分越高表示反馈越积极。 缺失的条目对应于两种情况下的未指定的偏好。这种差异显着改变了这两种情况下使用的算法。特别是，图18.4中的两个矩阵具有相同的指定条目，但它们提供了非常不同的见解。例如，用户$U_1$和$U_3$在图18.4a中有很大不同，因为它们对于它们的通用指定条目具有非常不同的评级。另一方面，这些用户在图18.4b中被认为是非常相似的，因为这些用户对相同的项目表示了肯定的偏好。基于评分的实用程序为用户提供了表达项目负面偏好的方法。例如，用户$U_1$不喜欢图18.4a中的电影《角斗士》。 没有任何机制可以在图18.4b的正面偏好效用矩阵中指定它，而不是在相对模糊的缺失条目之外。 换句话说，图18.4b中的矩阵表达性较差。 虽然图18.4b提供了一个二进制矩阵的例子，但非零输入可能是任意的正值。 例如，它们可以对应于不同用户购买的物品的数量。

这种差异会影响两种情况下使用的算法的类型。 考虑到积极和消极的偏好通常会使问题更加困难。 从数据收集的角度来看，当从顾客行为而不是评级推断时，也很难推断负面偏好。 建议也可以通过使用用户和项目表示中的内容来加强。

1. 基于内容的建议：在这种情况下，用户和项目都与基于特征的描述相关联。 例如，物品配置文件可以通过使用物品描述的文本来确定。 用户可能也在配置文件中明确指定了他们的兴趣。 或者，他们的个人资料可以从他们的购买或浏览行为中推断出来。
2. 协作过滤：顾名思义，协作过滤就是以“协作”的方式利用评级或购买行为的用户偏好，以造福所有用户。 具体而言，效用矩阵用于确定特定项目的相关用户或推荐过程中特定用户的相关项目。 这种方法的关键中间步骤是确定类似的项目和用户组。 这些同龄组中的模式提供了推荐过程中所需的协作知识。

这两种模式不是唯一的。 通常可以将基于内容的方法与协作过滤方法相结合以创建综合偏好分数。 协作过滤方法通常是更常用的模型之一，因此本节将对此进行更详细的讨论。

知道用于协同过滤算法的效用矩阵非常大且稀疏这一点是很重要的。$n×d$效用矩阵中$n$和$d$的值超过10的5次方并不罕见。矩阵也非常稀疏。例如，在电影数据集中，典型用户可能已经指定10个评级，超过了10的5次方个电影的范围。

在基本层面上，协作过滤可以被看作是缺失值估计或矩阵完成问题，其中指定了不完整的$n×d$效用矩阵，并且希望估计缺失值。 正如书目注释中所讨论的那样，传统统计学文献中关于缺失值估计存在许多方法。 然而，协作过滤问题在数据大小和稀疏性方面呈现出特别具有挑战性的特殊情况。

18.5.1 基于内容的建议

在基于内容的建议中，用户与描述他或她的兴趣的一组文档相关联。 多个文档可以与对应于他或她的指定人口统计资料的用户相关联，在注册时间的指定兴趣，购买物品的产品描述等等。 然后这些文档可以在向量空间表示中聚合成单个基于文本内容的用户简档。

这些项目还与文字说明相关联。 当项目的文字描述与用户配置文件相匹配时，可以将其视为相似性的指标。 当没有实用矩阵可用时，基于内容的推荐方法使用简单的k-邻域方法。 找到最接近用户文本配置文件的top-k项目。 可以使用与tf-idf的余弦相似性，如第13章所述。

另一方面，当有效矩阵可用时，为特定用户找到最相关的项目的问题可以被看作是传统的分类问题。 对于每个用户，我们有一组培训文档，代表该用户指定实用程序的项目描述。 标签代表效用值。 该用户的剩余项目的描述可以被视为分类的测试文档。 当实用程序矩阵包含数字评分时，类变量是数字。

在第11章的11.5节讨论的回归方法可以在这种情况下使用。logistic模型与有序的probit模型特别受欢迎。在实用程序矩阵中只有正面偏好（而不是评级）的情况下，所有指定的实用程序条目都对应于该项目的正面示例。 然后仅在剩余的测试文档上执行分类。 一个挑战是只有少数积极的训练例子被指定，而其余的例子没有标签。在这种情况下，可以使用仅使用正面和未标记方法的专门分类方法。 请参阅第11章的书目记录。基于内容的方法具有的优点是，它们甚至不需要实用程序矩阵并利用特定于域的内容信息。 另一方面，内容信息将推荐偏向于类似关键字所描述的项目与用户过去看到的项目。 协作过滤方法直接与效用矩阵一起工作，因此可以避免这种偏见。

18.5.2 基于邻域的协同过滤方法

基于邻域的方法的基本思想是使用用户-用户相似度或项目-项目相似度来根据评分矩阵进行推荐。

18.5.2.1 基于用户的评分相似度

在这种情况下，通过使用相似度函数来确定每个用户的前k类似用户。 因此，对于目标用户$i$，计算其与所有其他用户的相似度。 因此，需要在用户之间定义相似性功能。 在基于评级的矩阵的情况下，相似性计算是棘手的，因为不同的用户可能具有不同的评级尺度。 一个用户可能偏向喜欢大多数项目，另一个用户可能偏向于不喜欢大部分项目。 此外，不同的用户可能对不同的项目进行评分 捕获两个用户的评分向量之间的相似性的一个度量是皮尔逊相关系数。让$\overline{X}=(x_1...x_s)$和$\overline{Y}=(y_1...y_s)$表示一对用户之间的普通（特指）评级，它们的均值为$\hat{x}=\sum^s_{i=1}x_i/s$和$\hat{y}=\sum^s_{i=1}y_i/s$。或者，通过对所有指定的评分进行平均来计算用户的平均评分，而不是仅使用该对用户的共同评分项目。 这种计算均值的替代方法更为常见，并且可以显着影响成对Pearson计算。 然后，两个用户之间的Pearson相关系数定义如下： $<span><span class="MathJax_Preview">Pearson（\overline{X},\overline{Y}）=\frac{\sum^s_{i=1}(x_i-\hat{x})\cdot(y_i-\hat{y})}{\sqrt{\sum^s_{i=1}(x_i-\hat{x})^2}\cdot\sqrt{\sum^s_{i=1}(y_i-\hat{y})^2}}\tag{18.12}</span><script type="math/tex">Pearson（\overline{X},\overline{Y}）=\frac{\sum^s_{i=1}(x_i-\hat{x})\cdot(y_i-\hat{y})}{\sqrt{\sum^s_{i=1}(x_i-\hat{x})^2}\cdot\sqrt{\sum^s_{i=1}(y_i-\hat{y})^2}}\tag{18.12}$

皮尔逊系数是在目标用户和所有其他用户之间计算的。 目标用户的同伴组被定义为与具有最高Pearson相关系数的前$k$个用户。 具有非常低或负相关性的用户也会从对等组中删除。 此同级组的每个（指定）项目的平均评分均作为推荐评级返回。 为了获得更高的鲁棒性，还可以在计算平均值时使用其拥有者的Pearson相关系数对每个评级加权。 该加权平均评分可以为目标用户提供预测。 向用户推荐具有最高预测评级的项目。

这种方法的主要问题是不同的用户可能会提供不同规模的评级。 一个用户可以高度评价所有项目，而另一个用户可以负面评价所有项目。 因此，在确定对等组的（加权）平均评级之前，原始评分需要进行标准化。 用户的标准化评级通过从她的每个评级中减去她的平均评级来定义。 如前所述，对等组中项目的标准化评级的加权平均值被确定为标准化预测。 然后将目标用户的平均评分添加回归一化的评分预测以提供原始评分预测。

18.5.2.2 基于项目的评分相似度

与基于用户的方法相比，主要的概念区别在于，对等组是根据项目而不是用户构建的。 因此，需要在项目（或评级矩阵中的列）之间计算相似度。 在计算列之间的相似度之前，评分矩阵被标准化。 与基于用户的评级相同，评级矩阵中每行的平均值将从该行中减去。接着用一对项目的归一化评分$\overline{U}=(u_1...u_s)$和$\overline{V}=(v_1...v_s)$之间的余弦相似度来衡量它们之间的相似度： $<span><span class="MathJax_Preview">Co'si'ne（\overline{U},\overline{V}）=\frac{\sum^s_{i=1}u_i\cdot v_i}{\sqrt{\sum^s_{i=1}u_i^2}\cdot\sqrt{\sum^s_{i=1}v_i^2}}\tag{18.13}</span><script type="math/tex">Co'si'ne（\overline{U},\overline{V}）=\frac{\sum^s_{i=1}u_i\cdot v_i}{\sqrt{\sum^s_{i=1}u_i^2}\cdot\sqrt{\sum^s_{i=1}v_i^2}}\tag{18.13}$

这种相似性被称为调整后的余弦相似度，因为在计算相似度值之前，评分被归一化。

考虑需要确定用户$i$的项目$j$的评级的情况。 第一步是根据上述调整后的余弦相似度确定项目$j$中最相似的项目。 在项目$j$的前$k$个匹配项目中，确定了用户$i$指定了评分的项目。 这些（原始）评级的加权平均值报告为预测值。 这个平均中的项目$r$的权重等于项目$r$和目标项目$j$之间的调整余弦相似度。

基本的想法是在做出预测的最后一步中利用用户自己的评级。 例如，在电影推荐系统中，项目对等组通常将是类似流派的电影。 同一用户在此类电影上的以前的评分历史记录是该用户的兴趣的非常可靠的预测指标。

18.5.3 基于图形的方法

可以在用户项目图上使用随机游走而不是皮尔森相关系数来定义邻域。 对于稀疏评分矩阵，这种方法有时更有效。构造一个用户-项目两部分的图$G=（N_u\bigcup N_i,A）$,其中$N_u$是代表用户的节点集合，$N_i$是代表项目的节点集合。在实用程序矩阵中的每个非零条目的用户和项目之间的$A$中存在无向边。 例如，在图18.5中说明的图18.4中两个效用矩阵的用户-项目图。 可以使用个性化的PageRank或SimRank方法来确定给定用户的$k$个最相似的用户以进行基于用户的协作过滤。 同样，可以使用此方法确定与基于项目的协作过滤的给定项目最相似的$k$个项目。 基于用户的协作过滤和基于项目的协同过滤的其他步骤仍然相同。

图18.5 图18.4的效用矩阵的偏好图

更通用的方法是将问题视为用户项图上的正面和负面链接预测问题。 在这种情况下，用户项目图形的边缘会增加正负权重。 在减去用户平均值之后，用户对物品的标准化评级可被视为边缘上的正或负权重。 例如，考虑由图18.4（a）的等级矩阵构成的图。 用户$u_1$和项目角斗士之间的边缘会变成负边缘，因为$u_1$显然不喜欢电影《角斗士》。相应的Web将成为一个签名Web。 因此，推荐问题是预测签名Web中用户和项目之间的高正面权重边缘。 链接预测问题的一个简单版本只有正面链接在第19章19.5节讨论。有关链接预测方法的正面和负面链接，请参阅书目注释。 链接预测方法的优点在于它还可以利用社交Web链接连接的设置中不同用户之间的可用链接。 在这种情况下，用户项目图不再保持二分性。

当用户仅指定项目的正偏好值时，问题就变得简化了，因为大多数链接预测方法都是为正向链接而设计的。 也可以在用户项目图上使用随机散步来执行建议，而不是仅使用它来定义邻域。例如，在图18.4b的情况下，图18.5的相同用户 - 项目图可以与随机游走方法结合使用。 这个偏好图可以用来提供不同类型的建议：

1. 用户$i$的排名最高的项目可以通过在节点i重新开始随机漫步返回具有最大PageRank的项目节点来确定。
2. 项$j$的排名最高的用户可以通过以随机游走的方式返回带有最大PageRank的用户节点并在节点$j$重新启动来确定。

重新启动概率的选择调节了推荐项目/用户的全球受欢迎程度与推荐对特定用户/项目的特异性之间的权衡。 例如，考虑需要向用户$i$推荐项目的情况。 低的传送概率将有利于许多用户青睐的流行项目的推荐。 增加远程传送概率将使得建议对于用户$i$更特定。

18.5.4 聚类方法

基于邻域的方法的一个弱点是需要执行的计算规模。 对于每个用户，通常必须执行至少与矩阵中非零项数量成正比的计算。 此外，这些计算需要在所有用户上执行，以向不同的用户提供推荐。这可能非常慢， 因此出现了一个关于是否可以使用聚类方法来加速计算的问题。 集群还有助于在一定程度上解决数据稀疏问题。

除了将聚类作为定义对等组的预处理步骤执行之外，聚类方法与基于邻域的方法完全类似。 这些同龄组然后被用于提出建议。 可以在用户或项目上定义群集。 因此，它们可以用于制定用户 - 用户相似性建议或项目 - 项目相似性建议。 为简洁起见，这里仅描述用户用户推荐方法，尽管项目推荐方法完全类似。 聚类方法的工作原理如下：

1. 使用任何聚类算法将所有用户聚类为$n_g$个用户组。
2. 对于任何用户$i$，计算群集中指定项目的平均（标准化）评级。 转换回原始值后,为用户$i$报告这些评分。

项目-项目推荐方法是类似的，除了集群应用于列而不是行。 这些群集定义了类似项目的组（或隐式伪类型）。 计算用户-项目组合的评分的最后一步与基于邻域的方法相似。 在执行聚类后，确定所有评级通常非常有效。 还有待解释如何执行群集。

18.5.4.1 自适应K均值聚类

为了对评价矩阵进行聚类，可以对第6章讨论的许多聚类方法进行调整。 但是，将这些方法适用于稀疏指定的不完整数据集很重要。 诸如k均值和期望最大化之类的方法可以用于归一化评分矩阵。 在k-means方法的情况下，与第6章的描述有两个主要区别：

1. 在k-means的迭代中，通过对每个维度对集群成员中指定值的数量进行平均来计算质心。 此外，质心本身可能未完全指定。
2. 数据点与质心之间的距离仅在两者中的指定维度上计算。 此外，距离除以这些维度的数量以公平地比较不同的数据点。

评分矩阵在应用聚类方法之前应进行归一化处理。

18.5.4.2 自适应共聚类

共聚类方法在第13章的13.3.3.1节中描述。共聚类非常适合于在稀疏矩阵中发现用户和项目的邻域集合。指定的条目被视为1，未指定的条目被视为0以进行协同聚类。 图18.6a举例说明了应用于图18.4b的效用矩阵的协同聚类方法的一个例子。 在这种情况下，为了简单起见，仅示出了双向联合聚类。 联合聚类方法将用户和项目清晰地分为彼此清晰的对应关系。因此，同时发现用户邻域和项目邻域。 在定义了邻域之后，可以使用上述基于用户的方法和基于项目的方法来预测缺失的项目。

图18.6 用户项目图形的联合聚类

共聚类方法在用户-项目图上也有很好的解释。让$G=（N_u\bigcup N_i,A）​$表示偏好图,其中$N_u​$是代表用户的节点集合，$N_i​$是代表项目的节点集合。对于实用程序矩阵的每个非零项，A中存在无向边。 然后共簇是这个图结构的聚类。 相应的双向图分区如图18.6b所示。 由于用户-项目图形的这种解释，该方法能够同时利用项目项目和用户-用户相似性。 协同聚类方法也与潜在因子模型密切相关，如非负矩阵因子分解，它们可以通过使用潜在因子同时对行和列进行聚类。

18.5.5 潜在因子模型

前一节讨论的聚类方法使用数据的聚合属性来进行可靠的预测。这可以通过潜在因子模型以更强大的方式实现。这种方法既可用于评分矩阵，也可用于正偏好效用矩阵。潜伏因素模型近年来越来越受欢迎。潜在因子模型背后的关键思想是许多降维和矩阵分解方法以低维矢量或潜在因子的形式总结了行和列之间的相关性。此外，协作过滤本质上是一个缺失的数据估算问题，其中这些相关性用于进行预测。因此，这些潜在因素成为隐藏变量，它们以简明的方式对数据矩阵中的相关性进行编码，并可用于进行预测。当k的值远小于$d$时，即使从不完全指定的数据中也可以对k维主导潜在因子进行稳健估计。这是因为只要指定条目的数量足够大，就可以用稀疏指定的数据矩阵准确地估计更简洁明确的潜在因子。

这$n$个用户用$n$个相应的$k$维因子代表，表示为矢量$\overline{U_1}$...$\overline{U_n}$。$d$项由$d$个对应的$k$维因子代表，表示为矢量$\overline{I_1}$...$\overline{I_d}$。$k$的值表示潜在表示的简化维数。 然后，用户$i$和项目$j$的评级$r_{ij}$由相应潜在因子的矢量点乘积估算：$<span><span class="MathJax_Preview">r_{ij}\approx\overline{U_i}\cdot \overline{I_j}\tag{18.14}</span><script type="math/tex">r_{ij}\approx\overline{U_i}\cdot \overline{I_j}\tag{18.14}$

如果这种关系对于评分矩阵的每一项都是正确的，那么它意味着整个评分矩阵$D = [r_{ij}]_{n×d}$可以被分解成两个矩阵，如下所示：

$$D\approx F_{user}F_{item}^T\tag{18.15}$$

这里$F_{user}$是一个$n×k$矩阵，其中第$i$行表示用户$i$的潜在因子$\overline{U_i}$。同样，$F_{item}$是一个$d×k$矩阵，其中第$j$行表示项目$j$的潜在因子$\overline{I_j}$。这些因素如何确定？ 用于计算这些因素的两个关键方法是奇异值分解和矩阵分解，这将在下面的部分中讨论。

18.5.5.1 奇异值分解

奇异值分解（SVD）在第2章第2.4.3.2节中详细讨论。建议读者在继续阅读之前重新学习该部分。第2章的公式2.12近似将数据矩阵$D$分解为三个矩阵，如下：

$$D\approx Q_K\Sigma_kP_k^T \tag{18.16}$$

这里，$Q_k$是n×k矩阵，$\Sigma_k$是$k×k$对角矩阵，并且$P_k$是$d×k$矩阵。 与2路分解格式的主要区别在于对角矩阵$\Sigma_k$。但是，这个矩阵可以包含在用户因素中。 因此，可以得到以下因子矩阵：

$$F_user=Q_k\Sigma_k \tag{18.17}$$

$$F_item=P_k \tag{18.18}$$

第2章的讨论表明，矩阵$Q_k\Sigma_k$定义了SVD中数据点的简化和变换坐标。 因此，每个用户在由项目的线性组合定义的新的k维基础系统$P_k$中具有新的一组k维坐标。 严格地说，对于不完全矩阵，SVD是未定义的，尽管启发式近似是可能实现的。 书目注释提供了旨在解决这个问题的方法的指针。 SVD的另一个缺点是计算复杂度高。 对于非负评级矩阵，可以使用PLSA，因为它提供了与SVD相似的概率分解。

18.5.5.2 矩阵分解

SVD是一种矩阵分解形式。 由于矩阵分解有许多不同的形式，因此探讨它们是否可以用于推荐是必要的。 建议读者阅读第6章第6.8节，了解矩阵分解。部分公式如下： $<span><span class="MathJax_Preview">D\approx U\cdot V^T \tag{18.19}</span><script type="math/tex">D\approx U\cdot V^T \tag{18.19}$

这种分解已经直接以我们想要的形式出现。 因此，用户和项目因子矩阵定义如下： $<span><span class="MathJax_Preview">F_user=U \tag{18.20}</span><script type="math/tex">F_user=U \tag{18.20}$

$$F_item=V \tag{18.21}$$

这与6.8节分析的主要区别在于如何为不完全矩阵设置优化目标函数。 矩阵$U$和$V$是通过优化以下目标函数来确定的：

$$J=||D-U\cdot V^T||^2 \tag{28.22}$$

在这里，||·|| 代表Frobenius标准。 在这种情况下，因为评分矩阵$D$只是部分指定的，所以只对指定的条目进行优化，而不是对所有条目进行优化。 因此，优化问题的基本形式仍然非常相似，并且使用任何现成的优化求解器可以很容易地确定$U$和$V$.书目注释包含指向相关随机梯度下降方法的注解。 包含U和V的平方Frobenius范数的正则化项$\lambda(||U||^2+||V||^2)$可以被添加到J以减少过拟合。 当指定条目的数量很小时，正则化项尤为重要。 参数λ的值是使用交叉验证确定的。

这种方法比用SVD确定分解矩阵更方便，因为无论多么稀疏，优化目标都可以以无缝方式为一个不完全指定的矩阵设置。 当评级是非负的时候，也可以使用非负形式的矩阵分解。如第6.8节所述，矩阵分解的非负性提供了许多解释优势。 它还可以使用其他形式的因子分解，例如概率矩阵分解和最大余量矩阵分解。 这些变体中的大多数在目标函数（例如Frobenius范数最小化或最大似然最大化）和底层优化问题的约束（例如非负性）方面的微小变化方面是不同的。 这些差异常常转化为相同随机梯度下降方法的变体。

18.6 Web使用挖掘

Web的使用导致大量的日志数据。 通常收集两种主要类型的日志：

1. Web服务器日志：这些日志对应于Web服务器上的用户活动。 通常，日志以标准格式存储，称为NCSA通用日志格式，以方便不同程序的使用和分析。 这种格式的一些变体（如NCSA组合日志格式和扩展日志格式）存储了一些额外字段。 尽管如此，基本格式的变体数量相对较少。 Web日志条目的示例如下所示： 98.206.207.157 - - [31/Jul/2013:18:09:38 -0700] "GET /productA.pdf HTTP/1.1" 200 328177 "-" "Mozilla/5.0 (Mac OS X) AppleWebKit/536.26 (KHTML, like Gecko) Version/6.0 Mobile/10B329 Safari/8536.25" "retailer.net"
2. 查询日志：这些对应于用户在搜索引擎中提出的查询。 除了商业搜索引擎提供商之外，如果网站包含搜索功能，则这些日志也可用于网站所有者。

这些类型的日志可以用于各种应用程序。 例如，可以提取用户的浏览行为以提出建议。 Web使用率挖掘的范围太大，不能被单个章节的章节所覆盖。 因此，本节的目标是概述如何将本书中讨论的各种技术映射到Web使用挖掘。 书目注释包含有关此主题的更详细的Web挖掘书籍的指针。 Web日志应用程序的一个主要问题是日志包含的数据不能在不同用户之间完全分离，因此难以直接在任意应用程序设置中使用。 换句话说，重要的预处理是必需的。

18.6.1 数据的预处理

日志文件通常可用作与用户访问相对应的连续条目序列。 不同用户的条目通常是相互交错的，而且很难区分同一用户的不同会话。

通常，客户端Cookie用于区分不同的用户会话。 但是，由于客户端的隐私问题，客户端cookie往往被禁用。 在这种情况下，只有IP地址可用。 仅基于IP地址很难区分不同的用户。 其他领域，如用户代理和推荐人，通常用于进一步区分。 在许多情况下，至少有一部分用户可以被识别为合理的粒度级别。 因此，只能使用可识别用户的日志子集。 对于特定于应用程序的场景，这通常是足够的 书目注释包含指向Web日志预处理方法的指针。

预处理导致页面浏览形式的一组序列，这些也被称为点击流。 在某些情况下，还会构建遍历模式图，因为它涉及网站页面的链接结构。 对于查询日志，以搜索令牌的形式获得相似的序列，而不是页面视图。 因此，尽管应用场景有所不同，但收集到的数据的性质也有一些相似之处。 下面将简要介绍Web日志挖掘的一些关键应用。

18.6.2 应用

点击流数据会导致大量的序列数据挖掘应用。 在下文中，将提供各种应用程序的简要概述以及相关章节的具体位置。 书目注释还包含更多具体的指引。

建议

用户可以根据浏览模式推荐网页。 在这种情况下，甚至不需要使用序列信息; 相反，可以从先前的浏览行为构建用户浏览量矩阵。 这可以用来推断用户对不同页面的兴趣。 相应的矩阵通常是正偏好效用矩阵。 本章中的任何推荐算法都可以用来推断用户最有可能感兴趣的页面。

频繁遍历模式

站点中的频繁遍历模式提供了站点中用户遍历的最可能模式的概述。 15章的频繁序列挖掘算法以及17章的频繁图模式挖掘算法可用于确定最受欢迎的路径。 网站所有者可以使用这些结果进行网站重组。 例如，非常受欢迎的路径应该保持为网站图形中的连续路径。 如果需要，很少使用的路径和链接可能会重新组织。 如果在该对之间经常观察到顺序模式，则可以在页面对之间添加链接。

预测与异常检测

第15章中的马尔可夫模型可用于预测用户的未来点击。 这些点击与期望值的显着偏差可能对应于异常情况。 当整个访问模式不寻常时，会发生第二种异常。 这些类型的情景与案例中的情况不同，其中序列中的特定页面视图被认为是异常的。 隐马尔可夫模型可以用来发现这样的异常序列。 读者可以参考第15章对这些方法的讨论。

分类

在某些情况下，来自Web日志的序列可能会根据期望的或不需要的活动进行标记。 一个理想的活动的例子是当用户在一个网站浏览特定页面序列后购买某个产品时。 不合需要的序列可能指示入侵攻击。 标签可用时，可能会对Web日志序列进行早期分类。 结果可用于对Web用户的未来行为进行在线推断。

18.7 总结

Web数据有两种类型。 第一种类型的数据对应于Web上可用的文档和链接。 第二种类型的数据对应于用户行为的模式，例如购买行为，评级和Web日志。 这些类型的数据都可以用于不同的见解。

从Web收集文档数据通常是一项艰巨的任务，通常通过使用信息收集器来实现。 收集器可以是商业搜索引擎使用的通用收集器，也可以是优先收集器，只收集特定主题的主题。 收集文件后，它们被存储并在搜索引擎中编入索引。 搜索引擎使用文本相似度和基于声誉的排名组合来创建最终得分。 用于在搜索引擎中排名的两种最常用的算法是PageRank和HITS算法。 主题敏感的PageRank通常用于计算节点之间的相似度。

大量的数据在Web上收集，对应于用户项目偏好。 这些数据可用于提出建议。 推荐方法可以是基于内容的或基于用户偏好的。 基于偏好的方法包括基于邻域的技术，聚类技术，基于图的技术和基于潜在因子的技术。

Web日志是Web上另一个重要的数据源。 Web日志通常会导致序列数据或遍历模式的图形。 如果数据的顺序部分被忽略，那么日志也可以用于建议。 Web日志分析的典型应用包括确定频繁的遍历模式和异常情况，以及确定感兴趣的事件。

18.8 书目注释

Web挖掘的两个优秀资源是[127,357]中的书籍。 Google搜索引擎的创始人提供了从搜索到搜索阶段的Web搜索引擎的早期描述[114]。 收集器的一般原则可以在[127]中找到。 在优先收集器方面也有重要的工作[127,357]。 搜索引擎索引和查询的许多方面在[377]中描述。

PageRank算法在[114,412]中描述。 HITS算法在[317]中有描述。 PageRank和HITS算法的不同变化的详细描述可以在[127,343,357,377]中找到。 主题敏感的PageRank算法在[258]中描述，而SimRank算法在[289]中描述。

推荐系统在Web和数据挖掘书籍中有很好的描述[343,357]。 此外，有关该主题的一般背景可在期刊调查文章和特刊中找到[2,325]。 协同过滤的问题可以被认为是缺失数据估算问题的一个版本。 关于缺失数据分析存在大量文献[364]。 基于项目的协作过滤算法在[170,445]中讨论。 在[210,277,528]中讨论了基于图形的建议方法。 在[341]中讨论了在签名Web中进行链接预测的方法。潜在因素模型的起源通常归功于Netflix奖项竞赛中许多成功的参赛作品[558]。 然而，在推荐分析领域和Netflix奖项竞赛领域的工作之前，使用潜在因素模型来估计缺失的项目[23]。 这项工作[23]展示了如何通过将SVD与EM算法相结合来逼近缺失的数据条目。 此外，早于Netflix奖竞赛进行的[272,288,548]中的作品展示了如何将不同形式的矩阵分解用于推荐。在Netflix大奖赛推广这种方法之后，还提出了其他基于因子分解的方法用于协同过滤[321,322,323]。 相关的矩阵分解模型可以在[288,440,456]中找到。 潜在语义模型可以被看作是潜在因素模型的概率版本，并在[272]中进行了讨论。

Web使用挖掘已在[357]中得到很好的描述。 在这项工作中描述了Web日志挖掘和使用挖掘。 Web日志准备方法的描述可以在[161,473]中找到。 Web日志异常检测的方法在[5]中讨论。 Web使用情况挖掘调查显示在[65,390,425]。

18.9 习题

1. 使用宽度优先算法实现通用收集程序。
2. 考虑字符串ababcdef。 将每个字母作为标记，列出所有2层集合和3层集合。
3. 讨论为什么将锚文本添加到为了挖掘目的而指向的网页是好的，和为什么它出现的页面通常会产生误导。
4. 对“挖掘文本数据”和“文本数据挖掘”执行Google搜索。您是否获得相同的前10个搜索结果？ 这是什么告诉你有关搜索引擎使用的排名启发式的内容组件？
5. 证明传输的PageRank计算是一个适当构造的概率转换矩阵的特征向量计算。
6. 证明HITS的枢纽和权威分数可以通过$AA^T$和$A^TA$上的主导特征向量计算分别计算。 这里，$A$是图$G =（S，A）$的邻接矩阵，如本章定义。
7. 证明随机转移矩阵的最大特征值总是1。
8. 假设您被告知特定的转换矩阵$P$可以被对角化为$P = VΛV ^{-1}$，其中$Λ$是对角的。 你如何使用这个结果来有效地确定k跳转换矩阵，该转移矩阵定义了$k$跳中每对节点之间转换的概率？ 当$k =∞$时，你会为特殊情况做些什么？ 如果我们允许$P$和$V$的输入是复数，结果是否成立？
9. 将PageRank算法应用于图18.2b的图形，分别使用0.1,0.2和0.4的远距传送概率。 对增加隐形传送概率的死胡同组分（概率）有什么影响？
10. 重复前面的练习，除了重启是从节点1执行的。稳态概率如何通过增加远距传送概率而受到影响？
11. 证明图18.4.1b的图的转移矩阵将具有多于一个特征值为1的特征向量。为什么在这种情况下具有单位特征值的特征向量不唯一？
12. 在评分矩阵上实施基于邻域的协作过滤方法。
13. 实施个性化的PageRank方法，用于正偏向效用矩阵上的协同过滤。
14. 通过将重启概率分别设置为0.1,0.2和0.4，将PageRank算法应用于图18.5的示例。
15. 通过在节点《角斗士》处重新启动，并且重启概率分别为0.1,0.2和0.4，将个性化的PageRank算法应用于图18.5的示例。 这告诉你关于电影《角斗士》的最相关用户的是什么这告诉你关于电影《角斗士》的最相关用户谁还没有看过这部电影？ 最相关的用户是否有可能用远距传送概率进行更改？ 从特定应用的角度来看，传感概率的直观意义是什么？
16. 为不完全矩阵构造矩阵分解问题的优化公式。
17. 在图18.5的二分图中，用户节点和项目节点之间的SimRank值是多少？ 有鉴于此，请解释SimRank模型的弱点。