title: 网络数据挖掘 L4L5 网页排序
date: 2017-04-12 18:34:16
categories: DataMining
mathjax: true
tags: [WebDataMining]

L4 Ranking Aggregation

Social Choice Theory社会选择理论是关于投票的理论

我们如何做决定：

• 硬币
• Dictatorship独裁
• Democracy (Majority rule)大多数
• 还要考虑群体的异质偏好heterogeneous preferences

集体智慧

现在的民主方式其实是默认了一个前提，“集体智慧”。

• Cognition 群体决策会比一部分专家更高效和客观
• Coordination 代表了整体的文化认可度
• Cooperation 避免胁迫，更自由

但其实集体智慧有很多因素要考虑。不是所有人都能做正确明智的选择：

• 差异化
• 盲从
• 意见分散
• 争论

主观、意见分散、集权、跟从都可能导致失败
处于对不同人的意见的综合考虑，实际生活中就有了各种应用：

• 选举
• 民意调查
• 特定的选举规则（如美国的赢家通吃）
• 搜索排行

Rule

• Majority rule 多数
• Condorcet paradox ：康多塞悖论，投票的结果和投票的顺序有关
• Borda-Rule 博尔达计分法：每个人给每个方案都打分，再统计
  其他变形：
• Weighted Borda-Rule
• With relevant scores available
  早期算法：
• Min, Max and Average model[Fox and Shaw,1995]
  • Algorithm Final score
  • CombMin minimum of individual relevance scores
  • CombMed median of individual relevance scores
  • CombMax maximum of individual relevance scores
  • CombSum sum of individual relevance scores
  • CombANZ CombSum / num non-zero relevance scores
  • CombMNZ CombSum * num non-zero relevance scores
• Linear Combination Model[Bartell 1995]给每个数据加权
• Logistic Regression Model

以上算法在TREC会议上多有应用。

L5 Web Structure Mining

介绍

网络结构：

• 图
• 特征：
  • 大
  • 未知
  • 动态

因此需要考虑实际的关注点、计算能力、内存等情况来构造网络图。为了构造这张图，先定义以下几个函数关系：

• Back_url(the_url)找出所有指向本url的url
  • 一定程度上反应重要性
  • 苦难
  • 利用搜索引擎link:url
• Shortest_Path(url,url2)最短路径
• Maximal_Clique(url)最大团，类似于找url的闭包
• In_Degree(url)入度

Web Graph Mining

Fan：Back_url

流行程度
真粉？
特殊情况：google.com等

PageRank的计算

能够表明网页的流行程度。其中T是指向A的网页，而C(T)是T指向网页的总数
PR(A)=(1-d)+d*(\frac{PR(T_1)}{C(T_1)}+\frac{PR(T_2)}{C(T_2)}+...\frac{PR(T_n)}{C(T_n)})
举个例子：

Paste_Image.png

PR(a)=1, PR(b)=1, PR(c) =1

Paste_Image.png

Paste_Image.png

Paste_Image.png

Web Community

给定一些网页，找他们中的密集连接在一起的Community

• 完全子图
• 完全双向子图

附：
数据堂:出售数据
相关数据集、算法网站
http://webla.sourceforge.net/javadocs/pt/tumba/links/WebGraph.html
http://introcs.cs.princeton.edu/java/45graph/Digraph.java.html
http://www.cs.ucsb.edu/~kris/Research/agl/doc/agl2/Digraph.html