1.基本的数据分析算法

关联分析

X→Y的关联分析主要靠下面几个度量值：

支持度：同时包含X和Y的事务数/总事务数 P(AUB)
置信度：同时包含X和Y的事务数/包含X的事务数 P(A|B)
提升度：在X发生的条件下，Y发生的概率/Y发生的总概率（>1是才是有效强关联，<=1都不是有效的）P(B|A)/P(B)

判断提升度是否可靠还有以下两个参数
- KULC = 0.5 * P(X|Y) + 0.5 * P(Y|X)
- IR = P(Y|X) / P(X|Y)
http://www.cnblogs.com/michael-xiang/p/4598150.html

Apriori

遍历购物车，统计单个商品出现的次数，过滤掉次数小于一定阈值（最小支持度）的商品，得到频繁单项集；
遍历购物车，两两组合其中商品，如果一个商品对中的两个商品都在频繁单项集中，则统计商品对的出现次数，否则跳过，过滤掉小于最小支持度的，得到频繁2项集；
……….
N. 如果频繁N-1项集不为空，则进行第N次遍历，从每个购物车中取任意N个商品的组合，如果这N项的所有N-1项子集都在频繁N-1项集中，则统计其出现次数，否则跳过，过滤掉小于最小支持度的，得到频繁N项集。当频繁项集为空时停止循环。

Ck: 长度为k的候选项集
Lk :长度为k的频繁项集
L1 = {frequent items};
    for (k = 1; Lk !=∅; k++) do 
    begin
        Ck+1 = 从Lk 生成候选项集;   
        对于数据集中的任一交易 t   do
       如果 t 中包含 Ck+1中所包含的项集，则计数加 1
        Lk+1  = Ck+1 中超过最小支持度的频繁项集
    end
  return ∪k Lk;

分类与预测

ID3:经验熵
- H（D）=-pi*log2（pi）
- g（D，Ai）=H（D）-（Σ Pi*H（Di）
KNN

聚类

K-Means

2.MapReduce

分布式并行编程

分布式程序运行在大规模计算机集群上，集群中包括大量廉价服务器，可以并行执行大规模数据处理任务，从而获得海量的计算能力

模型简介

MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数：Map和Reduce
在MapReduce中，一个存储在分布式文件系统中的大规模数据集，会被切分成许多独立的小数据块，这些小数据块可以被多个Map任务并行处理
MapReduce框架会为每个Map任务输入一个数据子集，Map任务生成的结果会继续作为Reduce任务的输入，最终由Reduce任务输出最后结果，并写入到分布式文件系统中
MapReduce设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为，移动数据需要大量的网络传输开销
MapReduce框架采用了Master/Slave架构，包括一个Master和若干个Slave。Master上运行JobTracker，Slave上运行TaskTracker
Hadoop框架是用Java实现的，但是，MapReduce应用程序则不一定要用Java来写

Map

输入：<k1,v1>
输出：List(<k2,v2>)
将小数据进一步分析成一批<key,value>对，输入Map函数进行处理；每一个输入的<k1,v1>会输出一批<k2,v2>

Reduce

输入：<k2,List(v2)>
输出：<k3,v3>
输入的结果<k2,List(v2)>中的List(v2)表示是同一批属于同一个v2的value

工作流程

以下摘自：用通俗易懂的大白话讲解Map/Reduce原理

我问妻子：“你真的想要弄懂什么是MapReduce？” 她很坚定的回答说“是的”。因此我问道：

我：你是如何准备洋葱辣椒酱的？（以下并非准确食谱，请勿在家尝试）

妻子：我会取一个洋葱，把它切碎，然后拌入盐和水，最后放进混合研磨机里研磨。这样就能得到洋葱辣椒酱了。

妻子：但这和MapReduce有什么关系？

我：你等一下。让我来编一个完整的情节，这样你肯定可以在15分钟内弄懂MapReduce.

妻子：好吧。

我：现在，假设你想用薄荷、洋葱、番茄、辣椒、大蒜弄一瓶混合辣椒酱。你会怎么做呢？

