现在的位置: 首页 > 综合 > 正文

数据挖掘:如何寻找相关项

2017年09月30日 ⁄ 综合 ⁄ 共 27324字 ⁄ 字号 评论关闭

数据挖掘:如何寻找相关项

英文原文:bionicspirit.com,编译:CSDN张志平

导读:随着大数据时代浪潮的到来,数据科学家这一新兴职业也越来越受到人们的关注。本文作者Alexandru Nedelcu就将数学挖掘算法与大数据有机的结合起来,并无缝的应用在面临大数据浪潮的网站之中。

数据科学家需要具备专业领域知识并研究相应的算法以分析对应的问题,而数据挖掘是其必须掌握的重要技术。(相关文章:《数据科学家:未来至少5年内的好职业》)以帮助创建推动业务发展的相应大数据产品和 大数据解决方案。EMC最近的一项调查也证实了这点。调查结果显示83%的人认为大数据浪潮所催生的新技术增加了数据科学家的需求。本文将为您展示如何基
于一个简单的公式查找相关的项目。请注意,此项技术适用于所有的网站(如亚马逊),以个性化用户体验、提高转换效率。

http://d2fo8u6if66r8r.cloudfront.net/assets/photos/amazon.png

(图中的《Data Mining》一书中文版是《数据挖掘:实用机器学习技术》)

数据挖掘实用机器学习技术

查找相关项问题

要想为一个特定的项目查找相关项,就必须首先为这两个项目定义相关之处。而这些也正是你要解决的问题:

1. 在博客上,你可能想以标签的形式分享文章,或者对比查看同一个人阅读过的文章

2. 亚马逊站点被称为“购买此商品的客户还购买了”的部分

3, 一个类似于IMDB(Internet Movie Database)的服务,可以根据用户的评级,给出观影指南建议

不论是标签、购买的商品还是观看的电影,我们都要对其进行分门别类。这里我们将采用标签的形式,因为它很简单,而且其公式也适用于更复杂的情形。

以几何关系重定义问题

现在以我的博客为例,来列举一些标签:

1
["API""Algorithms""Amazon""Android""Books""Browser"]

好,我们来看看在欧式空间几何学中如何表示这些标签。

我们要排序或比较的每个项目在空间中以点表示,坐标值(代表一个标签)为1(标记)或者0(未标记)。

因此,如果我们已经获取了一篇标签为“API”和“Browser”的文章,那么其关联点是:

1
100001 ]

现在这些坐标可以表示其它含义。例如,他们可以代表用户。如果在你的系统中有6个用户,其中2个用户对一篇文章分别评了3星和5星,那么你就可以针对此文章查看相关联的点(请注意顺序):

1
030050 ]

现在我们可以计算出相关矢量之间的夹角,以及这些点之间的距离。下面是它们在二维空间中的图像:

欧式几何空间距离

计算欧式几何空间两点之间距离的数学公式非常简单。考虑相关两点A、B之间的距离:

两点之间的距离越近,它们的相关性越大。下面是Ruby代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#
Returns the Euclidean distance between 2 points
#
#
Params:

- a, b: list of coordinates (float or integer)
#
def

euclidean_distance(a, b)
  sq
= a.zip(b).map{|a,b| (a - b) **
2}
  Math.sqrt(sq.inject(0)
{|s,c| s + c})
end
 
#
Returns the associated point of our tags_set, relative to our
#
tags_space.
#
#
Params:

- tags_set: list of tags

- tags_space: _ordered_ list of tags
def

tags_to_point(tags_set, tags_space)
  tags_space.map{|c|
tags_set.member?(c) ?
1

:
0}
end
 
#
Returns other_items sorted by similarity to this_item
#
(most relevant are first in the returned list)
#
#
Params:

- items: list of hashes that have [:tags]

- by_these_tags: list of tags to compare with
def

sort_by_similarity(items, by_these_tags)
  tags_space
= by_these_tags + items.map{|x| x[
:tags]}
  tags_space.flatten!.sort!.uniq!
 
  this_point
= tags_to_point(by_these_tags, tags_space)
  other_points
= items.map{|i|
    [i,
tags_to_point(i[
:tags],
tags_space)]
  }
 
  similarities
= other_points.map{|item, that_point|
    [item,
euclidean_distance(this_point, that_point)]
  }
 
  sorted
= similarities.sort {|a,b| a[
1]
<=> b[
1]}
  return

sorted.map{|point,s| point}
end

这是一些示例代码,你可以直接复制运行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#
SAMPLE DATA
 
all_articles
= [
  {
   :article

=>
"Data
Mining: Finding Similar Items"
,
   :tags

=> [
"Algorithms",
"Programming",
"Mining",
     "Python",
"Ruby"]
  },
  {
   :article

=>
"Blogging
Platform for Hackers"
,
   :tags

=> [
"Publishing",
"Server",
"Cloud",
"Heroku",
     "Jekyll",
"GAE"]
  },
  {
   :article

=>
"UX
Tip: Don't Hurt Me On Sign-Up"
,
   :tags

=> [
"Web",
"Design",
"UX"]
  },
  {
   :article

=>
"Crawling
the Android Marketplace"
,
   :tags

=> [
"Python",
"Android",
"Mining",
     "Web",
"API"]
  }
]
 
#
SORTING these articles by similarity with an article
#
tagged with Publishing + Web + API
#
#
#
The list is returned in this order:
#
#
1. article: Crawling the Android Marketplace
#   
similarity: 2.0
#
#
2. article: "UX Tip: Don't Hurt Me On Sign-Up"
#   
similarity: 2.0
#
#
3. article: Blogging Platform for Hackers
#   
similarity: 2.645751
#
#
4. article: "Data Mining: Finding Similar Items"
#   
similarity: 2.828427
#
 
sorted
= sort_by_similarity(
    all_articles,
[
'Publishing',
'Web',
'API'])
 
require
'yaml'
puts
YAML.dump(sorted)

你是否留意到我们之前选择的数据存在一个缺陷?前两篇文章对于标签“["Publishing", "Web", "API"]”有着相同的欧氏几何空间距离。

为了更加形象化,我们来看看计算第一篇文章所用到的点:

1
2
[1000000000100001]
[1010000010010001]

 

只有四个坐标值不同,我们再来看看第二篇文章所用到的点:

1
2
[1000000000100001]
[0000100000000011]

 

与第一篇文章相同,也只有4个坐标值不同。欧氏空间距离的度量取决于点之间的差异。这也许不太好,因为相对平均值而言,有更多或更少标签的文章会处于不利地位。

余弦相似度

这种方法与之前的方法类似,但更关注相似性。下面是公式:

下面是Ruby代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def

dot_product(a, b)
  products
= a.zip(b).map{|a, b| a * b}
  products.inject(0)
{|s,p| s + p}
end
 
def

magnitude(point)
  squares
= point.map{|x| x **
2}
  Math.sqrt(squares.inject(0)
{|s, c| s + c})
end
 
#
Returns the cosine of the angle between the vectors
#associated
with 2 points
#
#
Params:

