精华内容
下载资源
问答
  • 战略分析工具:PEST分析模型、波特五力模型、价值链分析、雷达图、因果关系、利益相关者分析、竞争者分析。 战略选择工具:SWOT分析、波士顿矩阵、通用矩阵、V矩阵、EVA管理、定向政策矩阵、战略地位和行动评估矩阵...

    在做信息化规划、产品设计、需求分析、商业计划书、组织机构优化管理咨询等业务活动过程中,信息收集与分析是非常重要的环节,是建立领域模型的基础。如何做好信息收集及分析工作,对于有一定经验的人员来说,可以采用自顶向下方法,参照战略分析工具指引,探索业务机理,快速建立领域管理模型。

    本文重点是整理战略分析工具分类、关系及简明介绍。

    (1). 战略分析工具
    PEST分析模型、波特五力模型、价值链分析、雷达图、因果关系、利益相关者分析、竞争者分析。
    (2). 战略选择工具
    SWOT分析、波士顿矩阵、通用矩阵、V矩阵、EVA管理、定向政策矩阵、战略地位和行动评估矩阵。

    针对SWOT中的威胁部分,可以用五力分析模型来得到系统的分析结果。
    针对SWOT中的机会部分,可以用PEST进行分析得到系统的结果。

    1. PEST分析模型

    PEST分析是指宏观环境的分析,宏观环境又称一般环境,是指一切影响行业和企业的宏观因素。对宏观环境因素作分析,不同行业和企业根据自身特点和经营需要,分析的具体内容会有差异,但一般都应对政治(Political)、经济(Economic)、社会(Social)和技术(Technological)这四大类影响企业的主要外部环境因素进行分析。

    (1)政治环境(P),主要包括:政治制度与体制,政局,政府的态度等;法律环境主要包括政府制定的法律、法规。
    (2)经济环境(E),主要包括:GDP、利率水平、财政货币政策通货膨胀失业率水平、居民可支配收入水平、汇率、能源供给成本、市场机制、市场需求等。
    (3)社会(S),主要包括:人口环境和文化背景,而人口环境主要包括人口规模、年龄结构、人口分布、种族结构以及收入分布等因素。
    (4)技术(T),主要包括:发明及企业市场有关的新技术、新工艺、新材料的出现和发展趋势以及应用背景。

    应用场景:
    (1)官方:公司制定政策、大的发展战略时应用。
    (2)个人:选择应聘企业、选购股票、选择副业等等。

    下表是一个典型的PEST分析。

    政治 (包括法律) 经济 社会 技术
    环保制度 经济增长 收入分布 政府研究开支
    税收政策 利率与货币政策 人口统计、人口增长率与年龄分布 产业技术关注
    国际贸易章程与限制 政府开支 劳动力与社会流动性 新型发明与技术发展
    合同执行法、消费者保护法 失业政策 生活方式变革 技术转让率
    雇用法律 征税 职业与休闲态度、企业家精神 技术更新速度与生命周期
    政府组织/态度 汇率 教育 能源利用与成本
    竞争规则 通货膨胀率 潮流与风尚 信息技术变革
    政治稳定性 商业周期的所处阶段 健康意识、社会福利及安全感 互联网的变革
    安全规定 消费者信心 生活条件 移动技术变革

    2. 波特五力模型

    波特五力模型是迈克尔·波特(Michael Porter)于20世纪80年代初提出。他认为行业中存在着决定竞争规模和程度的五种力量,这五种力量综合起来影响着产业的吸引力以及现有企业的竞争战略决策。五种力量分别为同行业内现有竞争者的竞争能力、潜在竞争者进入的能力、替代品的替代能力、供应商的讨价还价能力、购买者的讨价还价能力。

    在这里插入图片描述

    缺点:
    关于五力分析模型的实践运用一直存在许多争论。较为一致的看法是:该模型更多是一种理论思考工具,而非可以实际操作的战略工具。该模型的理论是建立在以下三个假定基础之上的:
    1、制定战略者需要了解整个行业的信息,显然现实中是难于做到的。
    2、同行业之间只有竞争关系,没有合作关系。但现实中企业之间存在多种合作关系,不一定是你死我活的竞争关系。
    3、行业的规模是固定的,因此,只有通过夺取对手的份额来占有更大的资源和市场。但现实中企业之间往往不是通过吃掉对手而是与对手共同做大行业的蛋糕来获取更大的资源和市场。同时,市场可以通过不断的开发和创新来增大容量。

    3. 企业价值链

    “价值链”这一概念由迈克尔·波特(Michael Porter)于1985年提出,他将一个企业的经营活动分解为若干战略性相关的价值活动,每一种价值活动都会对企业的相对成本地位产生影响,并成为企业采取差异化战略的基础。

    企业价值链是以企业内部价值活动为核心所形成的价值链体系。企业的价值活动可以分为两类活动,即基本活动和辅助活动,共计九项一般的活动类型。基本活动是那些涉及到产品实物形态的生产、营销和向买方的支付,以及产品支持和售后服务等。辅助活动指的是对企业基本活动有辅助作用的投入和基础设施。
    在这里插入图片描述

    价值链分析的关键是,要认识企业不是机器、货币和人员的随机组合,如果不将这些资源有效地组织起来,生产出最终顾客认为有价值的产品或服务,那么这些资源将毫无价值。因此,资源分析必须是一个从资源评估到对怎样使用这些资源的评估过程。

    企业资源能力的价值链分析要明确以下几点:

    1.确认那些支持企业竞争优势的关键性活动。

    虽然价值链的每项活动,包括基本活动和支持活动都是企业成功所必经的环节,但是,这些活动对企业竞争优势的影响是不同的。在关键活动的基础上建立和强化这种优势很可能使企业获得成功。支持企业竞争优势的关键性活动事实上就是企业的独特能力的一部分。

    2.明确价值链内各种活动之间的联系。

    价值链中基本活动之间、基本活动与支持活动之间以及支持活动之间存在各种联系,选择或构筑最佳的联系方式对于提高价值创造和战略能力是十分重要的。

    3.明确价值系统内各项活动之间的联系。

    价值活动的联系不仅存在于企业价值链内部,而且存在于企业与企业的价值链之间。

    4. 雷达图分析法

    雷达图法是日本企业界的综合实力进行评估而采用的一种财务状况综合评价方法。按这种方法所绘制的财务比率综合图状似雷达,故得此名。

    雷达图是对客户财务能力分析的重要工具,从动态和静态两个方面分析客户的财务状况。静态分析将客户的各种财务比率与其他相似客户或整个行业的财务比率作横向比较;动态分析把客户现时的财务比率与先前的财务比率作纵向比较,就可以发现客户财务及经营情况的发展变化方向。雷达图把纵向和横向的分析比较方法结合起来,计算综合客户的收益性、成长性、安全性、流动性及生产性这五类指标。

    1.收益性指标
    分析收益性指标,目的在于观察客户一定时期的收益及获利能力。主要指标含义及计算公式如下表所示:
    在这里插入图片描述

    2.安全性指标
    安全性指的是客户经营的安全程度,也可以说是资金调度的安全性。分析安全性指标,目的在于观察客户在一定时期内偿债能力。主要指标含义及计算公式如图所示:

    3.流动性指标
    分析流动性指标,目的在于观察客户在一定时期内的资金周转状况,掌握客户资金的运用效率。主要指标含义及计算公式如图所示:

    4.成长性指标
    分析成长性指标,目的在于观察客户在一定时期内经营能力的发展变化趋势,一个客户既使收益性高,但成长必不好,也就表明其未来盈利能力下降。因此,以发展的眼光看客户,动态的分析客户财务资料,对战略制定来讲特别重要。

    5.生产性指标
    分析生产性指标,目的在于了解在一定时期内客户的生产经营能力、水平和成果的分配。主要指标如图所示:
    在这里插入图片描述
    上述客户财务能力的五性分析结果可以用雷达图表示出来,如下图所示。
    在这里插入图片描述
    雷达图的绘制方法是:
    (1)画出三个同心圆,同心圆的最小圆圈代表同行业平均水平的1/2值或最低水平,中间圆圈代表同行业平均水平,又称标准线,最大圆圈代表同行先进水平或平均水平的1.5倍;
    (2)把这三个圆圈的360度。分成五个扇形区,分别代表收益性、安全性、流动性、成长性和生产性指标区域;
    (3)从5个扇形区的圆心开始以放射线的形式分别画出相应的财务指标线,并标明指标名称及标度,财务指标线的比例尺及同心圆的大小由该经营比率的量纲与同行业的水平来决定;
    (4)把客户同期的相应指标值用点标在图上,以线段依次连接相邻点,形成的多边形折线闭环,就代表了客户的现实财务状况。

    5. 波士顿矩阵模型

    波士顿矩阵(BCG Matrix),又称市场增长率-相对市场份额矩阵、波士顿咨询集团法、四象限分析法、产品系列结构管理法等。波士顿矩阵由美国著名的管理学家、波士顿咨询公司创始人布鲁斯·亨德森于1970年首创。

    波士顿矩阵认为一般决定产品结构的基本因素有两个:即市场引力与企业实力。市场引力包括整个市场的销售量(额)增长率、竞争对手强弱及利润高低等。其中最主要的是反映市场引力的综合指标——销售增长率,这是决定企业产品结构是否合理的外在因素。

    企业实力包括市场占有率,技术、设备、资金利用能力等,其中市场占有率是决定企业产品结构的内在要素,它直接显示出企业竞争实力。销售增长率与市场占有率既相互影响,又互为条件:市场引力大,市场占有高,可以显示产品发展的良好前景,企业也具备相应的适应能力,实力较强;如果仅有市场引力大,而没有相应的高市场占有率,则说明企业尚无足够实力,则该种产品也无法顺利发展。相反,企业实力强,而市场引力小的产品也预示了该产品的市场前景不佳。

    通过以上两个因素相互作用,会出现四种不同性质的产品类型,形成不同的产品发展前景:
    (1)明星类产品:销售增长率和市场占有率“双高”的产品群;
    (2)销售增长率和市场占有率“双低”的产品群(瘦狗类产品);
    (3)销售增长率高、市场占有率低的产品群(问题类产品);
    (4)销售增长率低、市场占有率高的产品群(金牛类产品)。

    在这里插入图片描述

    6. SWOT分析

    所谓SWOT分析,即基于内外部竞争环境和竞争条件下的态势分析,就是将与研究对象密切相关的各种主要内部优势、劣势和外部的机会和威胁等,通过调查列举出来,并依照矩阵形式排列,然后用系统分析的思想,把各种因素相互匹配起来加以分析,从中得出一系列相应的结论,而结论通常带有一定的决策性。
    运用这种方法,可以对研究对象所处的情景进行全面、系统、准确的研究,从而根据研究结果制定相应的发展战略、计划以及对策等。
    S (strengths)是优势、W (weaknesses)是劣势,O (opportunities)是机会、T (threats)是威胁。按照企业竞争战略的完整概念,战略应是一个企业“能够做的”(即组织的强项和弱项)和“可能做的”(即环境的机会和威胁)之间的有机组合。
    在这里插入图片描述
    SWOT分析步骤:
    一、环境因素分析
    1、外部环境分析
    PEST分析、五力分析
    (政策信息、市场调查、竞争对手调查、其他渠道调查)

    2、内部环境分析
    QCDMS
    (会议、报告、内部沟通等渠道获得信息)
    二、构造SWOT矩阵
    1、将调查的出的各种因素填入矩阵图
    2、按轻重缓急或影响程度等排序方式,构造SWOT矩阵
    将对公司发展有直接的、重要的、大量的、迫切的、久远的影响因素优先排列出来
    将间接的、次要的、少许的、不急的、短暂的影响因素排在后面

    三、制定战略计划
    1、战略(方针、目标)
    战略框架图、战略结构图。
    2、战术(路线图)
    战略系统图。
    3、战法(步骤)
    具体实施方法、KT法、PDCA、其他管理工具。

    QCDMS是指Quality(品质)、Cost(成本)、Delivery(交期)、Morale(士气)、Safety(安全)。

    7. 麦肯锡矩阵/通用矩阵/GE矩阵

    在使用麦肯锡矩阵的时候,一般是根据具体业务模块在市场上的竞争实力和所在市场的吸引力两个维度进行评估,每个维度用高中低三个档来评价,形成一个3×3的矩阵(九宫格):
    在这里插入图片描述
    在使用GE矩阵时,要确定出每个经营单位在矩阵中的位置,必须将行业吸引力和竞争能力中的每个因素进行量化。

    一般来说,在对影响行业吸引力和竞争能力进行度量时可选用具有五等级的里克特等级度量法,如表所示
    在这里插入图片描述

    注:路灯区:扩展;黄灯区:维持;红灯区:回收。

    在战略规划过程中,应用GE矩阵必须经历以下5个步骤:

    (1)确定战略业务单位,并对每个战略业务单位进行内外部环境分析。根据企业的实际情况,或依据产品(包括服务),或依据地域,对企业的业务进行划分,形成战略业务单位,并根据针对每一个战略业务单位进行内外部环境分析。

    (2)确定评价因素及每个因素权重。确定市场吸引力和企业竞争力的主要评价指标,及每一个指标所占的权重。市场吸引力和企业竞争力的评价指标没有通用标准,必须根据企业所处的行业特点和企业发展阶段、行业竞争状况进行确定。但是从总体上讲,市场吸引力主要由行业的发展潜力和盈利能力决定,企业竞争力主要由企业的财务资源、人力资源、技术能力和经验、无形资源与能力决定。确定评价指标的同时还必须确定每个评价指标的权重。

    (3)进行评估打分。根据行业分析结果,对各战略业务单位的市场吸引力和竞争力进行评估和打分,并加权求和,得到每一项战略业务单元的市场吸引力和竞争力最终得分。

    (4)将个战略单位标在GE矩阵上。根据每个战略业务单位的市场吸引力和竞争力总体得分,将每个战略业务单位用圆圈标在GE矩阵上。在标注时,注意圆圈的大小表示战略业务单位的市场总量规模。有的还可以用扇形反映企业的市场占有率。

    (5)对各战略单位策略进行说明。根据每个战略业务单位在GE矩阵上的位置,对各个战略业务单位的发展战略指导思想进行系统说明和阐述。

    在这里插入图片描述

    要素定义样例如下:

    外部要素—行业吸引力要素
    企业要想得到发展,必须在行业中有一定的吸引力,这样才能够占领市场,争夺到自己的客户。下面这些就是在行业吸引力要素中必要重要的一些要素:
    1.企业在市场中的营销能力
    2.企业品牌知名度
    3.企业自身技术开发能力
    4.企业产品质量
    5.企业自身的行业经验和人才水平
    6.企业的融资能力
    7.企业的管理水平
    8.企业自身的产品系列宽度
    9.企业生产线技术水平
    10.企业的渠道能力

    内部要素—企业竞争力要素
    当企业占领了市场,又需要保持足够的竞争力,因为不同行业入行门槛的条件参差不齐,所以为了保住企业自身的市场,必须要保持足够的竞争力才能够取得长足的发展,在竞争力方面,我们需要注意的部分竞争力要素如下:
    1.市场增长率
    2.市场规模
    3.盈利性
    4.竞争对手强弱
    5.进入市场门槛高低
    6.市场容量大小
    7.政治经济文化法律技术等环境
    8.通货膨胀
    9.人才的可获得性
    10.行业的持续发展能力

    参考:
    《数据分析模型篇—麦肯锡矩阵(GE矩阵)》 CSDN博客 小白数据营 2019.09
    《如何将波特五力模型和PEST分析法融入SWOT分析法里面?》 知乎 2019.11
    《数据分析一定要懂的分析模型——波士顿矩阵》 知乎 帆软 2019.05
    《麦肯锡会用波士顿矩阵吗?》 知乎 2019.03

    展开全文
  • 链接分析

    千次阅读 2013-04-12 15:45:10
    1. 链接分析   搜索引擎在查找能够满足用户请求的网页时,主要考虑两方面的因素:  网页和查询的相关性:是用户发出的查询与网页内容的内容相似性得分。  网页的重要性:通过链接分析方法计算获得的...

    1. 链接分析 

          搜索引擎在查找能够满足用户请求的网页时,主要考虑两方面的因素:

            网页和查询的相关性:是用户发出的查询与网页内容的内容相似性得分。

            网页的重要性:通过链接分析方法计算获得的得分。

            搜索引擎融合两者,共同拟合出相似性评分函数,来对搜索结果进行排序。

            常见的链接分析算法除了鼎鼎有名的PageRank,还有HITS、SALSA、Hilltop以及主题PageRank等等。需要重点理解的是PageRank和HITS,后面这些算法都是以它们为基础的。

            绝大部分链接分析算法建立在两个概念模型,它们是:

            随机游走模型:针对浏览网页用户行为建立的抽象概念模型,用户上网过程中会不断打开链接,在相互有链接指向的网页之间跳转,这是直接跳转,如果某个页面包含的所有链接用户都不感兴趣则可能会在浏览器中输入另外的网址,这是远程跳转。该模型就是对一个直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型;典型的使用该模型的算法是PageRank
            子集传播模型:基本思想是把互联网网页按照一定规则划分,分为两个甚至是多个子集合。其中某个子集合具有特殊性质,很多算法从这个具有特殊性质的子集合出发,给予子集合内网页初始权值,之后根据这个特殊子集合内网页和其他网页的链接关系,按照一定方式将权值传递到其他网页。典型的使用该模型的算法有HITS和Hilltop算法

     

    2. 链接分析算法之间的关系: 


              

                                             图1 链接分析算法关系图:

              链接算法很多,但是从其概念模型来说,基本遵循上述小节介绍的随机游走模型和子集传播模型。而从图1中可看出,在众多算法中,PageRank和HITS算法可以说是最重要的两个具有代表性的链接分析算法,后续的很多链接分析算法都是在这两个算法基础上衍生出来的改进算法。


    1. PageRank

    1. PageRank算法概述

             PageRank,网页排名,又称网页级别Google左侧排名佩奇排名。

            是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法,自从Google在商业上获得空前的成功后,该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升,从而提高搜索结果的相关性和质量。其级别从0到10级,10级为满分。PR值越高说明该网页越受欢迎(越重要)。例如:一个PR值为1的网站表明这个网站不太具有流行度,而PR值为7到10则表明这个网站非常受欢迎(或者说极其重要)。一般PR值达到4,就算是一个不错的网站了。Google把自己的网站的PR值定到10,这说明Google这个网站是非常受欢迎的,也可以说这个网站非常重要。

     

    2. 从入链数量到 PageRank

            在PageRank提出之前,已经有研究者提出利用网页的入链数量来进行链接分析计算,这种入链方法假设一个网页的入链越多,则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法,对于搜索引擎效果提升也有较明显的效果。 PageRank除了考虑到入链数量的影响,还参考了网页质量因素,两者相结合获得了更好的网页重要性评价标准。
    对于某个互联网网页A来说,该网页PageRank的计算基于以下两个基本假设: 
         数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要。
         质量假设指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A,则页面A越重要。
           利用以上两个假设,PageRank算法刚开始赋予每个网页相同的重要性得分,通过迭代递归计算来更新每个页面节点的PageRank得分,直到得分稳定为止。 PageRank计算得出的结果是网页的重要性评价,这和用户输入的查询是没有任何关系的,即算法是主题无关的。假设有一个搜索引擎,其相似度计算函数不考虑内容相似因素,完全采用PageRank来进行排序,那么这个搜索引擎的表现是什么样子的呢?这个搜索引擎对于任意不同的查询请求,返回的结果都是相同的,即返回PageRank值最高的页面。

     

    3. PageRank算法原理

          PageRank的计算充分利用了两个假设:数量假设质量假设。步骤如下:
          1)在初始阶段网页通过链接关系构建起Web图,每个页面设置相同的PageRank值,通过若干轮的计算,会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行,网页当前的PageRank值会不断得到更新。

          2)在一轮中更新页面PageRank得分的计算方法:在一轮更新页面PageRank得分的计算中,每个页面将其当前的PageRank值平均分配到本页面包含的出链上,这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值,就完成了一轮PageRank计算。 

     

    3.2 基本思想:

           如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/L(T)

         其中PR(T)为T的PageRank值,L(T)为T的出链数

            则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

            即一个页面的得票数由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

    3.3 PageRank简单计算:

           假设一个由只有4个页面组成的集合:A,B,C和D。如果所有页面都链向A,那么A的PR(PageRank)值将是B,C及D的和。

           

           继续假设B也有链接到C,并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑,D投出的票只有三分之一算到了A的PageRank上。

           

          换句话说,根据链出总数平分一个页面的PR值。

           

    例子:

            如图1 所示的例子来说明PageRank的具体计算过程。  

                               

           

     

    3.4  修正PageRank计算公式:

             由于存在一些出链为0,也就是那些不链接任何其他网页的网, 也称为孤立网页,使得很多网页能被访问到。因此需要对 PageRank公式进行修正,即在简单公式的基础上增加了阻尼系数(damping factor)q, q一般取值q=0.85。

          其意义是,在任意时刻,用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击,随机跳到新URL的概率)的算法被用到了所有页面上,估算页面可能被上网者放入书签的概率。

          最后,即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法,没有页面的PageRank会是0。所以,Google通过数学系统给了每个页面一个最小值。

          

         这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定义的公式。

         所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值(非0),那么经过不断的重复计算,这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。

     

    4. PageRank幂法计算(线性代数应用)

    4.1 完整公式:

    关于这节内容,可以查阅:谷歌背后的数学

    首先求完整的公式:

    Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准确的表达为:

     

    是被研究的页面,链入页面的数量,链出页面的数量,而N是所有页面的数量。

    PageRank值是一个特殊矩阵中的特征向量。这个特征向量为:

     

    R是如下等式的一个解:

    如果网页i有指向网页j的一个链接,则

    否则=0。

    4.2 使用幂法求PageRank

          那我们PageRank 公式可以转换为求解的值,

          其中矩阵为 A = q  × P + ( 1 一 q) *  /N 。 P 为概率转移矩阵,为 n  维的全 1 行. 则 =

          

         幂法计算过程如下:
          X  设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1.

         R = AX;

         while  (1 )(

                if ( l X - R I  <  ) { //如果最后两次的结果近似或者相同,返回R

                      return R;

               }    else   {

                    X =R;

                   R = AX;

             }

        }

    4.3 求解步骤:

    一、 P概率转移矩阵的计算过程:

            先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。

          1) 首先我们使用图的形式来表述网页之间关系:

           现在假设只有四张网页集合:A、B、C,其抽象结构如下图1:

            

                                         图1 网页间的链接关系

          显然这个图是强连通的(从任一节点出发都可以到达另外任何一个节点)。

          2)我们用矩阵表示连通图:

           用邻接矩阵 P表示这个图中顶点关系 ,如果顶(页面)i向顶点(页面)j有链接情况 ,则pij   =   1 ,否则pij   =   0 。如图2所示。如果网页文件总数为N , 那么这个网页链接矩阵就是一个N x N  的矩 阵 。 

          3)网页链接概率矩阵

           然后将每一行除以该行非零数字之和,即(每行非0数之和就是链接网个数)则得到新矩阵P’,如图3所示。 这个矩阵记录了 每个网页跳转到其他网页的概率,即其中i行j列的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C,所以一个用户从A跳转到B、C的概率各为1/2。

          4)概率转移矩阵P

           采用P’ 的转置矩 阵进行计算, 也就是上面提到的概率转移矩阵P 。  如图4所示:

         

               
             图2  网页链接矩阵:                                      图3  网页链接概率矩阵:  
     
     

                             图4  P’ 的转置矩 阵

     

    二、 A矩阵计算过程。


          1)P概率转移矩阵  :

           

          2)/N 为:

         

          3)A矩阵为:q  × P + ( 1 一 q) *  /N = 0.85  × P + 0.15  * /N

         

          初始每个网页的 PageRank值均为1 , 即X~t = ( 1 , 1 , 1 ) 。 

    三、 循环迭代计算PageRank的过程

           第一步:

           

              因为X 与R的差别较大。 继续迭代。

              第二步:

               

           继续迭代这个过程...

          直到最后两次的结果近似或者相同,即R最终收敛,R 约等于X,此时计算停止。最终的R 就是各个页面的 PageRank 值。

    用幂法计算PageRank 值总是收敛的,即计算的次数是有限的。

     

          Larry Page和Sergey Brin 两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。

          由于互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页,那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘,计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧,大大的简化了计算量。

     

    5. PageRank算法优缺点

    优点

            是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。

    缺点:

           1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低

            2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接,除非它是某个站点的子站点。

     

     

     参考文献:

    维基百科http://en.wikipedia.org/wiki/Page_rank

    PageRank算法的分析及实现

    《这就是搜索引擎:核心技术详解》


    2.主题敏感PageRank

    前面的讨论提到。PageRank忽略了主题相关性,导致结果的相关性和主题性降低,对于不同的用户,甚至有很大的差别。例如,当搜索“苹果”时,一个数码爱好者可能是想要看 iphone 的信息,一个果农可能是想看苹果的价格走势和种植技巧,而一个小朋友可能在找苹果的简笔画。理想情况下,应该为每个用户维护一套专用向量,但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为主题敏感PageRank(Topic-Sensitive PageRank )的折中方案。主题敏感PageRank的做法是预定义几个话题类别,例如体育、娱乐、科技等等,为每个话题单独维护一个向量,然后想办法关联用户的话题倾向,根据用户的话题倾向排序结果。

          主题敏感PageRankPageRank算法的改进版本,该算法已被Google使用在个性化搜索服务中。

    1. 基本思想

    基本思想:

           通过离线计算出一个与某一主题相关的PageRank向量集合,即计算某个页面关于不同主题的得分。主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定(即在线相似度的计算)。 

    2. 主题敏感PageRank计算流程

    1、确定话题分类

               主题敏感PageRank参考ODP网站(www.dmoz.org),定义了16个大的主题类别,包括体育、商业、科技等。ODP(Open Directory Project)是人工整理的多层级网页分类导航站点(参见图1),在顶级的16个大分类下还有更细致的小

                       

         

                                                                       图1  ODP首页

    粒度分类结构,在最底层目录下,人工收集了符合该目录主题的精选高质量网页地址,以供互联网用户导航寻址。主题敏感PageRank采用了ODP最高级别的16个分类类别作为事先定义的主题类型。 

    2、网页topic 归属

           这一步需要将每个页面归入最合适的分类,具体归类有很多算法,例如可以使用 TF-IDF 基于词素归类,也可以聚类后人工归类。这一步最终的结果是每个网页被归到其中一个 topic。

    3、分topic 向量计算

          在PageRank的向量迭代公式:

             

            

         即R = q  × P * R + ( 1 一 q) * e/N  (e单位向量)

         而在主题敏感PageRank中,向量迭代公式为:

           

              首先是单位向量e变为了s。

              而s是这样一个向量:对于某 topic 的s,如果网页k在此 topic 中,则s中第k个元素为1,否则为0。注意对于每一个 topic 都有一个不同的s。而|s |表示s中 1 的数量。

            假设有页面A,B,C, D,假设页面A归为 Arts,B归为 Computers,C归为 Computers,D归为 Sports。那么对于 Computers 这个 topic,s就是:

               

         假设我们设置阻尼系数q=0.8, 而|s|=2, 因此,迭代公式为:

           

           最后算出的向量就是 Computers 这个 topic 的 rank。如果实际计算一下,会发现B、C页在这个 topic 下的权重相比上面非 Topic-Sensitive 的 rank 会升高,这说明如果用户是一个倾向于 Computers topic 的人(例如程序员),那么在给他呈现的结果中B、C会更重要,因此可能排名更靠前。

    4. 在线相似度计算

            最后一步就是在用户提交搜索时,确定用户的 topic 倾向,以选择合适的 rank 向量。主要方法有两种:

           一种是列出所有 topic 让用户自己选择感兴趣的项目,这种方法在一些社交问答网站注册时经常使用;

           另外一种方法利用“用户查询分类器”对查询进行分类,即搜索引擎会通过某种手段(如 cookie 跟踪)跟踪用户的行为,进行数据分析判断用户的倾向。

           如2,假设用户输入了查询请求“乔丹”,查询词“乔丹”隶属于体育类别的概率为0.6,娱乐类别的概率为0.1,商业类别的概率为0.3                                              


                                                2 在线相似度计算

           在进行上述用户查询分类计算的同时,搜索系统读取索引,找出包含了用户查询“乔丹”的所有网页,并获得已计算好的各个分类主题的PageRank值,在图6-21的例子里,假设某个网页A的各个主题PageRank值分别为体育0.2,娱乐0.3以及商业0.1

          得到用户查询的类别向量和某个网页的主题PageRank向量后,即可计算这个网页和查询的相似度。通过计算两个向量的乘积就可以得出两者之间的相关性。在图6-21的例子里,网页A和用户查询“乔丹”的相似度为:

    Sim(“乔丹”,A)= 0.6*0.2+0.1*0.3+0.3*0.1=0.18

          对包含“乔丹”这个关键词的网页,都根据以上方法计算,得出其与用户查询的相似度后,就可以按照相似度由高到低排序输出,作为本次搜索的搜索结果返回给用户。

    3. 利用主题敏感PageRank构造个性化搜索    

           以上内容介绍的是主题敏感PageRank的基本思想和计算流程,从其内在机制来说,这个算法非常适合作为个性化搜索的技术方案。

        在图2所示例子里,计算相似度使用的只有用户当前输入的查询词“乔丹”,如果能够对此进行扩展,即不仅仅使用当前查询词,也考虑利用用户过去的搜索记录等个性化信息。比如用户之前搜索过“耐克”,则可以推断用户输入“乔丹”是想购买运动服饰,而如果之前搜索过“姚明”,则很可能用户希望获得体育方面的信息。通过这种方式,可以将用户的个性化信息和当前查询相融合来构造搜索系统,以此达到个性化搜索的目的,更精准的提供搜索服务。

    4. 主题敏感PageRank与PageRank的差异 

          PageRank算法基本遵循前面章节提到的“随机游走模型”,即用户在浏览某个网页时,如果希望跳转到其它页面,则随机选择本网页包含的某个链接,进入另外一个页面。主题敏感PageRank则对该概念模型做出改进,引入了更符合现实的假设。一般来说用户会对某些领域感兴趣,同时,当浏览某个页面时,这个页面也是与某个主题相关的(比如体育报道或者娱乐新闻),所以,当用户看完当前页面,希望跳转时,更倾向于点击和当前页面主题类似的链接,即主题敏感PageRank是将用户兴趣、页面主题以及链接所指向网页与当前网页主题的相似程度综合考虑而建立的模型。很明显,这更符合真实用户的浏览过程。

         PageRank是全局性的网页重要性衡量标准,每个网页会根据链接情况,被赋予一个唯一的PageRank分值。主题敏感PageRank在此点有所不同,该算法引入16种主题类型,对于某个网页来说,对应某个主题类型都有相应的PageRank分值,即每个网页会被赋予16个主题相关PageRank分值。

         在接受到用户查询后,两个算法在处理方式上也有较大差异。PageRank算法与查询无关,只能作为相似度计算的一个计算因子体现作用,无法独立使用。而主题敏感PageRank是查询相关的,可单独作为相似度计算公式使用。而且,在接收到用户查询后,主题敏感PageRank还需要利用分类器,计算该查询隶属于事先定义好的16个主题的隶属度,并在相似度计算时的排序公式中利用此信息。


    3.HITS

    HITS(HITS(Hyperlink - Induced Topic Search) ) 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。

        HITS算法是链接分析中非常基础且重要的算法,目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用。


    1. Hub页面与Authority页面

          Hub页面(枢纽页面)和Authority页面(权威页面)是HITS算法最基本的两个定义

        所谓“Authority”页面,是指与某个领域或者某个话题相关的高质量网页,比如搜索引擎领域,Google和百度首页即该领域的高质量网页,比如视频领域,优酷和土豆首页即该领域的高质量网页。

        所谓“Hub”页面,指的是包含了很多指向高质量“Authority”页面链接的网页,比如hao123首页可以认为是一个典型的高质量“Hub”网页。

        图1给出了一个“Hub”页面实例,这个网页是斯坦福大学计算语言学研究组维护的页面,这个网页收集了与统计自然语言处理相关的高质量资源,包括一些著名的开源软件包及语料库等,并通过链接的方式指向这些资源页面。这个页面可以认为是“自然语言处理”这个领域的“Hub”页面,相应的,被这个页面指向的资源页面,大部分是高质量的“Authority”页面。

              

                     图1 自然语言处理领域的Hub页面

     

         HITS算法的目的即是通过一定的技术手段,在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面,尤其是“Authority”页面,因为这些页面代表了能够满足用户查询的高质量内容,搜索引擎以此作为搜索结果返回给用户。

    2. 算法基本思想:相互增强关系

         基本假设1:一个好的“Authority”页面会被很多好的“Hub”页面指向;

         基本假设2:一个好的“Hub”页面会指向很多好的“Authority”页面;

    3. HITS算法

    具体算法:可利用上面提到的两个基本假设,以及相互增强关系等原则进行多轮迭代计算,每轮迭代计算更新每个页面的两个权值,直到权值稳定不再发生明显的变化为止。

    步骤:

    3.1 根集合

          1)将查询q提交给基于关键字查询的检索系统,从返回结果页面的集合总取前n个网页(如n=200),作为根集合(root set)记为root,则root满足:

      1).root中的网页数量较少

      2).root中的网页是与查询q相关的网页

      3).root中的网页包含较多的权威(Authority)网页

           这个集合是个有向图结构:

    3.2 扩展集合base

            在根集root的基础上,HITS算法对网页集合进行扩充(参考图2)集合base,扩充原则是:凡是与根集内网页有直接链接指向关系的网页都被扩充到集合base,无论是有链接指向根集内页面也好,或者是根集页面有链接指向的页面也好,都被扩充进入扩展网页集合base。HITS算法在这个扩充网页集合内寻找好的“Hub”页面与好的“Authority”页面。

                                                                  

     

                                                           图2 根集与扩展集

     

     3.3 计算扩展集base中所有页面的Hub值(枢纽度)和Authority值(权威度)

            1)  分别表示网页结点 i 的Authority值(权威度)和Hub值(中心度)。

           2) 对于“扩展集base”来说,我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面,每个网页都有潜在的可能,所以对于每个页面都设立两个权值,分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下,在没有更多可利用信息前,每个页面的这两个权值都是相同的,可以都设置为1,即:

           

             3)每次迭代计算Hub权值和Authority权值:

               网页 a (i)在此轮迭代中的Authority权值即为所有指向网页 a (i)页面的Hub权值之和:

                a (i) = Σ h (i) ;

               网页 a (i)的Hub分值即为所指向的页面的Authority权值之和:

               h (i) = Σ a (i) 。

               对a (i)、h (i)进行规范化处理:

               将所有网页的中心度都除以最高中心度以将其标准化:

               a (i) = a (i)/|a(i)| ;

               将所有网页的权威度都除以最高权威度以将其标准化:

               h (i) = h (i)/ |h(i)| :

              
             5)如此不断的重复第4):上一轮迭代计算中的权值和本轮迭代之后权值的差异,如果发现总体来说权值没有明显变化,说明系统已进入稳定状态,则可以结束计算,即a ( u),h(v)收敛 。

           算法描述:

                 

     

           如图3所示,给出了迭代计算过程中,某个页面的Hub权值和Authority权值的更新方式。假设以A(i)代表网页i的Authority权值,以H(i)代表网页i的Hub权值。在图6-14的例子中,“扩充网页集合”有3个网页有链接指向页面1,同时页面1有3个链接指向其它页面。那么,网页1在此轮迭代中的Authority权值即为所有指向网页1页面的Hub权值之和;类似的,网页1的Hub分值即为所指向的页面的Authority权值之和。

                                                      

                                                                    图3 Hub与Authority权值计算

     

     3.4  输出排序结果

          将页面根据Authority权值得分由高到低排序,取权值最高的若干页面作为响应用户查询的搜索结果输出。

    4. HITS算法存在的问题

            HITS算法整体而言是个效果很好的算法,目前不仅应用在搜索引擎领域,而且被“自然语言处理”以及“社交分析”等很多其它计算机领域借鉴使用,并取得了很好的应用效果。尽管如此,最初版本的HITS算法仍然存在一些问题,而后续很多基于HITS算法的链接分析方法,也是立足于改进HITS算法存在的这些问题而提出的。

        归纳起来,HITS算法主要在以下几个方面存在不足:

        1.计算效率较低

            因为HITS算法是与查询相关的算法,所以必须在接收到用户查询后实时进行计算,而HITS算法本身需要进行很多轮迭代计算才能获得最终结果,这导致其计算效率较低,这是实际应用时必须慎重考虑的问题。

       2.主题漂移问题

            如果在扩展网页集合里包含部分与查询主题无关的页面,而且这些页面之间有较多的相互链接指向,那么使用HITS算法很可能会给予这些无关网页很高的排名,导致搜索结果发生主题漂移,这种现象被称为“紧密链接社区现象”(Tightly-Knit CommunityEffect)。

       3.易被作弊者操纵结果

            HITS从机制上很容易被作弊者操纵,比如作弊者可以建立一个网页,页面内容增加很多指向高质量网页或者著名网站的网址,这就是一个很好的Hub页面,之后作弊者再将这个网页链接指向作弊网页,于是可以提升作弊网页的Authority得分。

       4.结构不稳定

            所谓结构不稳定,就是说在原有的“扩充网页集合”内,如果添加删除个别网页或者改变少数链接关系,则HITS算法的排名结果就会有非常大的改变。

    5. HITS算法与PageRank算法比较

         HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出,两者无论是在基本概念模型还是计算思路以及技术实现细节都有很大的不同,下面对两者之间的差异进行逐一说明。      

        1.HITS算法是与用户输入的查询请求密切相关的,而PageRank与查询请求无关。所以,HITS算法可以单独作为相似性计算评价标准,而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价;

        2.HITS算法因为与用户查询密切相关,所以必须在接收到用户查询后实时进行计算,计算效率较低;而PageRank则可以在爬虫抓取完成后离线计算,在线直接使用计算结果,计算效率较高;

        3.HITS算法的计算对象数量较少,只需计算扩展集合内网页之间的链接关系;而PageRank是全局性算法,对所有互联网页面节点进行处理;

        4.从两者的计算效率和处理对象集合大小来比较,PageRank更适合部署在服务器端,而HITS算法更适合部署在客户端;

        5.HITS算法存在主题泛化问题,所以更适合处理具体化的用户查询;而PageRank在处理宽泛的用户查询时更有优势;

        6.HITS算法在计算时,对于每个页面需要计算两个分值,而PageRank只需计算一个分值即可;在搜索引擎领域,更重视HITS算法计算出的Authority权值,但是在很多应用HITS算法的其它领域,Hub分值也有很重要的作用;

        7.从链接反作弊的角度来说,PageRank从机制上优于HITS算法,而HITS算法更易遭受链接作弊的影响。

        8.HITS算法结构不稳定,当对“扩充网页集合”内链接关系作出很小改变,则对最终排名有很大影响;而PageRank相对HITS而言表现稳定,其根本原因在于PageRank计算时的“远程跳转”。


    4.SLLSA

       SALSA算法的初衷希望能够结合PageRank和HITS算法两者的主要特点,既可以利用HITS算法与查询相关的特点,也可以采纳PageRank的“随机游走模型”,这是SALSA算法提出的背景。由此可见,SALSA算法融合了PageRank和HITS算法的基本思想,从实际效果来说,很多实验数据表明,SALSA的搜索效果也都优于前两个算法,是目前效果最好的链接分析算法之一。

            从整体计算流程来说,可以将SALSA划分为两个大的阶段:首先是确定计算对象集合的阶段,这一阶段与HITS算法基本相同;第二个阶段是链接关系传播过程,在这一阶段则采纳了“随机游走模型”。

    1. 确定计算对象集合

            PageRank的计算对象是互联网所有网页,SALSA算法与此不同,在本阶段,其与HITS算法思路大致相同,也是先得到“扩充网页集合”,之后将网页关系转换为二分图形式。

            扩充网页集合

            SALSA算法在接收到用户查询请求后,利用现有搜索引擎或者检索系统,获得一批与用户查询在内容上高度相关的网页,以此作为“根集”。并在此基础上,将与“根集”内网页有直接链接关系的网页纳入,形成“扩充网页集合”(参考图6.4.3-1)。之后会在“扩充网页集合”内根据一定链接分析方法获得最终搜索结果排名。

            转换为无向二分图

            在获得了“扩充网页集合”之后,SALSA根据集合内的网页链接关系,将网页集合转换为一个二分图。即将网页划分到两个子集合中,一个子集合是Hub集合,另外一个子集合是Authority集合。划分网页节点属于哪个集合,则根据如下规则:

    如果一个网页包含出链,这些出链指向“扩充网页集合”内其它节点,则这个网页可被归入Hub集合;

    如果一个网页包含“扩充网页集合”内其它节点指向的入链,则可被归入Authority集合。

            由以上规则可以看出,如果某个网页同时包含入链和出链,则可以同时归入两个集合。同时,Hub集合内网页的出链组成了二分图内的边,根据以上法则,将“扩充网页集合”转换为二分图。

            图6-15和图6-16给出了一个示例,说明了这个转换过程。假设“扩充网页集合”如图6-15所示,由6个网页构成,其链接关系如图所示,同时为便于说明,每个网页给予一个唯一编号。图6-16则是将图6-15中的网页集合转换为二分图的结果。以网页6为例,因为其有出链指向网页节点3和网页节点5,所以可以放入Hub集合,也因为编号为1、3、10的网页节点有链接指向网页节点6,所以也可以放入Authority集合中。网页节点6的两个出链保留,作为二分图的边,

                      

                                                 图6-15 扩充网页集合示例

     

            但是这里需要注意的是,在转换为二分图后,原先的有向边不再保留方向,转换为无向边,而HITS算法仍然保留为有向边,这点与SALSA略有不同。

                           

                                                     图6-16   二分图

             到这一步骤为止,除了SALSA将“扩充网页集合”转换为无向二分图,而HITS仍然是有向二分图外,其它步骤和流程,SALSA算法与HITS算法完全相同,正因此,SALSA保证了是与用户查询相关的链接分析算法。

    2. 链接关系传播

             在链接关系传播阶段,SALSA放弃了HITS算法的Hub节点和Authority节点相互增强的假设,转而采纳PageRank的“随机游走模型”。

    链接关系传播概念模型

            如图6-16所示,假设存在某个浏览者,从某个子集合中随机选择一个节点出发(为方便说明,图中所示为从Hub子集的节点1出发,实际计算往往是从Authority子集出发),如果节点包含多条边,则以相等概率随机选择一条边,从Hub子集跳跃到Authority集合内节点,图中所示为由节点1转移到节点3,之后从Authority子集再次跳回Hub子集,即由节点3跳到节点6。如此不断在两个子集之间转移,形成了SALSA自身的链接关系传播模式。

             尽管看上去与PageRank的链接传播模式不同,其实两者是一样的,关键点在于:其从某个节点跳跃到另外一个节点的时候,如果包含多个可供选择的链接,则以等概率随机选择一条路径,即在权值传播过程中,权值是被所有链接平均分配的。而HITS算法不同,HITS算法属于权值广播模式,即将节点本身的权值完全传播给有链接指向的节点,并不根据链接多少进行分配。

        SALSA的上述权值传播模型与HITS模型关注重点不同,HITS模型关注的是Hub和Authority之间的节点相互增强关系,而SALSA实际上关注的是Hub-Hub以及Authority-Authority之间的节点关系,而另外一个子集合节点只是充当中转桥梁的作用。所以,上述权值传播模型可以转化为两个相似的子模型,即Hub节点关系图和Authority节点关系图。

     

    Authority节点关系图

              图6-17是由6-16的二分图转化成的“Authority节点关系图”,“Hub节点关系图”与此类似,两者转化过程是相似的,我们以“Authority节点关系图”为例来看如何从二分图转化为节点关系图。

                              

                                                                      图6-17  Authority节点关系图

     

            这里需要注意的是:Authority集合内从某个节点i转移到另外一个节点j的概率,与从节点j转移到节点i的概率是不同的,即非对称的,所以转换后的Authority节点关系图是个有向图,以此来表示其转移概率之间的差异。

           对于图6-17这个“Authority节点关系图”来说,图中包含的节点就是二分图中属于Authority子集的节点,关键在于节点之间的边如何建立以及节点之间转移概率如何计算。

     

    节点关系图中边的建立

           之所以在“Authority节点图”中,节点3有边指向节点5,是因为在二分图中,由节点3通过Hub子集的节点6中转,可以通达节点5,所以两者之间有边建立。

           这里需要注意的是:在二分图中,对于Authority集合内某个节点来说,一定可以通过Hub子集的节点中转后再次返回本身,所以一定包含一条指向自身的有向边。节点1因为只有中转节点2使得其返回Authority子集中自身节点,所以只有指向自身的一条边,和其它节点没有边联系,所以例子中的“Authority节点关系图”由两个连通子图构成,一个只有节点1,另外一个连通子图由剩余几个节点构成。

     

    节点之间的转移概率

            至于为何“Authority节点关系图”中,节点3到节点5的转移概率为0.25,是因为前面介绍过,SALSA的权值传播模型遵循“随机游走模型”。在图6-16的二分图中,从节点3转移到节点5的过程中,节点3有两条边可做选择来跳转到Hub子集,所以每条边的选择概率为1/2,可以选择其中一条边到达节点6,同样,从节点6跳回到Authority子集时,节点6也有两条边可选,选中每条边的概率为1/2。所以从节点3出发,经由节点6跳转到节点5的概率为两条边权值的乘积,即为1/4。

           对于指向自身的有向边,其权重计算过程是类似的,我们仍然以节点3为例,指向自身的有向边代表从Authority子集中节点3出发,经由Hub子集的节点再次返回节点3的概率。从6-16的二分图可以看出,完成这个过程有两条路径可走,一条是从节点3到节点1返回;另外一条是从节点3经由节点6后返回;每一条路径的概率与上面所述计算方法一样,因为两条路径各自的概率为0.25,所以节点3返回自身的概率为两条路径概率之和,即为0.5。图中其它边的转移概率计算方式也是类此。

           建立好“Authority节点关系图”后,即可在图上利用“随机游走模型”来计算每个节点的Authority权值。在实际计算过程中,SALSA将搜索结果排序问题进一步转换为求Authority节点矩阵的主秩问题,矩阵的主秩即为每个节点的相应Authority得分,按照Authority得分由高到低排列,即可得到最终的搜索排序结果。

     

    3. Authority权值计算

     

                              

                                                          图6-18  SALSA节点权值计算公式

     

              经过数学推导,可以得出SALSA与求矩阵主秩等价的Authority权值计算公式。图6-18示意图表明了SALSA算法中某个网页节点的Authority权值是如何计算的。如图右上角公式所示,决定某个网页i的Authority权值涉及到4个因子:

             Authority子集中包含的节点总数|A|。其实这个因子对于Authority集合中任意节点来说都是相同的,所以对于最终的根据节点Authority权值进行排序没有影响,只是起到保证权值得分在0到1之间,能够以概率形式表示权值的作用;

            网页i所在连通图中包含的节点个数|Aj|。网页所在的连通图包含的节点个数越多,则网页的Authority权值越大;

            网页i所在连通图中包含的入链总数|Ej|。网页所在的连通图包含的入链总数越少,则网页的Authority权值越大;

            网页i的入链个数|Bi|。节点入链越多,则Authority权值越大,这个因子是唯一一个和节点本身属性相关的。由此可见,SALSA权值计算和节点入链个数成正比。

             之前图6-17的“Authority节点关系图”由两个连通子图组成,一个由唯一的节点1构成,另外一个由节点3、5、6三个节点构成,两个连通子图在图6-18中也被分别圈出。

             我们以节点3为例,看其对应的四个计算因素取值:

    Authority子集共包括4个节点;

    节点3所在连通图包含3个节点;

    节点3所在连通图共有6个入链;

    节点3的入链个数为2;

             所以,节点3的Authority权值为:(3/4)*(2/6)=0.25。其它节点权值的计算过程与此类似。SALSA根据节点的Authority权值由高到低排序输出,即为搜索结果。

             由上述权值计算公式可以推论出:如果整个Authority子集所有节点形成一个完整的连通图,那么在计算authority权值过程中,对于任意两个节点,4个因子中除了节点入链个数外,其它三个因子总是相同,即只有入链个数起作用,此时,SALSA算法退化为根据节点入链个数决定排序顺序的算法。

              从SALSA计算Authority得分过程中可看出,SALSA算法不需像HITS算法一样进行不断迭代计算,所以从计算效率角度看要快于HITS算法。另外,SALSA算法解决了HITS算法的计算结果主题漂移的问题,所以搜索质量也优于HITS算法。SALSA算法是目前效果最好的链接算法之一。

     参考文献:

    《这就是搜索引擎:核心技术详解》

    4. Hilltop

    Hilltop算法是由Krishna Baharat 在2000年左右研究的,于2001年申请专利,但是有很多人以为Hilltop算法是由谷歌研究的。只不过是Krishna Baharat 后来加入了Google成为了一名核心工程师,然后授权给Google使用的。 

            在与PageRank算法相比之下,Google意识到这个算法的进步会为他们的搜索排名带来非常重要的功能。Google的HillTop算法现在已经能更好的与旧的算法(PR算法)联合起来工作。根据观察HillTop算法比起它在2000年刚设计的时候已经有了很大的进步。显然这也是2003年11月16日“佛罗里达”更新中影响的一个最主要的算法。     

           

    1. Hilltop算法基本思想

           Hilltop融合了HITS和PageRank两个算法的基本思想:

           一方面,Hilltop是与用户查询请求相关的链接分析算法,吸收了HITS算法根据用户查询获得高质量相关网页子集的思想,即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高.符合“子集传播模型”,是该模型的一个具体实例;

          另一方面,在权值传播过程中,Hilltop也采纳了PageRank的基本指导思想,即通过页面入链的数量和质量来确定搜索结果的排序权重。

     

    2. Hilltop算法的一些基本定义

      非从属组织页面   

        “非从属组织页面”(Non-affiliated Pages)是Hilltop算法的一个很重要的定义。要了解什么是非从属组织页面,先要搞明白什么是“从属组织网站”,所谓“从属组织网站”,即不同的网站属于同一机构或者其拥有者有密切关联。具体而言,满足如下任意一条判断规则的网站会被认为是从属网站:

          条件1:主机IP地址的前三个子网段相同,比如:IP地址分别为159.226.138.127和159.226.138.234的两个网站会被认为是从属网站。

          条件2:如果网站域名中的主域名相同,比如:www.ibm.com和www.ibm.com.cn会被认为是从属组织网站。 

         “非从属组织页面”的含义是:如果两个页面不属于从属网站,则为非从属组织页面。图6-22是相关示意图,从图中可以看出,页面2和页面3同属于IBM的网页,所以是“从属组织页面”,而页面1和页面5、页面3和页面6都是“非从属组织页面”。由此也可看出,“非从属组织页面”代表的是页面的一种关系,单个一个页面是无所谓从属或者非从属组织页面的。

         

                               图6-22 “从属组织页面”与“非从属组织页面”

    专家页面:

          “专家页面”(Export Sources)是Hilltop算法的另外一个重要定义。所谓“专家页面”,即与某个主题相关的高质量页面,同时需要满足以下要求:这些页面的链接所指向的页面相互之间都是“非从属组织页面”,且这些被指向的页面大多数是与“专家页面”主题相近的。

    目标页面集合:

         Hilltop算法将互联网页面划分为两类子集合,最重要的子集合是由专家页面构成的互联网页面子集,不在这个子集里的剩下的互联网页面作为另外一个集合,这个集合称作“目标页面集合”(Target Web Servers)。


    3. Hilltop算法

         图6-23是Hilltop算法的整体流程示意。

         1) 建立专家页面索引:首先从海量的互联网网页中通过一定规则筛选出“专家页面”子集合,并单独为这个页面集合建立索引。

         2)用户查询: Hilltop在接收到用户发出的某个查询请求时:

          首先) 根据用户查询的主题,从“专家页面”子集合中找出部分相关性最强的“专家页面”,并对每个专家页面计算相关性得分,

           然后)根据“目标页面”和这些“专家页面”的链接关系来对目标页面进行排序。基本思路遵循PageRank算法的链接数量假设和质量原则,将专家页面的得分通过链接关系传递给目标页面,并以此分数作为目标页面与用户查询相关性的排序得分。

           最后) 系统整合相关专家页面和得分较高的目标页面作为搜索结果返回给用户。

                                 

                                                                图6-23 Hilltop算法流程

          若在上述过程中,Hilltop无法得到一个足够大的专家页面集合,则返回搜索结果为空。由此可以看出,Hilltop算法更注重搜索结果的精度和准确性,不太考虑搜索结果是否足够多或者对大多数用户查询是否都有相应的搜索结果,所以很多用户发出的查询的搜索结果为空。这意味着Hilltop可以与某个排序算法相结合,以提高排序准确性,但并不适合作为一个独立的网页排序算法来使用。

    4. Hilltop算法流程

          从上述整体流程描述可看出,Hilltop算法主要包含两个步骤:专家页面搜索及目标页面排序。

    步骤一:专家页面搜索

             Hilltop算法从1亿4千万网页中,通过计算筛选出250万规模的互联网页面作为“专家页面”集合。“专家页面”的选择标准相对宽松,同时满足以下两个条件的页面即可进入“专家页面”集合:

             条件1:页面至少包含k个出链,这里的数量k可人为指定;

             条件2:k个出链指向的所有页面相互之间的关系都符合“非从属组织页面”的要求;

           当然,在此基础上,可以设定更严格的筛选条件,比如要求这些“专家页面”所包含链接指向的页面中,大部分所涉及的主题和专家页面的主题必须是一致或近似的。

           根据以上条件筛选出“专家页面”后,即可对“专家页面”单独建索引,在此过程中,索引系统只对页面中的“关键片段”(Key Phrase)进行索引。所谓“关键片段”,在Hilltop算法里包含了网页的三类信息:网页标题、H1标签内文字和URL锚文字。

           网页的“关键片段”可以支配(Qualify)某个区域内包含的所有链接,“支配”关系代表了一种管辖范围,不同的“关键片段”支配链接的区域范围不同,具体而言:

           页面标题可以支配页面内所有出现的链接,

           H1标签可以支配包围在<H1>和</H1>内的所有链接,

           URL锚文字只能支配本身唯一的链接。

           图6-24给出了“关键片段”对链接支配关系的示意图,在以“奥巴马访问中国”为标题的网页页面中,标题支配了所有这个页面出现的链接,而H1标签的管辖范围仅限于标签范围内出现的2个链接,对于锚文字“中国领导人”来说,其唯一能够支配的就是本身的这个链接。之所以定义这种支配关系,对于第二阶段将“专家页面”的分值传递到“目标页面”时候会起作用。

                                 

                                     图6-24 “关键片段”链接支配关系

            系统接收到用户查询Q,假设用户查询包含了多个单词,Hilltop如何对“专家页面”进行打分呢?对“专家页面”进行打分主要参考以下三类信息:

             1)“关键片段”包含了多少查询词,包含查询词越多,则分值越高,如果不包含任何查询词,则该“关键片段”不计分;

             2)“关键片段”本身的类型信息,网页标题权值最高,H1标签次之,再次是链接锚文字;

             3)用户查询和“关键片段”的失配率,即“关键片段”中不属于查询词的单词个数占“关键片段”总单词个数,这个值越小越好,越大则得分衰减越多;

           Hilltop综合考虑以上三类因素,拟合出打分函数来对“专家页面”是否与用户查询相关进行打分,选出相关性分值足够高的“专家页面”,以进行下一步骤操作,即对“目标页面”进行相关性计算。

    步骤二:目标页面排序

           Hilltop算法包含一个基本假设,即认为一个“目标页面”如果是满足用户查询的高质量搜索结果,其充分必要条件是该“目标页面”有高质量“专家页面”链接指向。然而,这个假设并不总是成立,比如有的“专家页面”的链接所指向的“目标页面”可能与用户查询并非密切相关。所以,Hilltop算法在这个阶段需要对“专家页面”的出链仔细进行甄别,以保证选出那些和查询密切相关的目标页面。

          Hilltop在本阶段是基于“专家页面”和“目标页面”之间的链接关系来进行的,在此基础上,将“专家页面”的得分传递给有链接关系的“目标页面”。传递分值之前,首先需要对链接关系进行整理,能够获得“专家页面”分值的“目标页面”需要满足以下两点要求:

         条件1:至少需要两个“专家页面”有链接指向“目标页面”,而且这两个专家页面不能是“从属组织页面”,即不能来自同一网站或相关网站。如果是“从属组织页面”,则只能保留一个链接,抛弃权值低的那个链接;

         条件2:“专家页面”和所指向的“目标页面”也需要符合一定要求,即这两个页面也不能是“从属组织页面”;

          在步骤一,给定用户查询,Hilltop算法已经获得相关的“专家页面”及其与查询的相关度得分,在此基础上,如何对“目标页面”的相关性打分?上面列出的条件1指出,能够获得传递分值的“目标页面”一定有多个“专家页面”链接指向,所以“目标页面”所获得的总传播分值是每个有链接指向的“专家页面”所传递分值之和。而计算其中某个“专家页面”传递给“目标页面”权值的时候是这么计算的:

            a. 找到“专家页面” 中那些能够支配目标页面的“关键片段”集合S;

            b. 统计S中包含用户查询词的“关键片段”个数T,T越大传递的权值越大;

            c.“专家页面”传递给“目标页面”的分值为:E*T,E为专家页面本身在第一阶段计算得到的相关得分,T为b步骤计算的分值,

         我们以图6-25的具体例子来说明。假设“专家页面”集合内存在一个网页P,其标题为:“奥巴马访问中国”,网页内容由一段<H1>标签文字和另外一个单独的链接锚文字组成。该页面包含三个出链,其中两个指向“目标页面集合”中的网页www.china.org,另外一个指向网页www.obama.org。出链对应的锚文字分别为:“奥巴马”,“中国”和“中国领导人”。

                            

                       

                                                              图6-25 Hilltop算法分值传递

           从图示的链接关系可以看出,网页P中能够支配www.china.org这个目标页面的“关键片段”集合包括:{中国领导人,中国,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}。而能够支配www.obamba.org目标页面的“关键片段”集合包括:{奥巴马,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}。

          接下来我们分析“专家页面”P在接收到查询时,是怎样将分值传递给与其有链接关系的“目标页面”的。假设系统接收到的查询请求为“奥巴马”,在接收到查询后,系统首先根据上述章节所述,找出“专家页面”并给予分值,而网页P是作为“专家页面”其中一个页面,并获得了相应的分值S,我们重点关注分值传播步骤。

         对于查询“奥巴马”来说,网页P中包含这个查询词的“关键片段”集合为:{奥巴马,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国},如上所述,这三个“关键片段”都能够支配www.obama.org页面,所以网页P传递给www.obamba.org的分值为S*3。而对于目标页面www.china.org来说,这三个“关键片段”中只有{<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}这两个能够支配目标页面,所以网页P传递给www.china.org的分值为S*2。

        对于包含多个查询词的用户请求,则每个查询词单独如上计算,将多个查询词的传递分值累加即可。

    5. Hilltop在应用中不足

          专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性;而专家页面的质量和公平性在一定程度上难以保证。 Hiltop忽略了大多数非专家页面的影响。

           在Hilltop的原型系统中,专家页面只占到整个页面的1.79%,不能全面反映民意。

           Hilltop算法在无法得到足够的专家页面子集时(少于两个专家页面),返回为空,即Hilltop适合于对查询排序进行求精,而不能覆盖。这意味着Hilltop可以与某个页面排序算法结合,提高精度,而不适合作为一个独立的页面排序算法。

           Hilltop存在与HITS算法类似的计算效率问题,因为根据查询主题从“专家页面”集合中选取主题相关的页面子集也是在线运行的,这与前面提到的HITS算法一样会影响查询响应时间。随着“专家页面”集合的增大,算法的可扩展性存在不足之处。


     参考文献:《这就是搜索引擎:核心技术详解》第六章



    展开全文
  • web链接分析算法

    千次阅读 2017-03-27 11:06:04
    由此可见,SALSA算法融合了PageRank和HITS算法的基本思想,从实际效果来说,很多实验数据表明,SALSA的搜索效果也都优于前两算法,是目前效果最好的链接分析算法之一。  从整体计算流程来说,可以将SALSA...

    转自:http://blog.csdn.net/hguisu/article/details/8005192

                http://blog.csdn.net/hguisu/article/details/8021036

                 http://blog.csdn.net/hguisu/article/details/8016916

                 http://blog.csdn.net/hguisu/article/details/8013489

    链接分析算法之:HITS算法

     HITS(HITS(Hyperlink - Induced Topic Search) ) 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。

        HITS算法是链接分析中非常基础且重要的算法,目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用。


    1. Hub页面与Authority页面

          Hub页面(枢纽页面)和Authority页面(权威页面)是HITS算法最基本的两个定义

        所谓“Authority”页面,是指与某个领域或者某个话题相关的高质量网页,比如搜索引擎领域,Google和百度首页即该领域的高质量网页,比如视频领域,优酷和土豆首页即该领域的高质量网页。

        所谓“Hub”页面,指的是包含了很多指向高质量“Authority”页面链接的网页,比如hao123首页可以认为是一个典型的高质量“Hub”网页。

        图1给出了一个“Hub”页面实例,这个网页是斯坦福大学计算语言学研究组维护的页面,这个网页收集了与统计自然语言处理相关的高质量资源,包括一些著名的开源软件包及语料库等,并通过链接的方式指向这些资源页面。这个页面可以认为是“自然语言处理”这个领域的“Hub”页面,相应的,被这个页面指向的资源页面,大部分是高质量的“Authority”页面。

              

                     图1 自然语言处理领域的Hub页面

     

         HITS算法的目的即是通过一定的技术手段,在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面,尤其是“Authority”页面,因为这些页面代表了能够满足用户查询的高质量内容,搜索引擎以此作为搜索结果返回给用户。

    2. 算法基本思想:相互增强关系

         基本假设1:一个好的“Authority”页面会被很多好的“Hub”页面指向;

         基本假设2:一个好的“Hub”页面会指向很多好的“Authority”页面;

    3. HITS算法

    具体算法:可利用上面提到的两个基本假设,以及相互增强关系等原则进行多轮迭代计算,每轮迭代计算更新每个页面的两个权值,直到权值稳定不再发生明显的变化为止。

    步骤:

    3.1 根集合

          1)将查询q提交给基于关键字查询的检索系统,从返回结果页面的集合总取前n个网页(如n=200),作为根集合(root set)记为root,则root满足:

      1).root中的网页数量较少

      2).root中的网页是与查询q相关的网页

      3).root中的网页包含较多的权威(Authority)网页

           这个集合是个有向图结构:

    3.2 扩展集合base

            在根集root的基础上,HITS算法对网页集合进行扩充(参考图2)集合base,扩充原则是:凡是与根集内网页有直接链接指向关系的网页都被扩充到集合base,无论是有链接指向根集内页面也好,或者是根集页面有链接指向的页面也好,都被扩充进入扩展网页集合base。HITS算法在这个扩充网页集合内寻找好的“Hub”页面与好的“Authority”页面。

                                                                  

     

                                                           图2 根集与扩展集

     

     3.3 计算扩展集base中所有页面的Hub值(枢纽度)和Authority值(权威度)

            1)  分别表示网页结点 i 的Authority值(权威度)和Hub值(中心度)。

           2) 对于“扩展集base”来说,我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面,每个网页都有潜在的可能,所以对于每个页面都设立两个权值,分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下,在没有更多可利用信息前,每个页面的这两个权值都是相同的,可以都设置为1,即:

           

             3)每次迭代计算Hub权值和Authority权值:

               网页 a (i)在此轮迭代中的Authority权值即为所有指向网页 a (i)页面的Hub权值之和:

                a (i) = Σ h (i) ;

               网页 a (i)的Hub分值即为所指向的页面的Authority权值之和:

               h (i) = Σ a (i) 。

               对a (i)、h (i)进行规范化处理:

               将所有网页的中心度都除以最高中心度以将其标准化:

               a (i) = a (i)/|a(i)| ;

               将所有网页的权威度都除以最高权威度以将其标准化:

               h (i) = h (i)/ |h(i)| :

              
             5)如此不断的重复第4):上一轮迭代计算中的权值和本轮迭代之后权值的差异,如果发现总体来说权值没有明显变化,说明系统已进入稳定状态,则可以结束计算,即a ( u),h(v)收敛 。

           算法描述:

                 

     

           如图3所示,给出了迭代计算过程中,某个页面的Hub权值和Authority权值的更新方式。假设以A(i)代表网页i的Authority权值,以H(i)代表网页i的Hub权值。在图6-14的例子中,“扩充网页集合”有3个网页有链接指向页面1,同时页面1有3个链接指向其它页面。那么,网页1在此轮迭代中的Authority权值即为所有指向网页1页面的Hub权值之和;类似的,网页1的Hub分值即为所指向的页面的Authority权值之和。

                                                      

                                                                    图3 Hub与Authority权值计算

     

     3.4  输出排序结果

          将页面根据Authority权值得分由高到低排序,取权值最高的若干页面作为响应用户查询的搜索结果输出。

    4. HITS算法存在的问题

            HITS算法整体而言是个效果很好的算法,目前不仅应用在搜索引擎领域,而且被“自然语言处理”以及“社交分析”等很多其它计算机领域借鉴使用,并取得了很好的应用效果。尽管如此,最初版本的HITS算法仍然存在一些问题,而后续很多基于HITS算法的链接分析方法,也是立足于改进HITS算法存在的这些问题而提出的。

        归纳起来,HITS算法主要在以下几个方面存在不足:

        1.计算效率较低

            因为HITS算法是与查询相关的算法,所以必须在接收到用户查询后实时进行计算,而HITS算法本身需要进行很多轮迭代计算才能获得最终结果,这导致其计算效率较低,这是实际应用时必须慎重考虑的问题。

       2.主题漂移问题

            如果在扩展网页集合里包含部分与查询主题无关的页面,而且这些页面之间有较多的相互链接指向,那么使用HITS算法很可能会给予这些无关网页很高的排名,导致搜索结果发生主题漂移,这种现象被称为“紧密链接社区现象”(Tightly-Knit CommunityEffect)。

       3.易被作弊者操纵结果

            HITS从机制上很容易被作弊者操纵,比如作弊者可以建立一个网页,页面内容增加很多指向高质量网页或者著名网站的网址,这就是一个很好的Hub页面,之后作弊者再将这个网页链接指向作弊网页,于是可以提升作弊网页的Authority得分。

       4.结构不稳定

            所谓结构不稳定,就是说在原有的“扩充网页集合”内,如果添加删除个别网页或者改变少数链接关系,则HITS算法的排名结果就会有非常大的改变。

    5. HITS算法与PageRank算法比较

         HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出,两者无论是在基本概念模型还是计算思路以及技术实现细节都有很大的不同,下面对两者之间的差异进行逐一说明。      

        1.HITS算法是与用户输入的查询请求密切相关的,而PageRank与查询请求无关。所以,HITS算法可以单独作为相似性计算评价标准,而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价;

        2.HITS算法因为与用户查询密切相关,所以必须在接收到用户查询后实时进行计算,计算效率较低;而PageRank则可以在爬虫抓取完成后离线计算,在线直接使用计算结果,计算效率较高;

        3.HITS算法的计算对象数量较少,只需计算扩展集合内网页之间的链接关系;而PageRank是全局性算法,对所有互联网页面节点进行处理;

        4.从两者的计算效率和处理对象集合大小来比较,PageRank更适合部署在服务器端,而HITS算法更适合部署在客户端;

        5.HITS算法存在主题泛化问题,所以更适合处理具体化的用户查询;而PageRank在处理宽泛的用户查询时更有优势;

        6.HITS算法在计算时,对于每个页面需要计算两个分值,而PageRank只需计算一个分值即可;在搜索引擎领域,更重视HITS算法计算出的Authority权值,但是在很多应用HITS算法的其它领域,Hub分值也有很重要的作用;

        7.从链接反作弊的角度来说,PageRank从机制上优于HITS算法,而HITS算法更易遭受链接作弊的影响。

        8.HITS算法结构不稳定,当对“扩充网页集合”内链接关系作出很小改变,则对最终排名有很大影响;而PageRank相对HITS而言表现稳定,其根本原因在于PageRank计算时的“远程跳转”。


    ----------------------------------------------------------------------------------------------------------

        SALSA算法的初衷希望能够结合PageRank和HITS算法两者的主要特点,既可以利用HITS算法与查询相关的特点,也可以采纳PageRank的“随机游走模型”,这是SALSA算法提出的背景。由此可见,SALSA算法融合了PageRank和HITS算法的基本思想,从实际效果来说,很多实验数据表明,SALSA的搜索效果也都优于前两个算法,是目前效果最好的链接分析算法之一。

            从整体计算流程来说,可以将SALSA划分为两个大的阶段:首先是确定计算对象集合的阶段,这一阶段与HITS算法基本相同;第二个阶段是链接关系传播过程,在这一阶段则采纳了“随机游走模型”。

    1. 确定计算对象集合

            PageRank的计算对象是互联网所有网页,SALSA算法与此不同,在本阶段,其与HITS算法思路大致相同,也是先得到“扩充网页集合”,之后将网页关系转换为二分图形式。

            扩充网页集合

            SALSA算法在接收到用户查询请求后,利用现有搜索引擎或者检索系统,获得一批与用户查询在内容上高度相关的网页,以此作为“根集”。并在此基础上,将与“根集”内网页有直接链接关系的网页纳入,形成“扩充网页集合”(参考图6.4.3-1)。之后会在“扩充网页集合”内根据一定链接分析方法获得最终搜索结果排名。

            转换为无向二分图

            在获得了“扩充网页集合”之后,SALSA根据集合内的网页链接关系,将网页集合转换为一个二分图。即将网页划分到两个子集合中,一个子集合是Hub集合,另外一个子集合是Authority集合。划分网页节点属于哪个集合,则根据如下规则:

    如果一个网页包含出链,这些出链指向“扩充网页集合”内其它节点,则这个网页可被归入Hub集合;

    如果一个网页包含“扩充网页集合”内其它节点指向的入链,则可被归入Authority集合。

            由以上规则可以看出,如果某个网页同时包含入链和出链,则可以同时归入两个集合。同时,Hub集合内网页的出链组成了二分图内的边,根据以上法则,将“扩充网页集合”转换为二分图。

            图6-15和图6-16给出了一个示例,说明了这个转换过程。假设“扩充网页集合”如图6-15所示,由6个网页构成,其链接关系如图所示,同时为便于说明,每个网页给予一个唯一编号。图6-16则是将图6-15中的网页集合转换为二分图的结果。以网页6为例,因为其有出链指向网页节点3和网页节点5,所以可以放入Hub集合,也因为编号为1、3、10的网页节点有链接指向网页节点6,所以也可以放入Authority集合中。网页节点6的两个出链保留,作为二分图的边,

                      

                                                 图6-15 扩充网页集合示例

     

            但是这里需要注意的是,在转换为二分图后,原先的有向边不再保留方向,转换为无向边,而HITS算法仍然保留为有向边,这点与SALSA略有不同。

                           

                                                     图6-16   二分图

             到这一步骤为止,除了SALSA将“扩充网页集合”转换为无向二分图,而HITS仍然是有向二分图外,其它步骤和流程,SALSA算法与HITS算法完全相同,正因此,SALSA保证了是与用户查询相关的链接分析算法。

    2. 链接关系传播

             在链接关系传播阶段,SALSA放弃了HITS算法的Hub节点和Authority节点相互增强的假设,转而采纳PageRank的“随机游走模型”。

    链接关系传播概念模型

            如图6-16所示,假设存在某个浏览者,从某个子集合中随机选择一个节点出发(为方便说明,图中所示为从Hub子集的节点1出发,实际计算往往是从Authority子集出发),如果节点包含多条边,则以相等概率随机选择一条边,从Hub子集跳跃到Authority集合内节点,图中所示为由节点1转移到节点3,之后从Authority子集再次跳回Hub子集,即由节点3跳到节点6。如此不断在两个子集之间转移,形成了SALSA自身的链接关系传播模式。

             尽管看上去与PageRank的链接传播模式不同,其实两者是一样的,关键点在于:其从某个节点跳跃到另外一个节点的时候,如果包含多个可供选择的链接,则以等概率随机选择一条路径,即在权值传播过程中,权值是被所有链接平均分配的。而HITS算法不同,HITS算法属于权值广播模式,即将节点本身的权值完全传播给有链接指向的节点,并不根据链接多少进行分配。

        SALSA的上述权值传播模型与HITS模型关注重点不同,HITS模型关注的是Hub和Authority之间的节点相互增强关系,而SALSA实际上关注的是Hub-Hub以及Authority-Authority之间的节点关系,而另外一个子集合节点只是充当中转桥梁的作用。所以,上述权值传播模型可以转化为两个相似的子模型,即Hub节点关系图和Authority节点关系图。

     

    Authority节点关系图

              图6-17是由6-16的二分图转化成的“Authority节点关系图”,“Hub节点关系图”与此类似,两者转化过程是相似的,我们以“Authority节点关系图”为例来看如何从二分图转化为节点关系图。

                              

                                                                      图6-17  Authority节点关系图

     

            这里需要注意的是:Authority集合内从某个节点i转移到另外一个节点j的概率,与从节点j转移到节点i的概率是不同的,即非对称的,所以转换后的Authority节点关系图是个有向图,以此来表示其转移概率之间的差异。

           对于图6-17这个“Authority节点关系图”来说,图中包含的节点就是二分图中属于Authority子集的节点,关键在于节点之间的边如何建立以及节点之间转移概率如何计算。

     

    节点关系图中边的建立

           之所以在“Authority节点图”中,节点3有边指向节点5,是因为在二分图中,由节点3通过Hub子集的节点6中转,可以通达节点5,所以两者之间有边建立。

           这里需要注意的是:在二分图中,对于Authority集合内某个节点来说,一定可以通过Hub子集的节点中转后再次返回本身,所以一定包含一条指向自身的有向边。节点1因为只有中转节点2使得其返回Authority子集中自身节点,所以只有指向自身的一条边,和其它节点没有边联系,所以例子中的“Authority节点关系图”由两个连通子图构成,一个只有节点1,另外一个连通子图由剩余几个节点构成。

     

    节点之间的转移概率

            至于为何“Authority节点关系图”中,节点3到节点5的转移概率为0.25,是因为前面介绍过,SALSA的权值传播模型遵循“随机游走模型”。在图6-16的二分图中,从节点3转移到节点5的过程中,节点3有两条边可做选择来跳转到Hub子集,所以每条边的选择概率为1/2,可以选择其中一条边到达节点6,同样,从节点6跳回到Authority子集时,节点6也有两条边可选,选中每条边的概率为1/2。所以从节点3出发,经由节点6跳转到节点5的概率为两条边权值的乘积,即为1/4。

           对于指向自身的有向边,其权重计算过程是类似的,我们仍然以节点3为例,指向自身的有向边代表从Authority子集中节点3出发,经由Hub子集的节点再次返回节点3的概率。从6-16的二分图可以看出,完成这个过程有两条路径可走,一条是从节点3到节点1返回;另外一条是从节点3经由节点6后返回;每一条路径的概率与上面所述计算方法一样,因为两条路径各自的概率为0.25,所以节点3返回自身的概率为两条路径概率之和,即为0.5。图中其它边的转移概率计算方式也是类此。

           建立好“Authority节点关系图”后,即可在图上利用“随机游走模型”来计算每个节点的Authority权值。在实际计算过程中,SALSA将搜索结果排序问题进一步转换为求Authority节点矩阵的主秩问题,矩阵的主秩即为每个节点的相应Authority得分,按照Authority得分由高到低排列,即可得到最终的搜索排序结果。

     

    3. Authority权值计算

     

                              

                                                          图6-18  SALSA节点权值计算公式

     

              经过数学推导,可以得出SALSA与求矩阵主秩等价的Authority权值计算公式。图6-18示意图表明了SALSA算法中某个网页节点的Authority权值是如何计算的。如图右上角公式所示,决定某个网页i的Authority权值涉及到4个因子:

             Authority子集中包含的节点总数|A|。其实这个因子对于Authority集合中任意节点来说都是相同的,所以对于最终的根据节点Authority权值进行排序没有影响,只是起到保证权值得分在0到1之间,能够以概率形式表示权值的作用;

            网页i所在连通图中包含的节点个数|Aj|。网页所在的连通图包含的节点个数越多,则网页的Authority权值越大;

            网页i所在连通图中包含的入链总数|Ej|。网页所在的连通图包含的入链总数越少,则网页的Authority权值越大;

            网页i的入链个数|Bi|。节点入链越多,则Authority权值越大,这个因子是唯一一个和节点本身属性相关的。由此可见,SALSA权值计算和节点入链个数成正比。

             之前图6-17的“Authority节点关系图”由两个连通子图组成,一个由唯一的节点1构成,另外一个由节点3、5、6三个节点构成,两个连通子图在图6-18中也被分别圈出。

             我们以节点3为例,看其对应的四个计算因素取值:

    Authority子集共包括4个节点;

    节点3所在连通图包含3个节点;

    节点3所在连通图共有6个入链;

    节点3的入链个数为2;

             所以,节点3的Authority权值为:(3/4)*(2/6)=0.25。其它节点权值的计算过程与此类似。SALSA根据节点的Authority权值由高到低排序输出,即为搜索结果。

             由上述权值计算公式可以推论出:如果整个Authority子集所有节点形成一个完整的连通图,那么在计算authority权值过程中,对于任意两个节点,4个因子中除了节点入链个数外,其它三个因子总是相同,即只有入链个数起作用,此时,SALSA算法退化为根据节点入链个数决定排序顺序的算法。

              从SALSA计算Authority得分过程中可看出,SALSA算法不需像HITS算法一样进行不断迭代计算,所以从计算效率角度看要快于HITS算法。另外,SALSA算法解决了HITS算法的计算结果主题漂移的问题,所以搜索质量也优于HITS算法。SALSA算法是目前效果最好的链接算法之一。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    链接分析算法之:HillTop算法

     Hilltop算法是由Krishna Baharat 在2000年左右研究的,于2001年申请专利,但是有很多人以为Hilltop算法是由谷歌研究的。只不过是Krishna Baharat 后来加入了Google成为了一名核心工程师,然后授权给Google使用的。 

            在与PageRank算法相比之下,Google意识到这个算法的进步会为他们的搜索排名带来非常重要的功能。Google的HillTop算法现在已经能更好的与旧的算法(PR算法)联合起来工作。根据观察HillTop算法比起它在2000年刚设计的时候已经有了很大的进步。显然这也是2003年11月16日“佛罗里达”更新中影响的一个最主要的算法。     

           

    1. Hilltop算法基本思想

           Hilltop融合了HITS和PageRank两个算法的基本思想:

           一方面,Hilltop是与用户查询请求相关的链接分析算法,吸收了HITS算法根据用户查询获得高质量相关网页子集的思想,即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高.符合“子集传播模型”,是该模型的一个具体实例;

          另一方面,在权值传播过程中,Hilltop也采纳了PageRank的基本指导思想,即通过页面入链的数量和质量来确定搜索结果的排序权重。

     

    2. Hilltop算法的一些基本定义

      非从属组织页面   

        “非从属组织页面”(Non-affiliated Pages)是Hilltop算法的一个很重要的定义。要了解什么是非从属组织页面,先要搞明白什么是“从属组织网站”,所谓“从属组织网站”,即不同的网站属于同一机构或者其拥有者有密切关联。具体而言,满足如下任意一条判断规则的网站会被认为是从属网站:

          条件1:主机IP地址的前三个子网段相同,比如:IP地址分别为159.226.138.127和159.226.138.234的两个网站会被认为是从属网站。

          条件2:如果网站域名中的主域名相同,比如:www.ibm.com和www.ibm.com.cn会被认为是从属组织网站。 

         “非从属组织页面”的含义是:如果两个页面不属于从属网站,则为非从属组织页面。图6-22是相关示意图,从图中可以看出,页面2和页面3同属于IBM的网页,所以是“从属组织页面”,而页面1和页面5、页面3和页面6都是“非从属组织页面”。由此也可看出,“非从属组织页面”代表的是页面的一种关系,单个一个页面是无所谓从属或者非从属组织页面的。

         

                               图6-22 “从属组织页面”与“非从属组织页面”

    专家页面:

          “专家页面”(Export Sources)是Hilltop算法的另外一个重要定义。所谓“专家页面”,即与某个主题相关的高质量页面,同时需要满足以下要求:这些页面的链接所指向的页面相互之间都是“非从属组织页面”,且这些被指向的页面大多数是与“专家页面”主题相近的。

    目标页面集合:

         Hilltop算法将互联网页面划分为两类子集合,最重要的子集合是由专家页面构成的互联网页面子集,不在这个子集里的剩下的互联网页面作为另外一个集合,这个集合称作“目标页面集合”(Target Web Servers)。


    3. Hilltop算法

         图6-23是Hilltop算法的整体流程示意。

         1) 建立专家页面索引:首先从海量的互联网网页中通过一定规则筛选出“专家页面”子集合,并单独为这个页面集合建立索引。

         2)用户查询: Hilltop在接收到用户发出的某个查询请求时:

          首先) 根据用户查询的主题,从“专家页面”子集合中找出部分相关性最强的“专家页面”,并对每个专家页面计算相关性得分,

           然后)根据“目标页面”和这些“专家页面”的链接关系来对目标页面进行排序。基本思路遵循PageRank算法的链接数量假设和质量原则,将专家页面的得分通过链接关系传递给目标页面,并以此分数作为目标页面与用户查询相关性的排序得分。

           最后) 系统整合相关专家页面和得分较高的目标页面作为搜索结果返回给用户。

                                 

                                                                图6-23 Hilltop算法流程

          若在上述过程中,Hilltop无法得到一个足够大的专家页面集合,则返回搜索结果为空。由此可以看出,Hilltop算法更注重搜索结果的精度和准确性,不太考虑搜索结果是否足够多或者对大多数用户查询是否都有相应的搜索结果,所以很多用户发出的查询的搜索结果为空。这意味着Hilltop可以与某个排序算法相结合,以提高排序准确性,但并不适合作为一个独立的网页排序算法来使用。

    4. Hilltop算法流程

          从上述整体流程描述可看出,Hilltop算法主要包含两个步骤:专家页面搜索及目标页面排序。

    步骤一:专家页面搜索

             Hilltop算法从1亿4千万网页中,通过计算筛选出250万规模的互联网页面作为“专家页面”集合。“专家页面”的选择标准相对宽松,同时满足以下两个条件的页面即可进入“专家页面”集合:

             条件1:页面至少包含k个出链,这里的数量k可人为指定;

             条件2:k个出链指向的所有页面相互之间的关系都符合“非从属组织页面”的要求;

           当然,在此基础上,可以设定更严格的筛选条件,比如要求这些“专家页面”所包含链接指向的页面中,大部分所涉及的主题和专家页面的主题必须是一致或近似的。

           根据以上条件筛选出“专家页面”后,即可对“专家页面”单独建索引,在此过程中,索引系统只对页面中的“关键片段”(Key Phrase)进行索引。所谓“关键片段”,在Hilltop算法里包含了网页的三类信息:网页标题、H1标签内文字和URL锚文字。

           网页的“关键片段”可以支配(Qualify)某个区域内包含的所有链接,“支配”关系代表了一种管辖范围,不同的“关键片段”支配链接的区域范围不同,具体而言:

           页面标题可以支配页面内所有出现的链接,

           H1标签可以支配包围在<H1>和</H1>内的所有链接,

           URL锚文字只能支配本身唯一的链接。

           图6-24给出了“关键片段”对链接支配关系的示意图,在以“奥巴马访问中国”为标题的网页页面中,标题支配了所有这个页面出现的链接,而H1标签的管辖范围仅限于标签范围内出现的2个链接,对于锚文字“中国领导人”来说,其唯一能够支配的就是本身的这个链接。之所以定义这种支配关系,对于第二阶段将“专家页面”的分值传递到“目标页面”时候会起作用。

                                 

                                     图6-24 “关键片段”链接支配关系

            系统接收到用户查询Q,假设用户查询包含了多个单词,Hilltop如何对“专家页面”进行打分呢?对“专家页面”进行打分主要参考以下三类信息:

             1)“关键片段”包含了多少查询词,包含查询词越多,则分值越高,如果不包含任何查询词,则该“关键片段”不计分;

             2)“关键片段”本身的类型信息,网页标题权值最高,H1标签次之,再次是链接锚文字;

             3)用户查询和“关键片段”的失配率,即“关键片段”中不属于查询词的单词个数占“关键片段”总单词个数,这个值越小越好,越大则得分衰减越多;

           Hilltop综合考虑以上三类因素,拟合出打分函数来对“专家页面”是否与用户查询相关进行打分,选出相关性分值足够高的“专家页面”,以进行下一步骤操作,即对“目标页面”进行相关性计算。

    步骤二:目标页面排序

           Hilltop算法包含一个基本假设,即认为一个“目标页面”如果是满足用户查询的高质量搜索结果,其充分必要条件是该“目标页面”有高质量“专家页面”链接指向。然而,这个假设并不总是成立,比如有的“专家页面”的链接所指向的“目标页面”可能与用户查询并非密切相关。所以,Hilltop算法在这个阶段需要对“专家页面”的出链仔细进行甄别,以保证选出那些和查询密切相关的目标页面。

          Hilltop在本阶段是基于“专家页面”和“目标页面”之间的链接关系来进行的,在此基础上,将“专家页面”的得分传递给有链接关系的“目标页面”。传递分值之前,首先需要对链接关系进行整理,能够获得“专家页面”分值的“目标页面”需要满足以下两点要求:

         条件1:至少需要两个“专家页面”有链接指向“目标页面”,而且这两个专家页面不能是“从属组织页面”,即不能来自同一网站或相关网站。如果是“从属组织页面”,则只能保留一个链接,抛弃权值低的那个链接;

         条件2:“专家页面”和所指向的“目标页面”也需要符合一定要求,即这两个页面也不能是“从属组织页面”;

          在步骤一,给定用户查询,Hilltop算法已经获得相关的“专家页面”及其与查询的相关度得分,在此基础上,如何对“目标页面”的相关性打分?上面列出的条件1指出,能够获得传递分值的“目标页面”一定有多个“专家页面”链接指向,所以“目标页面”所获得的总传播分值是每个有链接指向的“专家页面”所传递分值之和。而计算其中某个“专家页面”传递给“目标页面”权值的时候是这么计算的:

            a. 找到“专家页面” 中那些能够支配目标页面的“关键片段”集合S;

            b. 统计S中包含用户查询词的“关键片段”个数T,T越大传递的权值越大;

            c.“专家页面”传递给“目标页面”的分值为:E*T,E为专家页面本身在第一阶段计算得到的相关得分,T为b步骤计算的分值,

         我们以图6-25的具体例子来说明。假设“专家页面”集合内存在一个网页P,其标题为:“奥巴马访问中国”,网页内容由一段<H1>标签文字和另外一个单独的链接锚文字组成。该页面包含三个出链,其中两个指向“目标页面集合”中的网页www.china.org,另外一个指向网页www.obama.org。出链对应的锚文字分别为:“奥巴马”,“中国”和“中国领导人”。

                            

                       

                                                              图6-25 Hilltop算法分值传递

           从图示的链接关系可以看出,网页P中能够支配www.china.org这个目标页面的“关键片段”集合包括:{中国领导人,中国,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}。而能够支配www.obamba.org目标页面的“关键片段”集合包括:{奥巴马,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}。

          接下来我们分析“专家页面”P在接收到查询时,是怎样将分值传递给与其有链接关系的“目标页面”的。假设系统接收到的查询请求为“奥巴马”,在接收到查询后,系统首先根据上述章节所述,找出“专家页面”并给予分值,而网页P是作为“专家页面”其中一个页面,并获得了相应的分值S,我们重点关注分值传播步骤。

         对于查询“奥巴马”来说,网页P中包含这个查询词的“关键片段”集合为:{奥巴马,<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国},如上所述,这三个“关键片段”都能够支配www.obama.org页面,所以网页P传递给www.obamba.org的分值为S*3。而对于目标页面www.china.org来说,这三个“关键片段”中只有{<H1>奥巴马访问中国</H1>,标题:奥巴马访问中国}这两个能够支配目标页面,所以网页P传递给www.china.org的分值为S*2。

        对于包含多个查询词的用户请求,则每个查询词单独如上计算,将多个查询词的传递分值累加即可。

    5. Hilltop在应用中不足

          专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性;而专家页面的质量和公平性在一定程度上难以保证。 Hiltop忽略了大多数非专家页面的影响。

           在Hilltop的原型系统中,专家页面只占到整个页面的1.79%,不能全面反映民意。

           Hilltop算法在无法得到足够的专家页面子集时(少于两个专家页面),返回为空,即Hilltop适合于对查询排序进行求精,而不能覆盖。这意味着Hilltop可以与某个页面排序算法结合,提高精度,而不适合作为一个独立的页面排序算法。

           Hilltop存在与HITS算法类似的计算效率问题,因为根据查询主题从“专家页面”集合中选取主题相关的页面子集也是在线运行的,这与前面提到的HITS算法一样会影响查询响应时间。随着“专家页面”集合的增大,算法的可扩展性存在不足之处。

    -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

    链接分析算法之:主题敏感PageRank

      前面的讨论提到。PageRank忽略了主题相关性,导致结果的相关性和主题性降低,对于不同的用户,甚至有很大的差别。例如,当搜索“苹果”时,一个数码爱好者可能是想要看 iphone 的信息,一个果农可能是想看苹果的价格走势和种植技巧,而一个小朋友可能在找苹果的简笔画。理想情况下,应该为每个用户维护一套专用向量,但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为主题敏感PageRank(Topic-Sensitive PageRank )的折中方案。主题敏感PageRank的做法是预定义几个话题类别,例如体育、娱乐、科技等等,为每个话题单独维护一个向量,然后想办法关联用户的话题倾向,根据用户的话题倾向排序结果。

          主题敏感PageRankPageRank算法的改进版本,该算法已被Google使用在个性化搜索服务中。

    1. 基本思想

    基本思想:

           通过离线计算出一个与某一主题相关的PageRank向量集合,即计算某个页面关于不同主题的得分。主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定(即在线相似度的计算)。 

    2. 主题敏感PageRank计算流程

    1、确定话题分类

               主题敏感PageRank参考ODP网站(www.dmoz.org),定义了16个大的主题类别,包括体育、商业、科技等。ODP(Open Directory Project)是人工整理的多层级网页分类导航站点(参见图1),在顶级的16个大分类下还有更细致的小

                       

         

                                                                       图1  ODP首页

    粒度分类结构,在最底层目录下,人工收集了符合该目录主题的精选高质量网页地址,以供互联网用户导航寻址。主题敏感PageRank采用了ODP最高级别的16个分类类别作为事先定义的主题类型。 

    2、网页topic 归属

           这一步需要将每个页面归入最合适的分类,具体归类有很多算法,例如可以使用 TF-IDF 基于词素归类,也可以聚类后人工归类。这一步最终的结果是每个网页被归到其中一个 topic。

    3、分topic 向量计算

          在PageRank的向量迭代公式:

             

            

         即R = q  × P * R + ( 1 一 q) * e/N  (e单位向量)

         而在主题敏感PageRank中,向量迭代公式为:

           

              首先是单位向量e变为了s。

              而s是这样一个向量:对于某 topic 的s,如果网页k在此 topic 中,则s中第k个元素为1,否则为0。注意对于每一个 topic 都有一个不同的s。而|s |表示s中 1 的数量。

            假设有页面A,B,C, D,假设页面A归为 Arts,B归为 Computers,C归为 Computers,D归为 Sports。那么对于 Computers 这个 topic,s就是:

               

         假设我们设置阻尼系数q=0.8, 而|s|=2, 因此,迭代公式为:

           

           最后算出的向量就是 Computers 这个 topic 的 rank。如果实际计算一下,会发现B、C页在这个 topic 下的权重相比上面非 Topic-Sensitive 的 rank 会升高,这说明如果用户是一个倾向于 Computers topic 的人(例如程序员),那么在给他呈现的结果中B、C会更重要,因此可能排名更靠前。

    4. 在线相似度计算

            最后一步就是在用户提交搜索时,确定用户的 topic 倾向,以选择合适的 rank 向量。主要方法有两种:

           一种是列出所有 topic 让用户自己选择感兴趣的项目,这种方法在一些社交问答网站注册时经常使用;

           另外一种方法利用“用户查询分类器”对查询进行分类,即搜索引擎会通过某种手段(如 cookie 跟踪)跟踪用户的行为,进行数据分析判断用户的倾向。

           如2,假设用户输入了查询请求“乔丹”,查询词“乔丹”隶属于体育类别的概率为0.6,娱乐类别的概率为0.1,商业类别的概率为0.3                                              


                                                2 在线相似度计算

           在进行上述用户查询分类计算的同时,搜索系统读取索引,找出包含了用户查询“乔丹”的所有网页,并获得已计算好的各个分类主题的PageRank值,在图6-21的例子里,假设某个网页A的各个主题PageRank值分别为体育0.2,娱乐0.3以及商业0.1

          得到用户查询的类别向量和某个网页的主题PageRank向量后,即可计算这个网页和查询的相似度。通过计算两个向量的乘积就可以得出两者之间的相关性。在图6-21的例子里,网页A和用户查询“乔丹”的相似度为:

    Sim(“乔丹”,A)= 0.6*0.2+0.1*0.3+0.3*0.1=0.18

          对包含“乔丹”这个关键词的网页,都根据以上方法计算,得出其与用户查询的相似度后,就可以按照相似度由高到低排序输出,作为本次搜索的搜索结果返回给用户。

    3. 利用主题敏感PageRank构造个性化搜索    

           以上内容介绍的是主题敏感PageRank的基本思想和计算流程,从其内在机制来说,这个算法非常适合作为个性化搜索的技术方案。

        在图2所示例子里,计算相似度使用的只有用户当前输入的查询词“乔丹”,如果能够对此进行扩展,即不仅仅使用当前查询词,也考虑利用用户过去的搜索记录等个性化信息。比如用户之前搜索过“耐克”,则可以推断用户输入“乔丹”是想购买运动服饰,而如果之前搜索过“姚明”,则很可能用户希望获得体育方面的信息。通过这种方式,可以将用户的个性化信息和当前查询相融合来构造搜索系统,以此达到个性化搜索的目的,更精准的提供搜索服务。

    4. 主题敏感PageRank与PageRank的差异 

          PageRank算法基本遵循前面章节提到的“随机游走模型”,即用户在浏览某个网页时,如果希望跳转到其它页面,则随机选择本网页包含的某个链接,进入另外一个页面。主题敏感PageRank则对该概念模型做出改进,引入了更符合现实的假设。一般来说用户会对某些领域感兴趣,同时,当浏览某个页面时,这个页面也是与某个主题相关的(比如体育报道或者娱乐新闻),所以,当用户看完当前页面,希望跳转时,更倾向于点击和当前页面主题类似的链接,即主题敏感PageRank是将用户兴趣、页面主题以及链接所指向网页与当前网页主题的相似程度综合考虑而建立的模型。很明显,这更符合真实用户的浏览过程。

         PageRank是全局性的网页重要性衡量标准,每个网页会根据链接情况,被赋予一个唯一的PageRank分值。主题敏感PageRank在此点有所不同,该算法引入16种主题类型,对于某个网页来说,对应某个主题类型都有相应的PageRank分值,即每个网页会被赋予16个主题相关PageRank分值。

         在接受到用户查询后,两个算法在处理方式上也有较大差异。PageRank算法与查询无关,只能作为相似度计算的一个计算因子体现作用,无法独立使用。而主题敏感PageRank是查询相关的,可单独作为相似度计算公式使用。而且,在接收到用户查询后,主题敏感PageRank还需要利用分类器,计算该查询隶属于事先定义好的16个主题的隶属度,并在相似度计算时的排序公式中利用此信息。


    展开全文
  • 数据分析的6操作步骤

    万次阅读 2015-11-21 17:47:28
    什么是数据分析?数据分析是用适当的统计分析方法对收集来的大量数据进行分析,将它们加以汇理解并消化,以求最大化地开发数据的功能,发挥数据的作用。数据分析的目的?...数据分析大作用:现

    什么是数据分析?数据分析是用适当的统计分析方法对收集来的大量数据进行分析,将它们加以汇理解并消化,以求最大化地开发数据的功能,发挥数据的作用。数据分析的目的?把隐藏在一大批看似杂乱无章的数据背后的信息集中和提炼出来,总结出研究对象的内在规律。

    1

    数据分析的目的

    把隐藏在一大批看似杂乱无章的数据背后的信息集中和提炼出来,总结出研究对象的内在规律。

    数据分析的分类

    2
    数据分析的三大作用:现状分析、原因分析、预测分析。

    数据分析的六部曲

    3
    数据分析流程

    1.明确目的和思路

    梳理分析思路,并搭建分析框架,把分析目的分解成若干个不同的分析要点,即如何具体开展数据分析,需要从哪几个角度进行分析,采用哪些分析指标(各类分析指标需合理搭配使用)。同时,确保分析框架的体系化和逻辑性。

    2.数据收集

    一般数据来源于四种方式:数据库、第三方数据统计工具、专业的调研机构的统计年鉴或报告(如艾瑞资讯)、市场调查。

    对于数据的收集需要预先做埋点,在发布前一定要经过谨慎的校验和测试,因为一旦版本发布出去而数据采集出了问题,就获取不到所需要的数据,影响分析。

    3.数据处理

    数据处理主要包括数据清洗、数据转化、数据提取、数据计算等处理方法,将各种原始数据加工成为产品经理需要的直观的可看数据。

    4.数据分析

    数据分析是用适当的分析方法及工具,对处理过的数据进行分析,提取有价值的信息,形成有效结论的过程。

    常用的数据分析工具,掌握Excel的数据透视表,就能解决大多数的问题。需要的话,可以再有针对性的学习SPSS、SAS等。

    数据挖掘是一种高级的数据分析方法,侧重解决四类数据分析问题:分类、聚类、关联和预测,重点在寻找模式与规律。

    5.数据展现

    一般情况下,数据是通过表格和图形的方式来呈现的。常用的数据图表包括饼图、柱形图、条形图、折线图、气泡图、散点图、雷达图等。进一步加工整理变成我们需要的图形,如金字塔图、矩阵图、漏斗图、帕雷托图等。

    一般能用图说明问题的就不用表格,能用表说明问题的就不用文字。

    图表制作的五个步骤:

    1. 确定要表达主题
    2. 确定哪种图表最适合
    3. 选择数据制作图表
    4. 检查是否真实反映数据
    5. 检查是否表达观点

    常用图表类型和作用:

    5

    6.报告撰写

    一份好的数据分析报告,首先需要有一个好的分析框架,并且图文并茂,层次明晰,能够让阅读者一目了然。结构清晰、主次分明可以使阅读者正确理解报告内容;图文并茂,可以令数据更加生动活泼,提高视觉冲击力,有助于阅读者更形象、直观地看清楚问题和结论,从而产生思考。

    好的数据分析报告需要有明确的结论、建议或解决方案。

    数据分析的四大误区

    1.分析目的不明确,为了分析而分析;

    2.缺乏行业、公司业务认知,分析结果偏离实际。数据必须和业务结合才有意义。摸清楚所在产业链的整个结构,对行业的上游和下游的经营情况有大致的了解,再根据业务当前的需要,制定发展计划,归类出需要整理的数据。同时,熟悉业务才能看到数据背后隐藏的信息;

    3.为了方法而方法,为了工具而工具,只要能解决问题的方法和工具就是好的方法和工具;

    4.数据本身是客观的,但被解读出来的数据是主观的。同样的数据由不同的人分析很可能得出完全相反的结论,所以一定不能提前带着观点去分析。

    诸葛io,是一款基于用户洞察的精细化运营分析工具。由北京诸葛云游科技有限公司于2015年2月推出。诸葛io旨在以用户跟踪技术和简单易用的集成开发方法,帮助移动应用的运营者们挖掘用户的真实行为与属性、优化留存与活跃度、提升用户价值。目前,诸葛io支持Android、iOS和HTML(JS)三个平台。

    展开全文
  • DFMEA步骤二:结构分析

    千次阅读 2020-02-07 12:25:38
    目的 设计结构分析的目的是将设计识别和分解为系统、子系统、组件和零件,以便进行技术...● 功能分析步骤的基础 系统结构 系统结构由系统要素组成。根据分析的范围,设计结构的系统要素可以由系统、子系统、装配件...
  • 政务是大市场,阿里、腾讯、电信、华为都在赔本赚吆喝。本文作者宇同学是资深从业人士,研发总监,他会写一系列文章来阐述政务云全景。 前面八篇分别深入阐述:政务大数据的本质:《 浅谈政务大数据的本质》 ...
  • 很多同学表示,对于微服务中常用的调用功能的原理,感觉很模糊。本文将真正的从零开始,介绍调用客户端开发的一些要点。让你瞬间拥有APM开发经验。随着微服务架构的流行,一次请求往往需要涉及...
  • 区块链:7 个步骤入门区块链

    万次阅读 多人点赞 2019-04-27 09:53:28
    就好比是三个独立的 word 文档,里面描述了交易的内容和余额变化情况。文档 1 会按照时间顺序从第一笔交易开始记录,直到数据量达到 1 MB 为止,之后的交易会记录在文档 2 中,直到数据量达到 1 MB 为止,以此类推。...
  • 链接分析算法之:HillTop算法

    万次阅读 2012-09-26 17:04:43
    Hilltop算法是由Krishna Baharat 在2000年左右研究的,于2001年申请专利,但是有很多人以为Hilltop算法是由... 在与PageRank算法相比之下,Google意识到这算法的进步会为他们的搜索排名带来非常重要的功能。Googl
  • 重磅!不止是芯片!半导体全产业链分析

    万次阅读 多人点赞 2018-04-22 00:00:00
    IC设计可分成几个步骤,依序为:规格制定→逻辑设计→电路布局→布局后模拟→光罩制作。规格制定:品牌厂或白牌厂的工程师和IC设计工程师接触,提出要求;逻辑设计:IC设计工程师完成逻辑设计图;电路布局:将逻辑...
  • K-means算法分析航空公司客户价值

    千次阅读 2019-03-22 10:15:18
    通过客户分群,区分无价值客户和高价值客户。企业针对不同价值的客户制订优化的个性化服务方案,采取不同营销策略,将有限营销资源集中于高价值客户,实现企业利润最大化目标。准确的客户分群结果是企业优化营销资源...
  • 网站分析实战——如何以数据驱动决策,提升网站价值(大数据时代的分析利器) 王彦平吴盛峰 编著 ISBN 978-7-121-19312-5 2013年1月出版 定价:59.00 316页 16开 编辑推荐 掌握3种网站分析秘籍:趋势分析、...
  • 航空公司客户价值分析

    千次阅读 2017-12-03 15:41:14
    (1)识别客户价值的指标:最近消费时间间隔(Recency)、消费频率(Frequency)、消费金额(Monetary) 金额的衡量指标模糊(如在长途低等舱位用户和短途高等舱位的用户选择问题中),将其分为飞行里程数(M)和折扣系数的...
  • ITIL4中的三个基本概念

    千次阅读 2019-11-11 10:24:02
    在ITIL4中引入了三个概念: ...这是三个不同层次的概念,服务价值体系是一个思想体系,服务价值链是一个管理体系,价值流是管理体系中对不同场景的应变。 ITIL 4中的概念 层次 解释 “服务价值体系(SVS,S...
  • 基于RFM模型的用户价值的数据分析报告 分析背景与目的   目前企业的业务逐步从产品为主导转向以客户的需求为主导。一种全新的”以客户为中心“的业务模式正在形成并提升的前所未有的高度。然而与客户保持关系...
  • 淘宝客推广步骤

    千次阅读 2014-04-30 09:20:42
    国内互联网大广告联盟平台中,虽然Google Adsense、百度广告联盟是用户使用的比较多的,像一些大站如新浪、优酷等都能见到谷歌广告的身影,但是如果以广告赢利的利润来分析来看,阿里妈妈淘宝联盟广告或许要高很多...
  • STM32程序的编译、链接和启动分析

    千次阅读 多人点赞 2018-08-02 09:42:50
    本篇文章以STM32为硬件平台,使用GNU GCC作为开发工具,详细分析Compile 、Link 、Loader的过程以及Image(二进制程序)启动的详细分析。整个过程分析涉及到RW可读写段从Flash到Mem的Copy,BSS段的初始化,Stack和Heap...
  • 个步骤实现层级清晰的导航栏

    千次阅读 2016-06-21 15:41:35
    本文作者为 Wes McDowell,主要介绍通过四个步骤实现层级清晰的导航栏,进而提高网站的转化率。文章系国内 ITOM 管理平台 OneAPM 编译呈现。
  • 那么区块链在供应金融这赛道的优势何在?传统的模式存在哪些痛点?区块链能够创造出哪些新的商业模式来解决这些难题?区块链创业公司们又当如何切入这领域? 全球著名债券评级机构穆迪曾给出过127区块链...
  • 「SWOT分析步骤」 2. PEST分析模型 PEST分析的内容 3. 波特五力模型 [定义] [五力模型] 1. SWOT分析模型 「SWOT分析模型简介」 (也称TOWS分析法、道斯矩阵)。在现在的战略规划报告里,SWOT分析应该算是...
  • 数据分析运营---A/B测试中20必须知道的问题

    万次阅读 多人点赞 2017-04-29 23:49:08
    在网站和移动产品设计和开发中、以及互联网产品运营中,我们经常会面临多产品设计和运营方案的选择,比如某个按钮是用红色还是用蓝色,是放左边还是放右边。传统的解决方法通常是集体讨论表决,或者由某位专家或...
  • 在互联网行业普遍产品的数据分析中,我认为用户行为分析最重要的三个点是渠道分析、转化分析和留存分析。  用户行为数据分析最重要的三个点:渠道分析、转化分析和留存分析。  了解Growth Hacker(增长黑客)的...
  • 深度学习学习7步骤

    千次阅读 2017-08-10 15:14:12
    作者:李嘉璇 ...来源:知乎 ...下面就来详细介绍一下这7个步骤。 1.学习或者回忆一些数学知识 因为计算机能做的就只是计算,所以人工智能更多地来说还是数学问题[1]。我们的目标是训练出一个模型,用
  • 夜深人静写算法(九)- Dancing Links X(跳舞

    万次阅读 多人点赞 2018-01-31 19:56:44
    这个矩阵有一个特点就是:“每行三个1”,这是肯定的,因为对于每一行来说,要从三个数字中挑出所有中了两个数字的情况,即C(3,2)=3。但是这不是我们关心的重点,我们关心的是如何选择一些行集合,使得所有列都能被...
  • 价值流程图(Value Stream Mapping)是丰田精益制造(Lean Manufacturing)生产系统框架下的一种用来描述物流和信息流的形象化工具。文/e-works整理它运用精益制造的工具和技术来帮助企业理解和精简生产流程。价值...
  • 金三银四刚过去不久,各家大厂的岗位仍有少量空缺,奈何却招不到合适的人。 身边的HR跟我说,最近面试者情况普遍不太理想。...接下来我作为一工作了将近 3 年前端er来谈谈一名应届生应该如何去获得满意的 offer。
  • 、饥饿营销案例以及4个步骤: 有一种营销技巧,流传了好多年,而且在大江南北、全国各地都能见到这种技巧的影子。这种技巧通常是打着免费赠送的幌子,最后将一些不值钱的产品,以高于原价十几倍、几十倍的价钱...
  • 有的大厂的数据分析师都开到了30k一月,从这数据来看数据分析师是收入不错的职业,但是从群里大家的讨论中我发现,现实并没有那么美好,大部分人的薪资都没有达到10k,甚至一些二、三线城市的数据分析师月薪...
  • 数据分析团队的搭建与思考

    千次阅读 2018-02-22 18:48:16
    但就目前来看,数据驱动业务的增长已经成为一不仅仅是分析方法和模型,而是包括了数据人才培养、数据架构的设计,甚至整个公司组织架构设计的企业治理问题。所以今天我想从途家数据团队的发展、部门的构成及职责这...
  • 如何让数据分析来帮助业务挣钱,这是每数据分析师都会考虑的问题,近几年经常提到的精细化运营、数据驱动增长、增长黑客这样的字眼,这背后的核心就是用户行为分析。 而其中最经典的当属RFM模型吧,简单好操作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 51,886
精华内容 20,754
关键字:

价值链分析的三个步骤