网络数据挖掘 L4L5 网页排序
2018-07-12 本文已影响0人
gb_QA_log
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