- a, b: list of coordinates (float or integer)
#
def

cosine_similarity(a, b)
  dot_product(a,
b) / (magnitude(a) * magnitude(b))
end

对于以上示例,我们对文章进行分类得到:

1
2
3
4
5
6
7
8
9
10
11
-
article: Crawling the Android Marketplace
  similarity:
0.5163977794943222
 
-
article:
"UX
Tip: Don't Hurt Me On Sign-Up"
  similarity:
0.33333333333333337
 
-
article: Blogging Platform
for

Hackers
  similarity:
0.23570226039551587
 
-
article:
"Data
Mining: Finding Similar Items"
  similarity:
0.0

这种方法有了很大改善,我们的代码可以很好地运行,但它依然存在问题。

示例中的问题:Tf-ldf权重

我们的数据很简单,可以轻松地计算并作为衡量的依据。如果不采用余弦相似度,很可能会出现相同的结果。

Tf-ldf权重是一种解决方案。Tf-ldf是一个静态统计量,用于权衡文本集合中的一个词在一个文档中的重要性。

根据Tf-ldff,我们可以为坐标值赋予独特的值,而并非局限于0和1.

对于我们刚才示例中的简单数据集,也许更简单的度量方法更适合,比如Jaccard index也许会更好。

皮尔逊相关系数(Pearson Correlation Coefficient)

使用皮尔逊相关系数(Pearson Correlation Coefficient)寻找两个项目之间的相似性略显复杂,也并不是非常适用于我们的数据集合。

例 如,我们在IMDB中有2个用户。其中一个用户名为John,对五部电影做了评级:[1,2,3,4,5]。另一个用户名为Mary,对这五部电影也给出 了评级:[4, 5, 6, 7, 8]。这两个用户非常相似,他们之间有一个完美的线性关系,Mary的评级都是在John的基础上加3。

计算公式如下:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def

pearson_score(a, b)
  n
= a.length
  return

0

unless

n >
0
 
  #
summing the preferences
  sum1
= a.inject(
0)
{|sum, c| sum + c}
  sum2
= b.inject(
0)
{|sum, c| sum + c}
  #
summing up the squares
  sum1_sq
= a.inject(
0)
{|sum, c| sum + c **
2}
  sum2_sq
= b.inject(
0)
{|sum, c| sum + c **
2}
  #
summing up the product
  prod_sum
= a.zip(b).inject(
0)
{|sum, ab| sum + ab[
0]
* ab[
1]}
 
  #
calculating the Pearson score
  num
= prod_sum - (sum1 *sum2 / n)
  den
= Math.sqrt((sum1_sq - (sum1 **
2)
/ n) * (sum2_sq - (sum2 **
2)
/ n))
 
  return

0

if

den ==
0
  return

num / den
end
 
puts
pearson_score([
1,2,3,4,5],
[
4,5,6,7,8])
#
=> 1.0
puts
pearson_score([
1,2,3,4,5],
[
4,5,0,7,8])
#
=> 0.5063696835418333
puts
pearson_score([
1,2,3,4,5],
[
4,5,0,7,7])
#
=> 0.4338609156373132
puts
pearson_score([
1,2,3,4,5],
[
8,7,6,5,4])
#
=> -1

曼哈顿距离算法

没有放之四海而皆准的真理,我们所使用的公式取决于要处理的数据。下面我们简要介绍一下曼哈顿距离算法。

曼哈顿距离算法计算两点之间的网格距离,维基百科中的图形完美诠释了它与欧氏几何距离的不同:

红线、黄线和蓝线是具有相同长度的曼哈顿距离,绿线代表欧氏几何空间距离。(张志平/编译)

大数据技术综述

原文出处: 程序员

Big Data(大数据技术)是近来的一个技术热点,但从名字就能判断它并不是什么新词。毕竟,大是一个相对概念。历史上,数据库、数据仓库、数据集市等信息管理领域的技术,很大程度上也是为了解决大规模数据的问题。被誉为数据仓库之父的Bill Inmon早在20世纪90年代就经常将Big Data挂在嘴边了。

然而,Big Data作为一个专有名词成为热点,主要应归功于近年来互联网、云计算、移动和物联网的迅猛发展。无所不在的移动设备、RFID、无线传感器每分每秒都在产生数据,数以亿计用户的互联网服务时时刻刻在产生巨量的交互……要处理的数据量实在是太大、增长太快了,而业务需求和竞争压力对数据处理的实时性、有效性又提出了更高要求,传统的常规技术手段根本无法应付。

在这种情况下,技术人员纷纷研发和采用了一批新技术,主要包括分布式缓存、基于MPP的分布式数据库、分布式文件系统、各种NoSQL分布式存储方案等。

10年前,Eric Brewer提出著名的CAP定理,指出:一个分布式系统不可能满足一致性、可用性和分区容忍性这三个需求,最多只能同时满足两个。系统的关注点不同,采用的策略也不一样。只有真正理解了系统的需求,才有可能利用好CAP定理。

架构师一般有两个方向来利用CAP理论。

  • Key-Value存储,如Amazon Dynamo等,可以根据CAP理论灵活选择不同倾向的数据库产品。
  • 领域模型+分布式缓存+存储,可根据CAP理论结合自己的项目定制灵活的分布式方案,但难度较高。

对大型网站,可用性与分区容忍性优先级要高于数据一致性,一般会尽量朝着A、P的方向设计,然后通过其他手段保证对于一致性的商务需求。架构设计师不要将精力浪费在如何设计能满足三者的完美分布式系统,而应该懂得取舍。

不同的数据对一致性的要求是不同的。SNS网站可以容忍相对较长时间的不一致,而不影响交易和用户体验;而像支付宝这样的交易和账务数据则是非常敏感的,通常不能容忍超过秒级的不一致。

图1 memcached构成

图1 memcached构成

Cache篇

缓存在Web开发中运用越来越广泛,mem-cached是danga.com(运营LiveJournal的技术团队)开发的一套分布式内存对象缓存系统,用于在动态系统中减少数据库负载,提升性能。

memcached具有以下特点:

协议简单;基于libevent的事件处理;内置内存存储方式;memcached不互相通信的分布式。

memcached处理的原子是每一个(Key,Value)对(以下简称KV对),Key会通过一个hash算法转化成hash-Key,便于查找、对比以及做到尽可能的散列。同时,memcached用的是一个二级散列,通过一张大hash表来维护。

memcached由两个核心组件组成:服务端(ms)和客户端(mc),在一个memcached的查询中,ms先通过计算Key的hash值来确定KV对所处在的ms位置。当ms确定后,mc就会发送一个查询请求给对应的ms,让它来查找确切的数据。因为这之间没有交互以及多播协议,所以 memcached交互带给网络的影响是最小化的。

MemcacheDB是一个分布式、Key-Value形式的持久存储系统。它不是一个缓存组件,而是一个基于对象存取的、可靠的、快速的持久存储引擎。协议与memcached一致(不完整),所以很多memcached客户端都可以跟它连接。MemcacheDB采用Berkeley DB作为持久存储组件,因此很多Berkeley DB的特性它都支持。

