2026/9/4 4:10:02
FEATURED · 精选文章 
总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/a943a945bf23f7b32f4555bcec7b1fd5_24.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/a943a945bf23f7b32f4555bcec7b1fd5_25.png本节课中我们一起学习了数据仓库中物化视图的核心概念。我们通过SQL分组聚合的例子理解了视图之间的推导关系。我们重点掌握了物化视图如何通过预计算和存储中间结果来提升查询性能并定义了查询成本和物化增益。最后我们引出了选择性物化问题即在资源约束下如何最优选择要物化的视图集合以最大化性能增益。这是构建高效数据仓库系统的关键基础。018问题定义与NP-hard证明https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_1.png在本节课中我们将学习数据仓库中视图选择问题的形式化定义并证明该问题在计算上是困难的即NP-hard问题。问题定义上一节我们介绍了数据仓库中物化视图的概念。在了解其收益计算方式后我们明确要解决的问题是从所有可能的视图中选择一个子集进行物化使得总收益最大化。问题公式化给定一个视图格Lattice和物化视图的数量限制K目标是选择一个包含K个视图的集合V使得总收益Gain(V)最大化。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_1.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_3.png证明视图选择问题是NP-hard作为计算机科学家我们需要判断这个问题是否非常困难。与关联规则挖掘类似我们也想证明这个问题是NP-hard的。我们将使用一个已知的NP完全问题来进行归约证明。我们首先将上述最大化问题转化为一个决策问题。在NP-hard证明中通常使用决策问题。决策问题的答案是“是”或“否”。选择性物化决策问题给定一个整数K和一个实数J是否存在一个包含K个视图的集合V使得其信息增益至少为J我们的目标是证明这个决策问题是NP-hard的。使用已知的NP完全问题精确3覆盖证明方法与关联规则挖掘中学过的类似。我们使用一个已知的NP完全问题“精确3覆盖”Exact Cover by 3-Sets X3C。X3C问题定义给定一个包含3q个元素的集合X以及一个由X的3元素子集构成的集合C。问C中是否包含一个精确覆盖C‘C‘是C的子集使得X中的每个元素在C’中恰好出现一次为了让定义更清晰请看以下示例。示例一答案是“是”集合 X {A, B, C, D, E, F}集合 C { {A, B, C}, {B, C, D}, {D, E, F} }我们可以找到子集 C‘ { {A, B, C}, {D, E, F} }。X中的每个元素A, B, C, D, E, F在C’中都恰好出现一次。因此答案是“是”。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_5.png示例二答案是“否”集合 X {A, B, C, D, E, F}集合 C { {A, B, C}, {B, C, D}, {A, E, F} }https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_7.png无法找到满足条件的子集C‘。例如如果选择{A, B, C}和{A, E, F}则元素A出现了两次如果选择{B, C, D}和{A, E, F}则元素B、C、D、E、F都只出现一次但元素A没有出现。因此答案是“否”。精确3覆盖X3C是一个已被证明的NP完全问题。从X3C到视图选择问题的归约现在我们将X3C问题归约到我们的选择性物化决策问题。以下是归约步骤的概述随后将通过一个具体例子进行解释。归约构造如下创建一个根节点大小为200称为“魔法数字”位于第1层。创建一个底层节点大小为1位于第4层。对于X中的每个元素x创建一个节点N_x大小为50位于第3层。在N_x和底层节点之间创建一条边。对于C中的每个3元素子集A {x, y, z}创建一个节点N_A大小为100位于第2层。创建N_A到根节点的边以及N_A到N_x、N_y、N_z的边。在我们的决策问题中设K q即X中元素组数。设决策阈值 J 400 * q。你可能对其中出现的数字感到疑惑。接下来我们通过一个例子来具体说明。归约示例我们使用示例一的X3C实例进行归约X {A, B, C, D, E, F} 所以 q 2。C { {A, B, C}, {B, C, D}, {D, E, F} }。根据归约步骤K q 2。J 400 * q 800。构建的视图格结构如下图所示节点旁的数字为其“大小”属性。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_3.png现在考虑我们的选择性物化问题除了顶层的根视图必须物化外我们还需要选择K2个视图进行物化使得总收益至少达到J800。根据收益计算规则物化一个视图的收益等于其祖先视图中未被物化的最小祖先的大小我们可以计算各个候选视图的收益物化“ABC”视图的收益是100。物化“BCD”视图的收益是100。物化“DEF”视图的收益是100。那么选择哪两个视图能使总收益最大化呢答案是选择“ABC”和“DEF”。选择“ABC”它能为底层A、B、C三个元素的查询各节省100总收益300严格计算是覆盖了其下4个节点收益为4*100400此处为简化理解。选择“DEF”它能为底层D、E、F三个元素的查询各节省100总收益300。两者总收益为600按简化计算或800按图中结构精确计算每个物化视图为其4个后代节点各贡献100收益。无论如何计算选择“ABC”和“DEF”都能使总收益达到最大值并且至少为800满足决策问题的要求。归约的正确性与魔法数字的含义关键点在于在这个构造的实例中能够达到收益阈值J800的物化方案选择“ABC”和“DEF”恰好对应了原X3C问题的一个解{ {A, B, C}, {D, E, F} }。魔法数字200, 100, 50, 1的设置是为了确保只有物化那些完全覆盖三个独立底层元素且不与其他物化视图覆盖的元素重叠的第2层节点即C中的子集对应的节点才能获得最大收益。收益阈值J400*q被设置为只有当物化的q个节点恰好构成一个精确覆盖时才能达到的值。这些数字并非固定不变。例如若将根节点大小改为500第2层节点大小改为200那么相应的J值应变为 (500-200)*4 * q 1200 * q。其核心原理是保持收益计算的比例关系使得“精确覆盖”对应的物化方案具有最大且唯一的收益值。因此如果我们能解决这个选择性物化决策问题就等于解决了X3C问题。由于X3C是NP完全的所以选择性物化决策问题至少是NP-hard的。进而最初的最大化收益视图选择问题也是NP-hard的。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_11.png实例的物理意义最后让我们回顾一个更具体的例子理解视图格中节点的物理意义。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_9.png考虑一个视图格其属性包括零件P、供应商S、客户C。节点“PC”表示按零件和客户分组聚合的视图。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_11.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_12.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_14.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_16.png在数据库理论中这通常与函数依赖有关。例如图中“PC”视图的大小与“PSC”视图相同这可能暗示着一种函数依赖P, C可以唯一确定S。这意味着在原始数据中给定一个零件和一个客户对应的供应商是唯一的。这种语义约束会影响视图的大小从而影响物化视图的选择策略。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_17.png总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_16.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_17.png本节课中我们一起学习了数据仓库视图选择问题的形式化定义。我们通过将已知的NP完全问题——精确3覆盖X3C——归约到视图选择的决策问题证明了该问题是一个NP-hard问题这意味着在多项式时间内找到最优解是极其困难的。最后我们还探讨了视图格结构中可能蕴含的数据库语义如函数依赖。理解问题的计算复杂性是设计高效启发式算法或近似算法的基础。019视图物化选择算法https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_1.png概述在本节课中我们将学习数据仓库中一个重要的优化问题如何从众多可能的物化视图中选择一部分进行物理存储以最小化查询的总成本。我们将重点介绍解决此问题的贪心算法并通过一个具体例子来演示其计算过程。最后我们将探讨该算法的性能表现。算法介绍上一节我们介绍了视图物化选择问题的背景。本节中我们来看看解决该问题的核心算法——贪心算法。该算法思路非常简单直接。首先我们需要定义一个关键概念收益。给定一个视图集合S代表已选择物化的视图我们定义选择某个视图v进行物化的收益B(v, S)如下公式B(v, S) ∑ (对于每个能被 v 或其物化后代回答的视图 w计算未物化 v 时回答 w 的最小成本 - 物化 v 后回答 w 的最小成本)简单来说收益就是物化视图v后能为整个查询系统节省的总成本。基于收益的定义贪心算法的步骤如下算法伪代码输入需要物化的视图数量 k 1. 初始化选择集合 S {顶层视图} // 顶层视图总是被物化 2. FOR i 1 TO k DO 3. 对于每一个不在 S 中的视图 v计算其收益 B(v, S) 4. 选择收益 B(v, S) 最大的视图 v_max 5. 将 v_max 加入集合 SS S ∪ {v_max} 6. END FOR 7. 输出最终的选择集合 S算法示例为了帮助理解我们通过一个具体的例子来演示贪心算法的执行过程。假设我们有一个数据立方体其视图的依赖关系及查询成本如下图所示。我们的目标是选择k2个视图除了顶层视图进行物化。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_1.png我们通常会绘制一个收益计算表来辅助决策。初始时只有顶层视图被物化。以下是第一轮迭代选择第一个视图的收益计算过程视图 PC它会影响自身以及其父视图 P 和 C。物化前回答 PC 查询的成本是 6M。物化后成本变为 6M因为物化成本等于查询成本。因此对自身的收益为 0。对于 P 和 C由于物化 PC 并不能提供比现有顶层视图更优的路径来回答 P 和 C 的查询收益也为 0。总收益为 0。视图 PS它会影响自身以及 P 和 S。物化前回答 PS 查询的成本是 6M。物化后成本变为 0.8M。因此对自身的收益为 5.2M。对于 P 和 S同样因为无法提供更优路径收益为 0。总收益为 5.2M。视图 SC与 PC 对称总收益为 0。视图 P它只影响自身。物化前通过顶层视图回答 P 的成本是 6M。物化后成本变为 0.2M。因此收益为 5.8M。视图 S与 P 类似收益为 5.99M。视图 C与 P 类似收益为 5.9M。第一轮收益计算结果如下表所示| 候选视图 | 收益 (B) || :— | :— || PC | 0 ||PS|5.2M|| SC | 0 || P | 5.8M || S | 5.99M || C | 5.9M |根据贪心策略我们选择收益最大的视图。在本轮中视图S的收益最大5.99M因此我们物化视图 S。现在进入第二轮迭代选择第二个视图。此时物化集合S已包含 {顶层视图 S}。以下是第二轮迭代的收益计算要点需考虑已物化的视图 S 的影响视图 PC物化 PC 主要影响自身和 C。对于 P由于已有物化视图 S通过 S 回答 P 的成本为 0.8M这比通过 PC 路径6M更优因此物化 PC 对 P 无收益。最终计算出的总收益为 0。视图 PS此时 PS 已被考虑注意PS 是 S 的父视图。物化 PS 会影响自身和 P。对于 S已有物化视图 S成本 0.1M是最优的因此无收益。计算后物化 PS 的总收益为 0.6M。视图 SC与第一轮类似收益为 0。视图 P物化 P 只影响自身。现在回答 P 的最优成本是通过已物化的 S0.8M。物化 P 后成本降至 0.2M。因此收益为 0.6M。视图 C物化 C 只影响自身。回答 C 的最优成本目前是通过顶层视图6M。物化后成本降至 0.1M。因此收益为 5.9M。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_3.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_5.png第二轮收益计算结果如下| 候选视图 | 收益 (B) || :— | :— || PC | 0 || PS | 0.6M || SC | 0 || P | 0.6M || C |5.9M|在第二轮中视图C的收益最大5.9M。因此我们选择物化视图 C。最终贪心算法选择的物化视图集合是顶层视图、S 和 C。获得的总收益节省的总成本为第一轮收益与第二轮收益之和5.99M 5.9M 11.89M。算法性能分析上一节我们通过例子学习了贪心算法的步骤。本节中我们来看看这个算法的性能如何。我们知道视图物化选择问题本身是 NP 难问题贪心算法是一种启发式方法它可能无法得到最优解。这意味着贪心算法在某些情况下表现可能不佳。我们可以构造一个特例来说明这一点。假设有一个视图依赖结构其中顶层视图下有一些特定成本和关联关系的视图。通过详细计算具体计算过程可课后自行推导贪心算法可能会选择某两个视图例如 B 和 C并获得一个总收益值。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_7.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_7.png然而存在一个“神奇”的最优算法我们假设其能找到绝对最优解它可能会选择另一组视图例如 B 和 D并获得更高的总收益。比较贪心算法的收益与最优算法的收益我们得到一个比值。如果这个比值接近 1说明贪心算法结果接近最优如果比值接近 0说明贪心算法结果远差于最优解。那么贪心算法的这个性能比值是否有下限保证呢答案是肯定的。理论研究证明贪心算法对于视图物化选择问题的解其收益至少能达到最优解收益的 63%即比值下限约为 0.63。这意味着尽管贪心算法不能保证总是找到最佳方案但它能保证找到的方案不会太差至少是最优方案的 63% 以上。这个结论的完整证明可以在相关研究论文中找到。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_10.png总结本节课中我们一起学习了数据仓库中视图物化选择的贪心算法。我们首先定义了“收益”作为选择视图的关键度量然后详细阐述了算法的步骤。接着我们通过一个具体的计算示例一步步演示了如何应用贪心算法做出选择。最后我们分析了算法的性能了解到虽然它是启发式方法但在最坏情况下也有不低于 63% 的性能保证。这使我们在实际应用中能够有信心地使用该算法来处理这类复杂的优化问题。020HITS算法第一部分https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_1.png在本节课中我们将要学习一种重要的网页排名算法——HITS算法。该算法通过分析网页之间的链接关系来评估网页的重要性。我们将从基本概念入手逐步理解其工作原理和计算步骤。概述与背景在互联网搜索中如何快速准确地找到相关网页是一个核心问题。例如在搜索引擎中输入“Raymond Wong”进行搜索会返回大量相关网页。了解搜索引擎的排名机制有助于我们优化网页使其在搜索结果中获得更好的位置。HITS算法是两种主要排名方法之一另一种是Google目前使用的PageRank算法。HITS算法的核心思想是区分两种类型的网页枢纽Hub和权威Authority。核心概念枢纽与权威https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_3.png一个网页可以同时拥有枢纽权重和权威权重。权威Authority如果一个网页被许多其他网页链接那么它就是一个好的权威。权威权重A衡量的是指向该网页的链接数量和质量。公式对于一个网页v其权威权重A(v)是所有指向它的网页的枢纽权重之和。即A(v) Σ H(u)其中u是所有指向v的网页。枢纽Hub如果一个网页包含许多指向其他高质量网页的链接那么它就是一个好的枢纽。枢纽权重H衡量的是该网页指向外部的链接数量和质量。公式对于一个网页v其枢纽权重H(v)是所有它指向的网页的权威权重之和。即H(v) Σ A(u)其中u是所有被v指向的网页。简单来说好的权威被好的枢纽所链接而好的枢纽则链接向好的权威。HITS算法步骤https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_5.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_7.pngHITS算法主要包含两个步骤采样Sampling和迭代Iteration。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_9.png第一步采样构建基础集合给定一个包含若干关键词的用户查询例如“Raymond Wong”算法首先需要确定一个待分析的网页集合称为基础集合Base Set。构建过程如下收集根集合Root Set检索并收集所有包含查询关键词的网页。这些网页构成了根集合。扩展为基集Base Set将所有根集合中的网页加入基础集合。将所有链接到根集合中任一网页的网页加入基础集合。将所有被根集合中任一网页链接到的网页加入基础集合。经过以上步骤我们得到了一个围绕查询主题的、由相关网页及其紧密链接邻居构成的基础集合。后续的排名计算将仅在这个集合内进行。第二步迭代计算权重在获得基础集合后目标是为其中的每个网页计算其枢纽权重和权威权重。这通过一个迭代过程完成。首先我们需要用图来表示基础集合中网页的链接关系。每个网页是一个节点每个超链接是一条有向边。假设我们有一个简单的网络包含三个网页Netscape (N), Microsoft (MS), Amazon (A)。它们的链接关系如下图所示假设N指向MS和AMS指向AN - MS N - A MS - A我们可以用邻接矩阵M来表示这个图。如果网页i链接到网页j则M[i][j] 1否则为0。根据之前的核心概念公式我们可以将枢纽和权威权重的计算表示为矩阵运算。令h为所有网页的枢纽权重向量。令a为所有网页的权威权重向量。那么迭代公式可以写作a M^T * h权威权重等于所有指向它的网页的枢纽权重之和h M * a枢纽权重等于所有它指向的网页的权威权重之和将公式2代入公式1可以得到a M^T * M * a。这意味着权威权重向量a是矩阵M^T * M的特征向量。同理枢纽权重向量h是矩阵M * M^T的特征向量。在实际计算中我们采用迭代逼近法来求解初始化将所有网页的枢纽权重和权威权重设为1或任何相同的正数。进行以下迭代直到收敛a. 根据当前h利用公式a M^T * h更新所有a。b. 对a进行标准化例如使其各分量之和为1或固定值以防止数值过大。c. 根据更新后的a利用公式h M * a更新所有h。d. 对h进行标准化。当连续两次迭代的权重向量变化小于一个极小阈值时认为算法已收敛停止迭代。最终我们得到每个网页稳定的枢纽权重和权威权重。搜索引擎可以根据这些权重对结果进行排序例如按权威权重降序排列或按枢纽与权威权重的综合得分排序。总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_11.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_12.png本节课我们一起学习了HITS算法的第一部分。我们首先了解了网页排名的重要性然后引入了HITS算法的两个核心概念枢纽和权威。接着我们详细讲解了算法的两个主要步骤采样如何构建待分析的基础网页集合和迭代如何通过矩阵运算和迭代逼近来计算每个网页的枢纽与权威权重。理解这些基础是掌握HITS算法以及对比其他排名算法如PageRank的关键。在下一部分我们将通过更具体的例子和细节来深化理解。021PageRank算法第一部分https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_1.png概述在本节课中我们将要学习PageRank算法的基本原理。PageRank是Google搜索引擎早期用于网页排序的核心算法。我们将了解它如何通过一个单一的“重要性”概念来评估网页并学习其背后的随机过程思想。PageRank算法简介上一节我们介绍了基于“枢纽”和“权威”两个概念的排序算法。本节中我们来看看PageRank算法它只使用一个概念来对网页进行排名这使得算法更加简洁。PageRank算法采用了一种随机方法来评估网页。如果你熟悉数学你会知道这涉及到随机矩阵和随机过程的概念。如果不熟悉也没关系可以将其理解为一种概率方法。让我们看一个例子假设有三个网页Na cap、Amazon和Microsoft它们之间的链接关系如下图所示。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_1.png构建随机矩阵此时我们需要定义一个关键矩阵——随机矩阵。这里需要强调这个矩阵是按列归一化的这与我们之前接触的邻接矩阵按行不同很多学生会在这里犯错。按列归一化的含义是矩阵的每一列元素之和为1每个元素的值表示从该列对应的网页跳转到其他网页的概率。以下是构建步骤Na cap列Na cap有2条出链指向Amazon和Microsoft。因此跳转到每个目标页面的概率是1/2 0.5。Amazon列Amazon有1条出链指向Na cap。因此跳转到Na cap的概率是1/1 1跳转到其他页面的概率为0。Microsoft列Microsoft有1条出链指向Amazon。因此跳转到Amazon的概率是1/1 1跳转到其他页面的概率为0。由此我们得到随机矩阵MM [ [0.0, 1.0, 0.0], [0.5, 0.0, 1.0], [0.5, 0.0, 0.0] ]假设行顺序为 [Na cap, Amazon, Microsoft]PageRank迭代计算PageRank算法非常简单其核心迭代公式与枢纽权威值算法类似r_new M * r_old其中r是一个向量代表每个网页的重要性分数。让我们开始迭代计算初始化假设所有网页初始重要性相等。设初始向量r0 [1, 1, 1]。第一次迭代计算r1 M * r0。计算过程r1 [0*1 1*1 0*1, 0.5*1 0*1 1*1, 0.5*1 0*1 0*1] [1, 1.5, 0.5]此时所有网页重要性总和为1 1.5 0.5 3。第二次迭代计算r2 M * r1 [1.25, 0.75, 1]。重要性总和仍为1.25 0.75 1 3。继续重复此过程直到向量r不再发生显著变化收敛。我们会发现在每次迭代中所有网页的重要性总和始终保持不变。总和不变性的证明为什么在PageRank迭代中重要性总和能保持不变而之前的枢纽值算法却需要手动归一化这是一个重要的考点。口头解释因为随机矩阵M是列归一化的。可以想象初始时我们有1个单位的“重要性”分布在各个网页。经过矩阵M的转换这个单位的“重要性”只是被重新分配而不会凭空增加或减少。数学证明假设我们有n个网页当前的重要性向量为r_old [r1, r2, …, rn]其总和为S_old r1 r2 ... rn。随机矩阵M满足一个性质每一列的元素之和为1。即对于任意列j有M[1][j] M[2][j] ... M[n][j] 1。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_3.png计算新的重要性向量r_new M * r_old。其第i个元素为r_new[i] M[i][1]*r1 M[i][2]*r2 ... M[i][n]*rnhttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_5.png那么新的总和S_new为所有r_new[i]相加S_new 所有i的 (M[i][1]*r1 M[i][2]*r2 ... M[i][n]*rn) 之和交换求和顺序先对i求和S_new r1*(M[1][1]M[2][1]...) r2*(M[1][2]M[2][2]...) ... rn*(M[1][n]M[2][n]...)由于矩阵M每列之和为1即(M[1][j]M[2][j]...M[n][j]) 1代入上式S_new r1*1 r2*1 ... rn*1 r1 r2 ... rn S_old因此重要性总和在迭代中保持不变。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_7.png蜘蛛陷阱问题及其影响根据上述计算Microsoft的排名可能较低。假设Microsoft公司对此不满它可以通过修改自己网站的链接结构来操纵排名。例如Microsoft可以移除指向Amazon的链接改为只链接到自己。这样网络结构就变成了下图所示https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_7.png相应的随机矩阵也会改变。如果使用PageRank算法进行迭代最终会发现Microsoft的重要性分数变得非常高成为最重要的网页。这种行为创建了一个蜘蛛陷阱。以下是蜘蛛陷阱的定义蜘蛛陷阱是指一个或多个网页组成的群体这些网页没有指向群体外部的链接。在这个例子中Microsoft的页面只指向自己形成了一个只有一页的蜘蛛陷阱。其影响是在随机游走模型中一旦“重要性”或“随机冲浪者”进入这个陷阱就会永远在里面循环无法离开。最终整个网络几乎所有的重要性都会被这个陷阱页面吸收。解决方案引入阻尼因子Google当然知道这种操纵手法。在实际的PageRank算法中他们引入了一个修正项来避免这个问题。基本思想是在每次跳转时冲浪者不一定完全按照链接前进。他有一定概率例如15%随机跳转到网络中的任何一个网页而只有剩余概率例如85%按照当前页面的出链进行跳转。修正后的PageRank公式通常表示为r_new β * M * r_old (1 - β) * e / N其中β是阻尼因子通常取0.85表示跟随链接的概率。M是原始的随机矩阵。e是一个所有元素都为1的向量。N是网页总数。(1 - β) * e / N项代表了“随机跳转到任意网页”的部分这保证了即使存在蜘蛛陷阱重要性也不会被完全困住。引入阻尼因子后即使Microsoft只链接自己其最终的重要性分数也会被限制在一个更合理的范围内而不会吸收掉所有重要性。此外Google的排名算法还结合了关键词匹配、网站权威性等多种因素使其更加健壮和难以操纵。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_10.png总结本节课中我们一起学习了PageRank算法的第一部分。我们了解了PageRank如何用单一的“重要性”概念和随机矩阵来对网页排序学习了其迭代计算过程并证明了重要性总和的不变性。我们还探讨了算法的一个弱点——蜘蛛陷阱即网站可以通过特定的链接结构操纵排名。最后我们简要介绍了Google如何通过引入阻尼因子随机跳转来解决这个问题使算法更加公平和健壮。
HKUST 数据挖掘知识发现笔记（二）
总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/a943a945bf23f7b32f4555bcec7b1fd5_24.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/a943a945bf23f7b32f4555bcec7b1fd5_25.png本节课中我们一起学习了数据仓库中物化视图的核心概念。我们通过SQL分组聚合的例子理解了视图之间的推导关系。我们重点掌握了物化视图如何通过预计算和存储中间结果来提升查询性能并定义了查询成本和物化增益。最后我们引出了选择性物化问题即在资源约束下如何最优选择要物化的视图集合以最大化性能增益。这是构建高效数据仓库系统的关键基础。018问题定义与NP-hard证明https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_1.png在本节课中我们将学习数据仓库中视图选择问题的形式化定义并证明该问题在计算上是困难的即NP-hard问题。问题定义上一节我们介绍了数据仓库中物化视图的概念。在了解其收益计算方式后我们明确要解决的问题是从所有可能的视图中选择一个子集进行物化使得总收益最大化。问题公式化给定一个视图格Lattice和物化视图的数量限制K目标是选择一个包含K个视图的集合V使得总收益Gain(V)最大化。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_1.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_3.png证明视图选择问题是NP-hard作为计算机科学家我们需要判断这个问题是否非常困难。与关联规则挖掘类似我们也想证明这个问题是NP-hard的。我们将使用一个已知的NP完全问题来进行归约证明。我们首先将上述最大化问题转化为一个决策问题。在NP-hard证明中通常使用决策问题。决策问题的答案是“是”或“否”。选择性物化决策问题给定一个整数K和一个实数J是否存在一个包含K个视图的集合V使得其信息增益至少为J我们的目标是证明这个决策问题是NP-hard的。使用已知的NP完全问题精确3覆盖证明方法与关联规则挖掘中学过的类似。我们使用一个已知的NP完全问题“精确3覆盖”Exact Cover by 3-Sets X3C。X3C问题定义给定一个包含3q个元素的集合X以及一个由X的3元素子集构成的集合C。问C中是否包含一个精确覆盖C‘C‘是C的子集使得X中的每个元素在C’中恰好出现一次为了让定义更清晰请看以下示例。示例一答案是“是”集合 X {A, B, C, D, E, F}集合 C { {A, B, C}, {B, C, D}, {D, E, F} }我们可以找到子集 C‘ { {A, B, C}, {D, E, F} }。X中的每个元素A, B, C, D, E, F在C’中都恰好出现一次。因此答案是“是”。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_5.png示例二答案是“否”集合 X {A, B, C, D, E, F}集合 C { {A, B, C}, {B, C, D}, {A, E, F} }https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_7.png无法找到满足条件的子集C‘。例如如果选择{A, B, C}和{A, E, F}则元素A出现了两次如果选择{B, C, D}和{A, E, F}则元素B、C、D、E、F都只出现一次但元素A没有出现。因此答案是“否”。精确3覆盖X3C是一个已被证明的NP完全问题。从X3C到视图选择问题的归约现在我们将X3C问题归约到我们的选择性物化决策问题。以下是归约步骤的概述随后将通过一个具体例子进行解释。归约构造如下创建一个根节点大小为200称为“魔法数字”位于第1层。创建一个底层节点大小为1位于第4层。对于X中的每个元素x创建一个节点N_x大小为50位于第3层。在N_x和底层节点之间创建一条边。对于C中的每个3元素子集A {x, y, z}创建一个节点N_A大小为100位于第2层。创建N_A到根节点的边以及N_A到N_x、N_y、N_z的边。在我们的决策问题中设K q即X中元素组数。设决策阈值 J 400 * q。你可能对其中出现的数字感到疑惑。接下来我们通过一个例子来具体说明。归约示例我们使用示例一的X3C实例进行归约X {A, B, C, D, E, F} 所以 q 2。C { {A, B, C}, {B, C, D}, {D, E, F} }。根据归约步骤K q 2。J 400 * q 800。构建的视图格结构如下图所示节点旁的数字为其“大小”属性。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_3.png现在考虑我们的选择性物化问题除了顶层的根视图必须物化外我们还需要选择K2个视图进行物化使得总收益至少达到J800。根据收益计算规则物化一个视图的收益等于其祖先视图中未被物化的最小祖先的大小我们可以计算各个候选视图的收益物化“ABC”视图的收益是100。物化“BCD”视图的收益是100。物化“DEF”视图的收益是100。那么选择哪两个视图能使总收益最大化呢答案是选择“ABC”和“DEF”。选择“ABC”它能为底层A、B、C三个元素的查询各节省100总收益300严格计算是覆盖了其下4个节点收益为4*100400此处为简化理解。选择“DEF”它能为底层D、E、F三个元素的查询各节省100总收益300。两者总收益为600按简化计算或800按图中结构精确计算每个物化视图为其4个后代节点各贡献100收益。无论如何计算选择“ABC”和“DEF”都能使总收益达到最大值并且至少为800满足决策问题的要求。归约的正确性与魔法数字的含义关键点在于在这个构造的实例中能够达到收益阈值J800的物化方案选择“ABC”和“DEF”恰好对应了原X3C问题的一个解{ {A, B, C}, {D, E, F} }。魔法数字200, 100, 50, 1的设置是为了确保只有物化那些完全覆盖三个独立底层元素且不与其他物化视图覆盖的元素重叠的第2层节点即C中的子集对应的节点才能获得最大收益。收益阈值J400*q被设置为只有当物化的q个节点恰好构成一个精确覆盖时才能达到的值。这些数字并非固定不变。例如若将根节点大小改为500第2层节点大小改为200那么相应的J值应变为 (500-200)*4 * q 1200 * q。其核心原理是保持收益计算的比例关系使得“精确覆盖”对应的物化方案具有最大且唯一的收益值。因此如果我们能解决这个选择性物化决策问题就等于解决了X3C问题。由于X3C是NP完全的所以选择性物化决策问题至少是NP-hard的。进而最初的最大化收益视图选择问题也是NP-hard的。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_11.png实例的物理意义最后让我们回顾一个更具体的例子理解视图格中节点的物理意义。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_9.png考虑一个视图格其属性包括零件P、供应商S、客户C。节点“PC”表示按零件和客户分组聚合的视图。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_11.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_12.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_14.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_16.png在数据库理论中这通常与函数依赖有关。例如图中“PC”视图的大小与“PSC”视图相同这可能暗示着一种函数依赖P, C可以唯一确定S。这意味着在原始数据中给定一个零件和一个客户对应的供应商是唯一的。这种语义约束会影响视图的大小从而影响物化视图的选择策略。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_17.png总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_16.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/fe329ebed9e23718a88f8dc15209365d_17.png本节课中我们一起学习了数据仓库视图选择问题的形式化定义。我们通过将已知的NP完全问题——精确3覆盖X3C——归约到视图选择的决策问题证明了该问题是一个NP-hard问题这意味着在多项式时间内找到最优解是极其困难的。最后我们还探讨了视图格结构中可能蕴含的数据库语义如函数依赖。理解问题的计算复杂性是设计高效启发式算法或近似算法的基础。019视图物化选择算法https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_1.png概述在本节课中我们将学习数据仓库中一个重要的优化问题如何从众多可能的物化视图中选择一部分进行物理存储以最小化查询的总成本。我们将重点介绍解决此问题的贪心算法并通过一个具体例子来演示其计算过程。最后我们将探讨该算法的性能表现。算法介绍上一节我们介绍了视图物化选择问题的背景。本节中我们来看看解决该问题的核心算法——贪心算法。该算法思路非常简单直接。首先我们需要定义一个关键概念收益。给定一个视图集合S代表已选择物化的视图我们定义选择某个视图v进行物化的收益B(v, S)如下公式B(v, S) ∑ (对于每个能被 v 或其物化后代回答的视图 w计算未物化 v 时回答 w 的最小成本 - 物化 v 后回答 w 的最小成本)简单来说收益就是物化视图v后能为整个查询系统节省的总成本。基于收益的定义贪心算法的步骤如下算法伪代码输入需要物化的视图数量 k 1. 初始化选择集合 S {顶层视图} // 顶层视图总是被物化 2. FOR i 1 TO k DO 3. 对于每一个不在 S 中的视图 v计算其收益 B(v, S) 4. 选择收益 B(v, S) 最大的视图 v_max 5. 将 v_max 加入集合 SS S ∪ {v_max} 6. END FOR 7. 输出最终的选择集合 S算法示例为了帮助理解我们通过一个具体的例子来演示贪心算法的执行过程。假设我们有一个数据立方体其视图的依赖关系及查询成本如下图所示。我们的目标是选择k2个视图除了顶层视图进行物化。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_1.png我们通常会绘制一个收益计算表来辅助决策。初始时只有顶层视图被物化。以下是第一轮迭代选择第一个视图的收益计算过程视图 PC它会影响自身以及其父视图 P 和 C。物化前回答 PC 查询的成本是 6M。物化后成本变为 6M因为物化成本等于查询成本。因此对自身的收益为 0。对于 P 和 C由于物化 PC 并不能提供比现有顶层视图更优的路径来回答 P 和 C 的查询收益也为 0。总收益为 0。视图 PS它会影响自身以及 P 和 S。物化前回答 PS 查询的成本是 6M。物化后成本变为 0.8M。因此对自身的收益为 5.2M。对于 P 和 S同样因为无法提供更优路径收益为 0。总收益为 5.2M。视图 SC与 PC 对称总收益为 0。视图 P它只影响自身。物化前通过顶层视图回答 P 的成本是 6M。物化后成本变为 0.2M。因此收益为 5.8M。视图 S与 P 类似收益为 5.99M。视图 C与 P 类似收益为 5.9M。第一轮收益计算结果如下表所示| 候选视图 | 收益 (B) || :— | :— || PC | 0 ||PS|5.2M|| SC | 0 || P | 5.8M || S | 5.99M || C | 5.9M |根据贪心策略我们选择收益最大的视图。在本轮中视图S的收益最大5.99M因此我们物化视图 S。现在进入第二轮迭代选择第二个视图。此时物化集合S已包含 {顶层视图 S}。以下是第二轮迭代的收益计算要点需考虑已物化的视图 S 的影响视图 PC物化 PC 主要影响自身和 C。对于 P由于已有物化视图 S通过 S 回答 P 的成本为 0.8M这比通过 PC 路径6M更优因此物化 PC 对 P 无收益。最终计算出的总收益为 0。视图 PS此时 PS 已被考虑注意PS 是 S 的父视图。物化 PS 会影响自身和 P。对于 S已有物化视图 S成本 0.1M是最优的因此无收益。计算后物化 PS 的总收益为 0.6M。视图 SC与第一轮类似收益为 0。视图 P物化 P 只影响自身。现在回答 P 的最优成本是通过已物化的 S0.8M。物化 P 后成本降至 0.2M。因此收益为 0.6M。视图 C物化 C 只影响自身。回答 C 的最优成本目前是通过顶层视图6M。物化后成本降至 0.1M。因此收益为 5.9M。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_3.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_5.png第二轮收益计算结果如下| 候选视图 | 收益 (B) || :— | :— || PC | 0 || PS | 0.6M || SC | 0 || P | 0.6M || C |5.9M|在第二轮中视图C的收益最大5.9M。因此我们选择物化视图 C。最终贪心算法选择的物化视图集合是顶层视图、S 和 C。获得的总收益节省的总成本为第一轮收益与第二轮收益之和5.99M 5.9M 11.89M。算法性能分析上一节我们通过例子学习了贪心算法的步骤。本节中我们来看看这个算法的性能如何。我们知道视图物化选择问题本身是 NP 难问题贪心算法是一种启发式方法它可能无法得到最优解。这意味着贪心算法在某些情况下表现可能不佳。我们可以构造一个特例来说明这一点。假设有一个视图依赖结构其中顶层视图下有一些特定成本和关联关系的视图。通过详细计算具体计算过程可课后自行推导贪心算法可能会选择某两个视图例如 B 和 C并获得一个总收益值。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_7.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_7.png然而存在一个“神奇”的最优算法我们假设其能找到绝对最优解它可能会选择另一组视图例如 B 和 D并获得更高的总收益。比较贪心算法的收益与最优算法的收益我们得到一个比值。如果这个比值接近 1说明贪心算法结果接近最优如果比值接近 0说明贪心算法结果远差于最优解。那么贪心算法的这个性能比值是否有下限保证呢答案是肯定的。理论研究证明贪心算法对于视图物化选择问题的解其收益至少能达到最优解收益的 63%即比值下限约为 0.63。这意味着尽管贪心算法不能保证总是找到最佳方案但它能保证找到的方案不会太差至少是最优方案的 63% 以上。这个结论的完整证明可以在相关研究论文中找到。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/f57122e22e784ee8b81addeccb4f7d78_10.png总结本节课中我们一起学习了数据仓库中视图物化选择的贪心算法。我们首先定义了“收益”作为选择视图的关键度量然后详细阐述了算法的步骤。接着我们通过一个具体的计算示例一步步演示了如何应用贪心算法做出选择。最后我们分析了算法的性能了解到虽然它是启发式方法但在最坏情况下也有不低于 63% 的性能保证。这使我们在实际应用中能够有信心地使用该算法来处理这类复杂的优化问题。020HITS算法第一部分https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_1.png在本节课中我们将要学习一种重要的网页排名算法——HITS算法。该算法通过分析网页之间的链接关系来评估网页的重要性。我们将从基本概念入手逐步理解其工作原理和计算步骤。概述与背景在互联网搜索中如何快速准确地找到相关网页是一个核心问题。例如在搜索引擎中输入“Raymond Wong”进行搜索会返回大量相关网页。了解搜索引擎的排名机制有助于我们优化网页使其在搜索结果中获得更好的位置。HITS算法是两种主要排名方法之一另一种是Google目前使用的PageRank算法。HITS算法的核心思想是区分两种类型的网页枢纽Hub和权威Authority。核心概念枢纽与权威https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_3.png一个网页可以同时拥有枢纽权重和权威权重。权威Authority如果一个网页被许多其他网页链接那么它就是一个好的权威。权威权重A衡量的是指向该网页的链接数量和质量。公式对于一个网页v其权威权重A(v)是所有指向它的网页的枢纽权重之和。即A(v) Σ H(u)其中u是所有指向v的网页。枢纽Hub如果一个网页包含许多指向其他高质量网页的链接那么它就是一个好的枢纽。枢纽权重H衡量的是该网页指向外部的链接数量和质量。公式对于一个网页v其枢纽权重H(v)是所有它指向的网页的权威权重之和。即H(v) Σ A(u)其中u是所有被v指向的网页。简单来说好的权威被好的枢纽所链接而好的枢纽则链接向好的权威。HITS算法步骤https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_5.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_7.pngHITS算法主要包含两个步骤采样Sampling和迭代Iteration。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_9.png第一步采样构建基础集合给定一个包含若干关键词的用户查询例如“Raymond Wong”算法首先需要确定一个待分析的网页集合称为基础集合Base Set。构建过程如下收集根集合Root Set检索并收集所有包含查询关键词的网页。这些网页构成了根集合。扩展为基集Base Set将所有根集合中的网页加入基础集合。将所有链接到根集合中任一网页的网页加入基础集合。将所有被根集合中任一网页链接到的网页加入基础集合。经过以上步骤我们得到了一个围绕查询主题的、由相关网页及其紧密链接邻居构成的基础集合。后续的排名计算将仅在这个集合内进行。第二步迭代计算权重在获得基础集合后目标是为其中的每个网页计算其枢纽权重和权威权重。这通过一个迭代过程完成。首先我们需要用图来表示基础集合中网页的链接关系。每个网页是一个节点每个超链接是一条有向边。假设我们有一个简单的网络包含三个网页Netscape (N), Microsoft (MS), Amazon (A)。它们的链接关系如下图所示假设N指向MS和AMS指向AN - MS N - A MS - A我们可以用邻接矩阵M来表示这个图。如果网页i链接到网页j则M[i][j] 1否则为0。根据之前的核心概念公式我们可以将枢纽和权威权重的计算表示为矩阵运算。令h为所有网页的枢纽权重向量。令a为所有网页的权威权重向量。那么迭代公式可以写作a M^T * h权威权重等于所有指向它的网页的枢纽权重之和h M * a枢纽权重等于所有它指向的网页的权威权重之和将公式2代入公式1可以得到a M^T * M * a。这意味着权威权重向量a是矩阵M^T * M的特征向量。同理枢纽权重向量h是矩阵M * M^T的特征向量。在实际计算中我们采用迭代逼近法来求解初始化将所有网页的枢纽权重和权威权重设为1或任何相同的正数。进行以下迭代直到收敛a. 根据当前h利用公式a M^T * h更新所有a。b. 对a进行标准化例如使其各分量之和为1或固定值以防止数值过大。c. 根据更新后的a利用公式h M * a更新所有h。d. 对h进行标准化。当连续两次迭代的权重向量变化小于一个极小阈值时认为算法已收敛停止迭代。最终我们得到每个网页稳定的枢纽权重和权威权重。搜索引擎可以根据这些权重对结果进行排序例如按权威权重降序排列或按枢纽与权威权重的综合得分排序。总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_11.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/64b19108c0e87249c6c2abaa579ce795_12.png本节课我们一起学习了HITS算法的第一部分。我们首先了解了网页排名的重要性然后引入了HITS算法的两个核心概念枢纽和权威。接着我们详细讲解了算法的两个主要步骤采样如何构建待分析的基础网页集合和迭代如何通过矩阵运算和迭代逼近来计算每个网页的枢纽与权威权重。理解这些基础是掌握HITS算法以及对比其他排名算法如PageRank的关键。在下一部分我们将通过更具体的例子和细节来深化理解。021PageRank算法第一部分https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_1.png概述在本节课中我们将要学习PageRank算法的基本原理。PageRank是Google搜索引擎早期用于网页排序的核心算法。我们将了解它如何通过一个单一的“重要性”概念来评估网页并学习其背后的随机过程思想。PageRank算法简介上一节我们介绍了基于“枢纽”和“权威”两个概念的排序算法。本节中我们来看看PageRank算法它只使用一个概念来对网页进行排名这使得算法更加简洁。PageRank算法采用了一种随机方法来评估网页。如果你熟悉数学你会知道这涉及到随机矩阵和随机过程的概念。如果不熟悉也没关系可以将其理解为一种概率方法。让我们看一个例子假设有三个网页Na cap、Amazon和Microsoft它们之间的链接关系如下图所示。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_1.png构建随机矩阵此时我们需要定义一个关键矩阵——随机矩阵。这里需要强调这个矩阵是按列归一化的这与我们之前接触的邻接矩阵按行不同很多学生会在这里犯错。按列归一化的含义是矩阵的每一列元素之和为1每个元素的值表示从该列对应的网页跳转到其他网页的概率。以下是构建步骤Na cap列Na cap有2条出链指向Amazon和Microsoft。因此跳转到每个目标页面的概率是1/2 0.5。Amazon列Amazon有1条出链指向Na cap。因此跳转到Na cap的概率是1/1 1跳转到其他页面的概率为0。Microsoft列Microsoft有1条出链指向Amazon。因此跳转到Amazon的概率是1/1 1跳转到其他页面的概率为0。由此我们得到随机矩阵MM [ [0.0, 1.0, 0.0], [0.5, 0.0, 1.0], [0.5, 0.0, 0.0] ]假设行顺序为 [Na cap, Amazon, Microsoft]PageRank迭代计算PageRank算法非常简单其核心迭代公式与枢纽权威值算法类似r_new M * r_old其中r是一个向量代表每个网页的重要性分数。让我们开始迭代计算初始化假设所有网页初始重要性相等。设初始向量r0 [1, 1, 1]。第一次迭代计算r1 M * r0。计算过程r1 [0*1 1*1 0*1, 0.5*1 0*1 1*1, 0.5*1 0*1 0*1] [1, 1.5, 0.5]此时所有网页重要性总和为1 1.5 0.5 3。第二次迭代计算r2 M * r1 [1.25, 0.75, 1]。重要性总和仍为1.25 0.75 1 3。继续重复此过程直到向量r不再发生显著变化收敛。我们会发现在每次迭代中所有网页的重要性总和始终保持不变。总和不变性的证明为什么在PageRank迭代中重要性总和能保持不变而之前的枢纽值算法却需要手动归一化这是一个重要的考点。口头解释因为随机矩阵M是列归一化的。可以想象初始时我们有1个单位的“重要性”分布在各个网页。经过矩阵M的转换这个单位的“重要性”只是被重新分配而不会凭空增加或减少。数学证明假设我们有n个网页当前的重要性向量为r_old [r1, r2, …, rn]其总和为S_old r1 r2 ... rn。随机矩阵M满足一个性质每一列的元素之和为1。即对于任意列j有M[1][j] M[2][j] ... M[n][j] 1。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_3.png计算新的重要性向量r_new M * r_old。其第i个元素为r_new[i] M[i][1]*r1 M[i][2]*r2 ... M[i][n]*rnhttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_5.png那么新的总和S_new为所有r_new[i]相加S_new 所有i的 (M[i][1]*r1 M[i][2]*r2 ... M[i][n]*rn) 之和交换求和顺序先对i求和S_new r1*(M[1][1]M[2][1]...) r2*(M[1][2]M[2][2]...) ... rn*(M[1][n]M[2][n]...)由于矩阵M每列之和为1即(M[1][j]M[2][j]...M[n][j]) 1代入上式S_new r1*1 r2*1 ... rn*1 r1 r2 ... rn S_old因此重要性总和在迭代中保持不变。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_7.png蜘蛛陷阱问题及其影响根据上述计算Microsoft的排名可能较低。假设Microsoft公司对此不满它可以通过修改自己网站的链接结构来操纵排名。例如Microsoft可以移除指向Amazon的链接改为只链接到自己。这样网络结构就变成了下图所示https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_7.png相应的随机矩阵也会改变。如果使用PageRank算法进行迭代最终会发现Microsoft的重要性分数变得非常高成为最重要的网页。这种行为创建了一个蜘蛛陷阱。以下是蜘蛛陷阱的定义蜘蛛陷阱是指一个或多个网页组成的群体这些网页没有指向群体外部的链接。在这个例子中Microsoft的页面只指向自己形成了一个只有一页的蜘蛛陷阱。其影响是在随机游走模型中一旦“重要性”或“随机冲浪者”进入这个陷阱就会永远在里面循环无法离开。最终整个网络几乎所有的重要性都会被这个陷阱页面吸收。解决方案引入阻尼因子Google当然知道这种操纵手法。在实际的PageRank算法中他们引入了一个修正项来避免这个问题。基本思想是在每次跳转时冲浪者不一定完全按照链接前进。他有一定概率例如15%随机跳转到网络中的任何一个网页而只有剩余概率例如85%按照当前页面的出链进行跳转。修正后的PageRank公式通常表示为r_new β * M * r_old (1 - β) * e / N其中β是阻尼因子通常取0.85表示跟随链接的概率。M是原始的随机矩阵。e是一个所有元素都为1的向量。N是网页总数。(1 - β) * e / N项代表了“随机跳转到任意网页”的部分这保证了即使存在蜘蛛陷阱重要性也不会被完全困住。引入阻尼因子后即使Microsoft只链接自己其最终的重要性分数也会被限制在一个更合理的范围内而不会吸收掉所有重要性。此外Google的排名算法还结合了关键词匹配、网站权威性等多种因素使其更加健壮和难以操纵。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_9.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/hkust-dtmn/img/92553723b9fa9f12d2c8202c034dcfb2_10.png总结本节课中我们一起学习了PageRank算法的第一部分。我们了解了PageRank如何用单一的“重要性”概念和随机矩阵来对网页排序学习了其迭代计算过程并证明了重要性总和的不变性。我们还探讨了算法的一个弱点——蜘蛛陷阱即网站可以通过特定的链接结构操纵排名。最后我们简要介绍了Google如何通过引入阻尼因子随机跳转来解决这个问题使算法更加公平和健壮。 