妻子：我会取薄荷叶一撮，洋葱一个，番茄一个，辣椒一根，大蒜一根，切碎后加入适量的盐和水，再放入混合研磨机里研磨，这样你就可以得到一瓶混合辣椒酱了。

我：没错，让我们把MapReduce的概念应用到食谱上。Map和Reduce其实是两种操作，我来给你详细讲解下。
Map（映射）: 把洋葱、番茄、辣椒和大蒜切碎，是各自作用在这些物体上的一个Map操作。所以你给Map一个洋葱，Map就会把洋葱切碎。同样的，你把辣椒，大蒜和番茄一一地拿给Map，你也会得到各种碎块。所以，当你在切像洋葱这样的蔬菜时，你执行就是一个Map操作。 Map操作适用于每一种蔬菜，它会相应地生产出一种或多种碎块，在我们的例子中生产的是蔬菜块。在Map操作中可能会出现有个洋葱坏掉了的情况，你只要把坏洋葱丢了就行了。所以，如果出现坏洋葱了，Map操作就会过滤掉坏洋葱而不会生产出任何的坏洋葱块。

Reduce（化简）:在这一阶段，你将各种蔬菜碎都放入研磨机里进行研磨，你就可以得到一瓶辣椒酱了。这意味要制成一瓶辣椒酱，你得研磨所有的原料。因此，研磨机通常将map操作的蔬菜碎聚集在了一起。

妻子：所以，这就是MapReduce?

我：你可以说是，也可以说不是。其实这只是MapReduce的一部分，MapReduce的强大在于分布式计算。

妻子：分布式计算？那是什么？请给我解释下吧。

我：没问题。

我：假设你参加了一个辣椒酱比赛并且你的食谱赢得了最佳辣椒酱奖。得奖之后，辣椒酱食谱大受欢迎，于是你想要开始出售自制品牌的辣椒酱。假设你每天需要生产10000瓶辣椒酱，你会怎么办呢？

妻子：我会找一个能为我大量提供原料的供应商。

我：是的…就是那样的。那你能否独自完成制作呢？也就是说，独自将原料都切碎？仅仅一部研磨机又是否能满足需要？而且现在，我们还需要供应不同种类的辣椒酱，像洋葱辣椒酱、青椒辣椒酱、番茄辣椒酱等等。

妻子：当然不能了，我会雇佣更多的工人来切蔬菜。我还需要更多的研磨机，这样我就可以更快地生产辣椒酱了。
我：没错，所以现在你就不得不分配工作了，你将需要几个人一起切蔬菜。每个人都要处理满满一袋的蔬菜，而每一个人都相当于在执行一个简单的Map操作。每一个人都将不断的从袋子里拿出蔬菜来，并且每次只对一种蔬菜进行处理，也就是将它们切碎，直到袋子空了为止。
这样，当所有的工人都切完以后，工作台（每个人工作的地方）上就有了洋葱块、番茄块、和蒜蓉等等。

妻子：但是我怎么会制造出不同种类的番茄酱呢？

我：现在你会看到MapReduce遗漏的阶段—搅拌阶段。MapReduce将所有输出的蔬菜碎都搅拌在了一起，这些蔬菜碎都是在以key为基础的 map操作下产生的。搅拌将自动完成，你可以假设key是一种原料的名字，就像洋葱一样。所以全部的洋葱keys都会搅拌在一起，并转移到研磨洋葱的研磨器里。这样，你就能得到洋葱辣椒酱了。同样地，所有的番茄也会被转移到标记着番茄的研磨器里，并制造出番茄辣椒酱。

Shufflef过程详解

从Map输出到Reduce输入的整个过程可以广义地称为Shuffle。

Shuffle横跨Map端和Reduce端，在Map端包括Spill过程，在Reduce端包括copy和sort过程，

Spill过程：Spill过程包括输出、排序、溢写、合并等步骤

例子

1.Map：分别计算

2.shuffle（有）：先内部算

3.reduce：统计总结果

3.网络数据计算

社交网络计算

搜索引擎计算

餐馆推荐
auth和hub值
PageRank：
- 重要性：进来的和

市场分配计算

1.根据点击率算广告位估值：广告位价值=点击价值*点击率

2.市场清仓价格：