图2 Greenplum数据引擎软件

图2 Greenplum数据引擎软件

类似这样的产品也很多,如淘宝Tair就是Key-Value结构存储,在淘宝得到了广泛使用。后来Tair也做了一个持久化版本,思路基本与新浪MemcacheDB一致。

分布式数据库篇

支付宝公司在国内最早使用Greenplum数据库,将数据仓库从原来的Oracle RAC平台迁移到Greenplum集群。Greenplum强大的计算能力用来支持支付宝日益发展的业务需求。

Greenplum数据引擎软件专为新一代数据仓库所需的大规模数据和复杂查询功能所设计,基于MPP(海量并行处理)和Shared-Nothing(完全无共享)架构,基于开源软件和x86商用硬件设计(性价比更高)。

分布式文件系统篇

谈到分布式文件系统,不得不提的是Google的GFS。基于大量安装有Linux操作系统的普通PC构成的集群系统,整个集群系统由一台 Master(通常有几台备份)和若干台TrunkServer构成。GFS中文件备份成固定大小的Trunk分别存储在不同的TrunkServer 上,每个Trunk有多份(通常为3份)拷贝,也存储在不同的TrunkServer上。Master负责维护GFS中的 Metadata,即文件名及其Trunk信息。客户端先从Master上得到文件的Metadata,根据要读取的数据在文件中的位置与相应的
TrunkServer通信,获取文件数据。

图3 引自Facebook工程师的Hive与Hadoop关系图

图3 引自Facebook工程师的Hive与Hadoop关系图

在Google的论文发表后,就诞生了Hadoop。截至今日,Hadoop被很多中国最大互联网公司所追捧,百度的搜索日志分析,腾讯、淘宝和支付宝的数据仓库都可以看到Hadoop的身影。

Hadoop具备低廉的硬件成本、开源的软件体系、较强的灵活性、允许用户自己修改代码等特点,同时能支持海量数据存储和计算任务。

Hive是一个基于Hadoop的数据仓库平台,将转化为相应的MapReduce程序基于Hadoop执行。通过Hive,开发人员可以方便地进行ETL开发。

如图3所示,引用一张Facebook工程师做的Hive和Hadoop的关系图。

NoSQL篇

随着数据量增长,越来越多的人关注NoSQL,特别是2010年下半年,Facebook选择HBase来做实时消息存储系统,替换原来开发的 Cassandra系统。这使得很多人开始关注HBase。Facebook选择HBase是基于短期小批量临时数据和长期增长的很少被访问到的数据这两个需求来考虑的。

HBase是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统,利用HBase技术可在廉价PC Server上搭建大规模结构化存储集群。HBase是BigTable的开源实现,使用HDFS作为其文件存储系统。Google运行 MapReduce来处理BigTable中的海量数据,HBase同样利用MapReduce来处理HBase中的海量数据;BigTable利用 Chubby作为协同服务,HBase则利用Zookeeper作为对应。

图4 线上应用系统与数据平台的无缝融入

图4 线上应用系统与数据平台的无缝融入

总结篇

近来NoSQL数据库的使用越来越普及,几乎所有的大型互联网公司都在这个领域进行着实践和探索。在享受了这类数据库与生俱来的扩展性、容错性、高读写吞吐外(尽管各主流NoSQL仍在不断完善中),越来越多的实际需求把人们带到了NoSQL并不擅长的其他领域,比如搜索、准实时统计分析、简单事务等。实践中一般会在NoSQL的外围组合一些其他技术形成一个整体解决方案。

准实时的统计分析

  • 传输时统计分析,Stream Processing技术:FlumeBase、S4。

FlumeBase:可参考 http://flumebase.org/documentation/0.1.0/UserGuide.html 中的quick start和architecture两部分。

S4:Yahoo!开源数据来流计算实时框架,可参考http://labs.yahoo.com/files/KDCloud%202010%20S4.pdf

  • 查询时统计分析,结果集较小时,可以直接在返回前做统计分析处理。

比如买家消费记录查询的HBase实现,Schema设计,rowkey=uid,column=搜索词和查询值,version=交易id。

搜索相关

  • 充分利用NoSQL(比如HBase)内部数据的有序性、Row Key、Column Family、Version Timestamp。

我们用“HBase+二次索引”来实现实时营销的解决方案。也可以参考Facebook Message的解决方案:http://blog.bluedavy.com/?p=258

  • 构建一个外围系统完成索引建立。

Google MegaStore:原文链接为http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf ,中文译文链接为http://cloud.csdn.net/a/20110216/291968.html 。

也有人开始尝试基于HBase的MegaStore实现,链接为https://github.com/drevell/megalon 。

简单事务

  • 事务处理服务 + NoSQL存储。
  • 淘宝开发的千亿级海量数据库Oceanbase,通过update server角色执行将写操作限制在一台机器上,实现事务。参考链接为:http://www.nosqlnotes.net/archives/170 。
  • Google MegaStore通过为用户提供机制,根据应用特点划分entity group,将事务涉及的数据分布到一台机器上,实现事务。
  • 大数据技术综述

    原文出处: 程序员

    Big Data(大数据技术)是近来的一个技术热点,但从名字就能判断它并不是什么新词。毕竟,大是一个相对概念。历史上,数据库、数据仓库、数据集市等信息管理领域的技术,很大程度上也是为了解决大规模数据的问题。被誉为数据仓库之父的Bill Inmon早在20世纪90年代就经常将Big Data挂在嘴边了。

    然而,Big Data作为一个专有名词成为热点,主要应归功于近年来互联网、云计算、移动和物联网的迅猛发展。无所不在的移动设备、RFID、无线传感器每分每秒都在产生数据,数以亿计用户的互联网服务时时刻刻在产生巨量的交互……要处理的数据量实在是太大、增长太快了,而业务需求和竞争压力对数据处理的实时性、有效性又提出了更高要求,传统的常规技术手段根本无法应付。

    在这种情况下,技术人员纷纷研发和采用了一批新技术,主要包括分布式缓存、基于MPP的分布式数据库、分布式文件系统、各种NoSQL分布式存储方案等。

    10年前,Eric Brewer提出著名的CAP定理,指出:一个分布式系统不可能满足一致性、可用性和分区容忍性这三个需求,最多只能同时满足两个。系统的关注点不同,采用的策略也不一样。只有真正理解了系统的需求,才有可能利用好CAP定理。

    架构师一般有两个方向来利用CAP理论。

    • Key-Value存储,如Amazon Dynamo等,可以根据CAP理论灵活选择不同倾向的数据库产品。
    • 领域模型+分布式缓存+存储,可根据CAP理论结合自己的项目定制灵活的分布式方案,但难度较高。

    对大型网站,可用性与分区容忍性优先级要高于数据一致性,一般会尽量朝着A、P的方向设计,然后通过其他手段保证对于一致性的商务需求。架构设计师不要将精力浪费在如何设计能满足三者的完美分布式系统,而应该懂得取舍。

    不同的数据对一致性的要求是不同的。SNS网站可以容忍相对较长时间的不一致,而不影响交易和用户体验;而像支付宝这样的交易和账务数据则是非常敏感的,通常不能容忍超过秒级的不一致。

    图1 memcached构成

    图1 memcached构成

    Cache篇

    缓存在Web开发中运用越来越广泛,mem-cached是danga.com(运营LiveJournal的技术团队)开发的一套分布式内存对象缓存系统,用于在动态系统中减少数据库负载,提升性能。

    memcached具有以下特点:

    协议简单;基于libevent的事件处理;内置内存存储方式;memcached不互相通信的分布式。

    memcached处理的原子是每一个(Key,Value)对(以下简称KV对),Key会通过一个hash算法转化成hash-Key,便于查找、对比以及做到尽可能的散列。同时,memcached用的是一个二级散列,通过一张大hash表来维护。

    memcached由两个核心组件组成:服务端(ms)和客户端(mc),在一个memcached的查询中,ms先通过计算Key的hash值来确定KV对所处在的ms位置。当ms确定后,mc就会发送一个查询请求给对应的ms,让它来查找确切的数据。因为这之间没有交互以及多播协议,所以 memcached交互带给网络的影响是最小化的。

    MemcacheDB是一个分布式、Key-Value形式的持久存储系统。它不是一个缓存组件,而是一个基于对象存取的、可靠的、快速的持久存储引擎。协议与memcached一致(不完整),所以很多memcached客户端都可以跟它连接。MemcacheDB采用Berkeley DB作为持久存储组件,因此很多Berkeley DB的特性它都支持。

    图2 Greenplum数据引擎软件

    图2 Greenplum数据引擎软件

    类似这样的产品也很多,如淘宝Tair就是Key-Value结构存储,在淘宝得到了广泛使用。后来Tair也做了一个持久化版本,思路基本与新浪MemcacheDB一致。

    分布式数据库篇

    支付宝公司在国内最早使用Greenplum数据库,将数据仓库从原来的Oracle RAC平台迁移到Greenplum集群。Greenplum强大的计算能力用来支持支付宝日益发展的业务需求。

    Greenplum数据引擎软件专为新一代数据仓库所需的大规模数据和复杂查询功能所设计,基于MPP(海量并行处理)和Shared-Nothing(完全无共享)架构,基于开源软件和x86商用硬件设计(性价比更高)。

    分布式文件系统篇

    谈到分布式文件系统,不得不提的是Google的GFS。基于大量安装有Linux操作系统的普通PC构成的集群系统,整个集群系统由一台 Master(通常有几台备份)和若干台TrunkServer构成。GFS中文件备份成固定大小的Trunk分别存储在不同的TrunkServer 上,每个Trunk有多份(通常为3份)拷贝,也存储在不同的TrunkServer上。Master负责维护GFS中的 Metadata,即文件名及其Trunk信息。客户端先从Master上得到文件的Metadata,根据要读取的数据在文件中的位置与相应的
    TrunkServer通信,获取文件数据。

    图3 引自Facebook工程师的Hive与Hadoop关系图

    图3 引自Facebook工程师的Hive与Hadoop关系图

    在Google的论文发表后,就诞生了Hadoop。截至今日,Hadoop被很多中国最大互联网公司所追捧,百度的搜索日志分析,腾讯、淘宝和支付宝的数据仓库都可以看到Hadoop的身影。

    Hadoop具备低廉的硬件成本、开源的软件体系、较强的灵活性、允许用户自己修改代码等特点,同时能支持海量数据存储和计算任务。

    Hive是一个基于Hadoop的数据仓库平台,将转化为相应的MapReduce程序基于Hadoop执行。通过Hive,开发人员可以方便地进行ETL开发。

    如图3所示,引用一张Facebook工程师做的Hive和Hadoop的关系图。

    NoSQL篇

    随着数据量增长,越来越多的人关注NoSQL,特别是2010年下半年,Facebook选择HBase来做实时消息存储系统,替换原来开发的 Cassandra系统。这使得很多人开始关注HBase。Facebook选择HBase是基于短期小批量临时数据和长期增长的很少被访问到的数据这两个需求来考虑的。

    HBase是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统,利用HBase技术可在廉价PC Server上搭建大规模结构化存储集群。HBase是BigTable的开源实现,使用HDFS作为其文件存储系统。Google运行 MapReduce来处理BigTable中的海量数据,HBase同样利用MapReduce来处理HBase中的海量数据;BigTable利用 Chubby作为协同服务,HBase则利用Zookeeper作为对应。

    图4 线上应用系统与数据平台的无缝融入

    图4 线上应用系统与数据平台的无缝融入

    总结篇

    近来NoSQL数据库的使用越来越普及,几乎所有的大型互联网公司都在这个领域进行着实践和探索。在享受了这类数据库与生俱来的扩展性、容错性、高读写吞吐外(尽管各主流NoSQL仍在不断完善中),越来越多的实际需求把人们带到了NoSQL并不擅长的其他领域,比如搜索、准实时统计分析、简单事务等。实践中一般会在NoSQL的外围组合一些其他技术形成一个整体解决方案。

    准实时的统计分析

    • 传输时统计分析,Stream Processing技术:FlumeBase、S4。

    FlumeBase:可参考 http://flumebase.org/documentation/0.1.0/UserGuide.html 中的quick start和architecture两部分。

    S4:Yahoo!开源数据来流计算实时框架,可参考http://labs.yahoo.com/files/KDCloud%202010%20S4.pdf

    • 查询时统计分析,结果集较小时,可以直接在返回前做统计分析处理。

    比如买家消费记录查询的HBase实现,Schema设计,rowkey=uid,column=搜索词和查询值,version=交易id。

    搜索相关

    • 充分利用NoSQL(比如HBase)内部数据的有序性、Row Key、Column Family、Version Timestamp。

    我们用“HBase+二次索引”来实现实时营销的解决方案。也可以参考Facebook Message的解决方案:http://blog.bluedavy.com/?p=258

    • 构建一个外围系统完成索引建立。

    Google MegaStore:原文链接为http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf ,中文译文链接为http://cloud.csdn.net/a/20110216/291968.html 。

    也有人开始尝试基于HBase的MegaStore实现,链接为https://github.com/drevell/megalon 。

    简单事务

    • 事务处理服务 + NoSQL存储。
    • 淘宝开发的千亿级海量数据库Oceanbase,通过update server角色执行将写操作限制在一台机器上,实现事务。参考链接为:http://www.nosqlnotes.net/archives/170 。
    • Google MegaStore通过为用户提供机制,根据应用特点划分entity group,将事务涉及的数据分布到一台机器上,实现事务。

    社会化海量数据采集爬虫框架搭建

    原文出处: 严澜(@观澜而索源)

    随着BIG DATA大数据概念逐渐升温,如何搭建一个能够采集海量数据的架构体系摆在大家眼前。如何能够做到所见即所得的无阻拦式采集、如何快速把不规则页面结构化并存储、如何满足越来越多的数据采集还要在有限时间内采集。这篇文章结合我们自身项目经验谈一下。

    我们来看一下作为人是怎么获取网页数据的呢?

    1、打开浏览器,输入网址url访问页面内容。
    2、复制页面内容的标题、作者、内容。
    3、存储到文本文件或者excel。

    从技术角度来说整个过程主要为 网络访问、扣取结构化数据、存储。我们看一下用java程序如何来实现这一过程。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    import

    java.io.IOException;
    import

    org.apache.commons.httpclient.HttpClient;
    import

    org.apache.commons.httpclient.HttpException;
    import

    org.apache.commons.httpclient.HttpStatus;
    import

    org.apache.commons.httpclient.methods.GetMethod;
    import

    org.apache.commons.lang.StringUtils;
     
    public

    class

    HttpCrawler {
           public

    static

    void

    main(String[] args) {
     
                String
    content =
    null

    ;
                 try

    {
                      HttpClient
    httpClient =
    new

    HttpClient();
                       //1、网络请求
                      GetMethod
    method =
    new

    GetMethod(
    "http://www.baidu.com"

    );
                       int

    statusCode = httpClient.executeMethod(method);
                       if

    (statusCode == HttpStatus. SC_OK) {
                            content
    = method.getResponseBodyAsString();
                             //结构化扣取
                            String
    title = StringUtils.substringBetween(content,
    "<title>"

    ,
    "</title>"

    );
                             //存储
                            System.
    out .println(title);
                      }
     
                }
    catch

    (HttpException e) {
                      e.printStackTrace();
                }
    catch

    (IOException e) {
                      e.printStackTrace();
                }
    finally

    {
                }
          }
    }

    通过这个例子,我们看到通过httpclient获取数据,通过字符串操作扣取标题内容,然后通过system.out输出内容。大家是不是感觉做一个爬虫也还是蛮简单呢。这是一个基本的入门例子,我们再详细介绍怎么一步一步构建一个分布式的适用于海量数据采集的爬虫框架。

    整个框架应该包含以下部分,资源管理、反监控管理、抓取管理、监控管理。看一下整个框架的架构图:

    crawler1

      • 资源管理指网站分类体系、网站、网站访问url等基本资源的管理维护;
      • 反监控管理指被访问网站(特别是社会化媒体)会禁止爬虫访问,怎么让他们不能监控到我们的访问时爬虫软件,这就是反监控机制了;

    一个好的采集框架,不管我们的目标数据在哪儿,只要用户能够看到都应该能采集到。所见即所得的无阻拦式采集,无论是否需要登录的数据都能够顺利采集。现在大部分社交网站都需要登录,为了应对登录的网站要有模拟用户登录的爬虫系统,才能正常获取数据。不过社会化网站都希望自己形成一个闭环,不愿意把数据放到站外,这种系统也不会像新闻等内容那么开放的让人获取。这些社会化网站大部分会采取一些限制防止机器人爬虫系统爬取数据,一般一个账号爬取不了多久就会被检测出来被禁止访问了。那是不是我们就不能爬取这些网站的数据呢?肯定不是这样的,只要社会化网站不关闭网页访问,正常人能够访问的数据,我们也能访问。说到底就是模拟人的正常行为操作,专业一点叫“反监控”。

    那一般网站会有什么限制呢?

    一定时间内单IP访问次数,没有哪个人会在一段持续时间内过快访问,除非是随意的点着玩,持续时间也不会太长。可以采用大量不规则代理IP来模拟。

    一定时间内单账号访问次数,这个同上,正常人不会这么操作。可以采用大量行为正常的账号,行为正常就是普通人怎么在社交网站上操作,如果一个人一天24小时都在访问一个数据接口那就有可能是机器人了。

    如果能把账号和IP的访问策略控制好了,基本可以解决这个问题了。当然对方网站也会有运维会调整策略,说到底这是一个战争,躲在电脑屏幕后的敌我双方,爬虫必须要能感知到对方的反监控策略进行了调整,通知管理员及时处理。未来比较理想应该是通过机器学习算法自动完成策略调整,保证抓取不间断。

      • 抓取管理指通过url,结合资源、反监控抓取数据并存储;我们现在大部分爬虫系统,很多都需要自己设定正则表达式,或者使用htmlparser、jsoup等软件来硬编码解决结构化抓取的问题。不过大家在做爬虫也会发现,如果爬取一个网站就去开发一个类,在规模小的时候还可以接受,如果需要抓取的网站成千上万,那我们不是要开发成百上千的类。为此我们开发了一个通用的抓取类,可以通过参数驱动内部逻辑调度。比如我们在参数里指定抓取新浪微博,抓取机器就会调度新浪微博网页扣取规则抓取节点数据,调用存储规则存储数据,不管什么类型最后都调用同一个类来处理。对于我们用户只需要设置抓取规则,相应的后续处理就交给抓取平台了。

    整个抓取使用了 xpath、正则表达式、消息中间件、多线程调度框架(参考)。xpath 是一种结构化网页元素选择器,支持列表和单节点数据获取,他的好处可以支持规整网页数据抓取。我们使用的是google插件 XPath
    Helper
    ,这个玩意可以支持在网页点击元素生成xpath,就省去了自己去查找xpath的功夫,也便于未来做到所点即所得的功能。正则表达式补充xpath抓取不到的数据,还可以过滤一些特殊字符。消息中间件,起到抓取任务中间转发的目的,避免抓取和各个需求方耦合。比如各个业务系统都可能抓取数据,只需要向消息中间件发送一个抓取指令,抓取平台抓完了会返回一条消息给消息中间件,业务系统在从消息中间件收到消息反馈,整个抓取完成。多线程调度框架之前提到过,我们的抓取平台不可能在同一时刻只抓一个消息的任务;也不可能无限制抓取,这样资源会耗尽,导致恶性循环。这就需要使用多线程调度框架来调度多线程任务并行抓取,并且任务的数量,保证资源的消耗正常。

    不管怎么模拟总还是会有异常的,这就需要有个异常处理模块,有些网站访问一段时间需要输入验证码,如果不处理后续永远返回不了正确数据。我们需要有机制能够处理像验证码这类异常,简单就是有验证码了人为去输入,高级一些可以破解验证码识别算法实现自动输入验证码的目的。

    扩展一下 :所见即所得我们是不是真的做到?规则配置也是个重复的大任务?重复网页如何不抓取?

    1、有些网站利用js生成网页内容,直接查看源代码是一堆js。 可以使用mozilla、webkit等可以解析浏览器的工具包解析js、ajax,不过速度会有点慢。
    2、网页里有一些css隐藏的文字。使用工具包把css隐藏文字去掉。
    3、图片flash信息。 如果是图片中文字识别,这个比较好处理,能够使用ocr识别文字就行,如果是flash目前只能存储整个url。
    4、一个网页有多个网页结构。如果只有一套抓取规则肯定不行的,需要多个规则配合抓取。
    5、html不完整,不完整就不能按照正常模式去扣取。这个时候用xpath肯定解析不了,我们可以先用htmlcleaner清洗网页后再解析。
    6、 如果网站多起来,规则配置这个工作量也会非常大。如何帮助系统快速生成规则呢?首先可以配置规则可以通过可视化配置,比如用户在看到的网页想对它抓取数据,只需要拉开插件点击需要的地方,规则就自动生成好了。另在量比较大的时候可视化还是不够的,可以先将类型相同的网站归类,再通过抓取的一些内容聚类,可以统计学、可视化抓取把内容扣取出几个版本给用户去纠正,最后确认的规则就是新网站的规则。这些算法后续再讲。这块再补充一下(多谢zicjin建议):

    背景:如果我们需要抓取的网站很多,那如果靠可视化配置需要耗费大量的人力,这是个成本。并且这个交给不懂html的业务去配置准确性值得考量,所以最后还是需要技术做很多事情。那我们能否通过技术手段可以帮助生成规则减少人力成本,或者帮助不懂技术的业务准确的把数据扣取下来并大量复制。

    方案:先对网站分类,比如分为新闻、论坛、视频等,这一类网站的网页结构是类似的。在业务打开需要扣取的还没有录入我们规则库的网页时,他先设定这个页面的分类(当然这个也可以机器预先判断,他们来选择,这一步必须要人判断下),有了分类后,我们会通过“统计学、可视化判断”识别这一分类的字段规则,但是这个是机器识别的规则,可能不准确,机器识别完后,还需要人在判断一下。判断完成后,最后形成规则才是新网站的规则

    7、对付重复的网页,如果重复抓取会浪费资源,如果不抓需要一个海量的去重判断缓存。判断抓不抓,抓了后存不存,并且这个缓存需要快速读写。常见的做法有bloomfilter、相似度聚合、分类海明距离判断。

    • 监控管理指不管什么系统都可能出问题,如果对方服务器宕机、网页改版、更换地址等我们需要第一时间知道,这时监控系统就起到出现了问题及时发现并通知联系人。

    目前这样的框架搭建起来基本可以解决大量的抓取需求了。通过界面可以管理资源、反监控规则、网页扣取规则、消息中间件状态、数据监控图表,并且可以通过后台调整资源分配并能动态更新保证抓取不断电。不过如果一个任务的处理特别大,可能需要抓取24个小时或者几天。比如我们要抓取一条微博的转发,这个转发是30w,那如果每页线性去抓取耗时肯定是非常慢了,如果能把这30w拆分很多小任务,那我们的并行计算能力就会提高很多。不得不提的就是把大型的抓取任务hadoop化,废话不说直接上图:

    crawler2

    今天先写到这里,后续再介绍下 日均千万大型采集项目实战。

大数据技术综述

原文出处: 程序员

Big Data(大数据技术)是近来的一个技术热点,但从名字就能判断它并不是什么新词。毕竟,大是一个相对概念。历史上,数据库、数据仓库、数据集市等信息管理领域的技术,很大程度上也是为了解决大规模数据的问题。被誉为数据仓库之父的Bill Inmon早在20世纪90年代就经常将Big Data挂在嘴边了。

然而,Big Data作为一个专有名词成为热点,主要应归功于近年来互联网、云计算、移动和物联网的迅猛发展。无所不在的移动设备、RFID、无线传感器每分每秒都在产生数据,数以亿计用户的互联网服务时时刻刻在产生巨量的交互……要处理的数据量实在是太大、增长太快了,而业务需求和竞争压力对数据处理的实时性、有效性又提出了更高要求,传统的常规技术手段根本无法应付。

在这种情况下,技术人员纷纷研发和采用了一批新技术,主要包括分布式缓存、基于MPP的分布式数据库、分布式文件系统、各种NoSQL分布式存储方案等。

10年前,Eric Brewer提出著名的CAP定理,指出:一个分布式系统不可能满足一致性、可用性和分区容忍性这三个需求,最多只能同时满足两个。系统的关注点不同,采用的策略也不一样。只有真正理解了系统的需求,才有可能利用好CAP定理。

架构师一般有两个方向来利用CAP理论。

  • Key-Value存储,如Amazon Dynamo等,可以根据CAP理论灵活选择不同倾向的数据库产品。
  • 领域模型+分布式缓存+存储,可根据CAP理论结合自己的项目定制灵活的分布式方案,但难度较高。

对大型网站,可用性与分区容忍性优先级要高于数据一致性,一般会尽量朝着A、P的方向设计,然后通过其他手段保证对于一致性的商务需求。架构设计师不要将精力浪费在如何设计能满足三者的完美分布式系统,而应该懂得取舍。

不同的数据对一致性的要求是不同的。SNS网站可以容忍相对较长时间的不一致,而不影响交易和用户体验;而像支付宝这样的交易和账务数据则是非常敏感的,通常不能容忍超过秒级的不一致。

图1 memcached构成

图1 memcached构成

Cache篇

缓存在Web开发中运用越来越广泛,mem-cached是danga.com(运营LiveJournal的技术团队)开发的一套分布式内存对象缓存系统,用于在动态系统中减少数据库负载,提升性能。

memcached具有以下特点:

协议简单;基于libevent的事件处理;内置内存存储方式;memcached不互相通信的分布式。

memcached处理的原子是每一个(Key,Value)对(以下简称KV对),Key会通过一个hash算法转化成hash-Key,便于查找、对比以及做到尽可能的散列。同时,memcached用的是一个二级散列,通过一张大hash表来维护。

memcached由两个核心组件组成:服务端(ms)和客户端(mc),在一个memcached的查询中,ms先通过计算Key的hash值来确定KV对所处在的ms位置。当ms确定后,mc就会发送一个查询请求给对应的ms,让它来查找确切的数据。因为这之间没有交互以及多播协议,所以 memcached交互带给网络的影响是最小化的。

MemcacheDB是一个分布式、Key-Value形式的持久存储系统。它不是一个缓存组件,而是一个基于对象存取的、可靠的、快速的持久存储引擎。协议与memcached一致(不完整),所以很多memcached客户端都可以跟它连接。MemcacheDB采用Berkeley DB作为持久存储组件,因此很多Berkeley DB的特性它都支持。

图2 Greenplum数据引擎软件

图2 Greenplum数据引擎软件

类似这样的产品也很多,如淘宝Tair就是Key-Value结构存储,在淘宝得到了广泛使用。后来Tair也做了一个持久化版本,思路基本与新浪MemcacheDB一致。

分布式数据库篇

支付宝公司在国内最早使用Greenplum数据库,将数据仓库从原来的Oracle RAC平台迁移到Greenplum集群。Greenplum强大的计算能力用来支持支付宝日益发展的业务需求。

Greenplum数据引擎软件专为新一代数据仓库所需的大规模数据和复杂查询功能所设计,基于MPP(海量并行处理)和Shared-Nothing(完全无共享)架构,基于开源软件和x86商用硬件设计(性价比更高)。

分布式文件系统篇

谈到分布式文件系统,不得不提的是Google的GFS。基于大量安装有Linux操作系统的普通PC构成的集群系统,整个集群系统由一台 Master(通常有几台备份)和若干台TrunkServer构成。GFS中文件备份成固定大小的Trunk分别存储在不同的TrunkServer 上,每个Trunk有多份(通常为3份)拷贝,也存储在不同的TrunkServer上。Master负责维护GFS中的 Metadata,即文件名及其Trunk信息。客户端先从Master上得到文件的Metadata,根据要读取的数据在文件中的位置与相应的
TrunkServer通信,获取文件数据。

图3 引自Facebook工程师的Hive与Hadoop关系图

图3 引自Facebook工程师的Hive与Hadoop关系图

在Google的论文发表后,就诞生了Hadoop。截至今日,Hadoop被很多中国最大互联网公司所追捧,百度的搜索日志分析,腾讯、淘宝和支付宝的数据仓库都可以看到Hadoop的身影。

Hadoop具备低廉的硬件成本、开源的软件体系、较强的灵活性、允许用户自己修改代码等特点,同时能支持海量数据存储和计算任务。

Hive是一个基于Hadoop的数据仓库平台,将转化为相应的MapReduce程序基于Hadoop执行。通过Hive,开发人员可以方便地进行ETL开发。

如图3所示,引用一张Facebook工程师做的Hive和Hadoop的关系图。

NoSQL篇

随着数据量增长,越来越多的人关注NoSQL,特别是2010年下半年,Facebook选择HBase来做实时消息存储系统,替换原来开发的 Cassandra系统。这使得很多人开始关注HBase。Facebook选择HBase是基于短期小批量临时数据和长期增长的很少被访问到的数据这两个需求来考虑的。

HBase是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统,利用HBase技术可在廉价PC Server上搭建大规模结构化存储集群。HBase是BigTable的开源实现,使用HDFS作为其文件存储系统。Google运行 MapReduce来处理BigTable中的海量数据,HBase同样利用MapReduce来处理HBase中的海量数据;BigTable利用 Chubby作为协同服务,HBase则利用Zookeeper作为对应。

图4 线上应用系统与数据平台的无缝融入

图4 线上应用系统与数据平台的无缝融入

总结篇

近来NoSQL数据库的使用越来越普及,几乎所有的大型互联网公司都在这个领域进行着实践和探索。在享受了这类数据库与生俱来的扩展性、容错性、高读写吞吐外(尽管各主流NoSQL仍在不断完善中),越来越多的实际需求把人们带到了NoSQL并不擅长的其他领域,比如搜索、准实时统计分析、简单事务等。实践中一般会在NoSQL的外围组合一些其他技术形成一个整体解决方案。

准实时的统计分析

  • 传输时统计分析,Stream Processing技术:FlumeBase、S4。

FlumeBase:可参考 http://flumebase.org/documentation/0.1.0/UserGuide.html 中的quick start和architecture两部分。

S4:Yahoo!开源数据来流计算实时框架,可参考http://labs.yahoo.com/files/KDCloud%202010%20S4.pdf

  • 查询时统计分析,结果集较小时,可以直接在返回前做统计分析处理。

比如买家消费记录查询的HBase实现,Schema设计,rowkey=uid,column=搜索词和查询值,version=交易id。

搜索相关

  • 充分利用NoSQL(比如HBase)内部数据的有序性、Row Key、Column Family、Version Timestamp。

我们用“HBase+二次索引”来实现实时营销的解决方案。也可以参考Facebook Message的解决方案:http://blog.bluedavy.com/?p=258

  • 构建一个外围系统完成索引建立。

Google MegaStore:原文链接为http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf ,中文译文链接为http://cloud.csdn.net/a/20110216/291968.html 。

也有人开始尝试基于HBase的MegaStore实现,链接为https://github.com/drevell/megalon 。

简单事务

  • 事务处理服务 + NoSQL存储。
  • 淘宝开发的千亿级海量数据库Oceanbase,通过update server角色执行将写操作限制在一台机器上,实现事务。参考链接为:http://www.nosqlnotes.net/archives/170 。
  • Google MegaStore通过为用户提供机制,根据应用特点划分entity group,将事务涉及的数据分布到一台机器上,实现事务。

社会化海量数据采集爬虫框架搭建

原文出处: 严澜(@观澜而索源)

随着BIG DATA大数据概念逐渐升温,如何搭建一个能够采集海量数据的架构体系摆在大家眼前。如何能够做到所见即所得的无阻拦式采集、如何快速把不规则页面结构化并存储、如何满足越来越多的数据采集还要在有限时间内采集。这篇文章结合我们自身项目经验谈一下。

我们来看一下作为人是怎么获取网页数据的呢?

1、打开浏览器,输入网址url访问页面内容。
2、复制页面内容的标题、作者、内容。
3、存储到文本文件或者excel。

从技术角度来说整个过程主要为 网络访问、扣取结构化数据、存储。我们看一下用java程序如何来实现这一过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import

java.io.IOException;
import

org.apache.commons.httpclient.HttpClient;
import

org.apache.commons.httpclient.HttpException;
import

org.apache.commons.httpclient.HttpStatus;
import

org.apache.commons.httpclient.methods.GetMethod;
import

org.apache.commons.lang.StringUtils;
 
public

class

HttpCrawler {
       public

static

void

main(String[] args) {
 
            String
content =
null

;
             try

{
                  HttpClient
httpClient =
new

HttpClient();
                   //1、网络请求
                  GetMethod
method =
new

GetMethod(
"http://www.baidu.com"

);
                   int

statusCode = httpClient.executeMethod(method);
                   if

(statusCode == HttpStatus. SC_OK) {
                        content
= method.getResponseBodyAsString();
                         //结构化扣取
                        String
title = StringUtils.substringBetween(content,
"<title>"

,
"</title>"

);
                         //存储
                        System.
out .println(title);
                  }
 
            }
catch

(HttpException e) {
                  e.printStackTrace();
            }
catch

(IOException e) {
                  e.printStackTrace();
            }
finally

{
            }
      }
}

通过这个例子,我们看到通过httpclient获取数据,通过字符串操作扣取标题内容,然后通过system.out输出内容。大家是不是感觉做一个爬虫也还是蛮简单呢。这是一个基本的入门例子,我们再详细介绍怎么一步一步构建一个分布式的适用于海量数据采集的爬虫框架。

整个框架应该包含以下部分,资源管理、反监控管理、抓取管理、监控管理。看一下整个框架的架构图:

crawler1

    • 资源管理指网站分类体系、网站、网站访问url等基本资源的管理维护;
    • 反监控管理指被访问网站(特别是社会化媒体)会禁止爬虫访问,怎么让他们不能监控到我们的访问时爬虫软件,这就是反监控机制了;

一个好的采集框架,不管我们的目标数据在哪儿,只要用户能够看到都应该能采集到。所见即所得的无阻拦式采集,无论是否需要登录的数据都能够顺利采集。现在大部分社交网站都需要登录,为了应对登录的网站要有模拟用户登录的爬虫系统,才能正常获取数据。不过社会化网站都希望自己形成一个闭环,不愿意把数据放到站外,这种系统也不会像新闻等内容那么开放的让人获取。这些社会化网站大部分会采取一些限制防止机器人爬虫系统爬取数据,一般一个账号爬取不了多久就会被检测出来被禁止访问了。那是不是我们就不能爬取这些网站的数据呢?肯定不是这样的,只要社会化网站不关闭网页访问,正常人能够访问的数据,我们也能访问。说到底就是模拟人的正常行为操作,专业一点叫“反监控”。

那一般网站会有什么限制呢?

一定时间内单IP访问次数,没有哪个人会在一段持续时间内过快访问,除非是随意的点着玩,持续时间也不会太长。可以采用大量不规则代理IP来模拟。

一定时间内单账号访问次数,这个同上,正常人不会这么操作。可以采用大量行为正常的账号,行为正常就是普通人怎么在社交网站上操作,如果一个人一天24小时都在访问一个数据接口那就有可能是机器人了。

如果能把账号和IP的访问策略控制好了,基本可以解决这个问题了。当然对方网站也会有运维会调整策略,说到底这是一个战争,躲在电脑屏幕后的敌我双方,爬虫必须要能感知到对方的反监控策略进行了调整,通知管理员及时处理。未来比较理想应该是通过机器学习算法自动完成策略调整,保证抓取不间断。

    • 抓取管理指通过url,结合资源、反监控抓取数据并存储;我们现在大部分爬虫系统,很多都需要自己设定正则表达式,或者使用htmlparser、jsoup等软件来硬编码解决结构化抓取的问题。不过大家在做爬虫也会发现,如果爬取一个网站就去开发一个类,在规模小的时候还可以接受,如果需要抓取的网站成千上万,那我们不是要开发成百上千的类。为此我们开发了一个通用的抓取类,可以通过参数驱动内部逻辑调度。比如我们在参数里指定抓取新浪微博,抓取机器就会调度新浪微博网页扣取规则抓取节点数据,调用存储规则存储数据,不管什么类型最后都调用同一个类来处理。对于我们用户只需要设置抓取规则,相应的后续处理就交给抓取平台了。

整个抓取使用了 xpath、正则表达式、消息中间件、多线程调度框架(参考)。xpath 是一种结构化网页元素选择器,支持列表和单节点数据获取,他的好处可以支持规整网页数据抓取。我们使用的是google插件 XPath
Helper
,这个玩意可以支持在网页点击元素生成xpath,就省去了自己去查找xpath的功夫,也便于未来做到所点即所得的功能。正则表达式补充xpath抓取不到的数据,还可以过滤一些特殊字符。消息中间件,起到抓取任务中间转发的目的,避免抓取和各个需求方耦合。比如各个业务系统都可能抓取数据,只需要向消息中间件发送一个抓取指令,抓取平台抓完了会返回一条消息给消息中间件,业务系统在从消息中间件收到消息反馈,整个抓取完成。多线程调度框架之前提到过,我们的抓取平台不可能在同一时刻只抓一个消息的任务;也不可能无限制抓取,这样资源会耗尽,导致恶性循环。这就需要使用多线程调度框架来调度多线程任务并行抓取,并且任务的数量,保证资源的消耗正常。

不管怎么模拟总还是会有异常的,这就需要有个异常处理模块,有些网站访问一段时间需要输入验证码,如果不处理后续永远返回不了正确数据。我们需要有机制能够处理像验证码这类异常,简单就是有验证码了人为去输入,高级一些可以破解验证码识别算法实现自动输入验证码的目的。

扩展一下 :所见即所得我们是不是真的做到?规则配置也是个重复的大任务?重复网页如何不抓取?

1、有些网站利用js生成网页内容,直接查看源代码是一堆js。 可以使用mozilla、webkit等可以解析浏览器的工具包解析js、ajax,不过速度会有点慢。
2、网页里有一些css隐藏的文字。使用工具包把css隐藏文字去掉。
3、图片flash信息。 如果是图片中文字识别,这个比较好处理,能够使用ocr识别文字就行,如果是flash目前只能存储整个url。
4、一个网页有多个网页结构。如果只有一套抓取规则肯定不行的,需要多个规则配合抓取。
5、html不完整,不完整就不能按照正常模式去扣取。这个时候用xpath肯定解析不了,我们可以先用htmlcleaner清洗网页后再解析。
6、 如果网站多起来,规则配置这个工作量也会非常大。如何帮助系统快速生成规则呢?首先可以配置规则可以通过可视化配置,比如用户在看到的网页想对它抓取数据,只需要拉开插件点击需要的地方,规则就自动生成好了。另在量比较大的时候可视化还是不够的,可以先将类型相同的网站归类,再通过抓取的一些内容聚类,可以统计学、可视化抓取把内容扣取出几个版本给用户去纠正,最后确认的规则就是新网站的规则。这些算法后续再讲。这块再补充一下(多谢zicjin建议):

背景:如果我们需要抓取的网站很多,那如果靠可视化配置需要耗费大量的人力,这是个成本。并且这个交给不懂html的业务去配置准确性值得考量,所以最后还是需要技术做很多事情。那我们能否通过技术手段可以帮助生成规则减少人力成本,或者帮助不懂技术的业务准确的把数据扣取下来并大量复制。

方案:先对网站分类,比如分为新闻、论坛、视频等,这一类网站的网页结构是类似的。在业务打开需要扣取的还没有录入我们规则库的网页时,他先设定这个页面的分类(当然这个也可以机器预先判断,他们来选择,这一步必须要人判断下),有了分类后,我们会通过“统计学、可视化判断”识别这一分类的字段规则,但是这个是机器识别的规则,可能不准确,机器识别完后,还需要人在判断一下。判断完成后,最后形成规则才是新网站的规则

7、对付重复的网页,如果重复抓取会浪费资源,如果不抓需要一个海量的去重判断缓存。判断抓不抓,抓了后存不存,并且这个缓存需要快速读写。常见的做法有bloomfilter、相似度聚合、分类海明距离判断。

  • 监控管理指不管什么系统都可能出问题,如果对方服务器宕机、网页改版、更换地址等我们需要第一时间知道,这时监控系统就起到出现了问题及时发现并通知联系人。

目前这样的框架搭建起来基本可以解决大量的抓取需求了。通过界面可以管理资源、反监控规则、网页扣取规则、消息中间件状态、数据监控图表,并且可以通过后台调整资源分配并能动态更新保证抓取不断电。不过如果一个任务的处理特别大,可能需要抓取24个小时或者几天。比如我们要抓取一条微博的转发,这个转发是30w,那如果每页线性去抓取耗时肯定是非常慢了,如果能把这30w拆分很多小任务,那我们的并行计算能力就会提高很多。不得不提的就是把大型的抓取任务hadoop化,废话不说直接上图:

crawler2

今天先写到这里,后续再介绍下 日均千万大型采集项目实战。

抱歉!评论已关闭.