Introduction

definition

在计算机科学中，routines 被定义为一系列操作。routines的执行过程形成了一种父-子关系，子routine总是先于父routine终止。 Couroutines是routines的一种泛化.(Donald Knuth:协程和routines的主要区别是一个协程可以通过附加的操作明确的进行挂起和恢复，这一机制主要是通过保存执行状态并且提供了加强的控制流程（保存执行上下文）来实现的。

how it works

函数 foo 和 bar 可以切换执行，离开自己的函数体，进入对方的体内执行。

如果Couroutines的调用方式和routine一模一样的话，栈区就会一直增长并且永远不会出栈。而且如果调用方式一样，那么跳转到一个Couroutine中间执行就不可能实现，因为返回地址会在栈顶。

##1.引言

在处理数据时常常需要对数据进行可视化以便观察,但是,在笛卡尔坐标系下,超过3维的数据我们就无法可视化了,所以,我们就需要一种有效的方法来可视化高维数据.

常用的方法有Parallel Coordinates,关于这个方法的介绍可以看wikipedia页面,这里就不再重复了.

##2.python解决方案

用python实现高维数据可视化需要用到几个库函数 :

1. Pandas : parallel_coordinates
2. Pandas : DataFrame
3. scikit-learn : datasets.load_iris()
4. Numpy

这里有一个简单的教程来熟悉pands语法:
10分钟熟悉pandas

如果对pandas的数据结构不了解,还要熟悉一下它的数据结构
Pandas 数据结构简介

DataFrame 的API文档

材料准备齐全,就可以开始进行可视化操作了.

##3. 实现过程

3.1 准备数据

首先找一个经典的4维数据集: 鸢尾花 iris数据集 wiki ,uci下载地址

数据集简要描述:

只有四个属性:

1. sepal length in cm
2. sepal width in cm
3. petal length in cm
4. petal width in cm

共三类:

• Iris Setosa
• Iris Versicolour
• Iris Virginica

3.1.1 导入数据

由于scikit-learn已经内建了这个数据集,可以直接导入使用

1
2
3

from sklearn import datasets
data_origin = datasets.load_iris()

data_origin是一个 python 字典, 包含了

• ‘target_names’: 标签名,’setosa’ ‘versicolor’ ‘virginica’
• ‘data’: 数据 ,150 * 4的 ndarray 对象
• ‘target’: 标签值, 0 1 2, 分别对应一个标签名
• ‘feature_names’: 特征名, ‘sepal length (cm)’, ‘sepal width (cm)’, ‘petal length (cm)’, ‘petal width (cm)’
• ‘DESC’ : 数据集描述字符串

3.1.2 处理数据

由于我们要调用 pandas 的 parallel_coordinates 函数,它需要一个 Pandas.DataFrame 对象格式的数据,所以我们要把上面的数据包装到一个 DataFrame对象里.

DataFrame对象其实就和Sql数据库中的表一样,它和矩阵的不同之处在于它包含了每一列的名称和每一行的名称.

由于Pandas可以由多种数据类型构造:

• Dict of 1D ndarrays,lists,or Series (由 1维的 ndarray,list,Serie 构成的 字典Dict)
• 2-D numpy.ndarray 2维的numpy 多维数组
• numpy中的 Structured or record ndarry
• Pandas中的 一个 Series
• 另一个DataFrame

这里,我选用第一种方式,用python中的字典对象构造.把iris数据包装成一个DataFrame对象,前四列是每个特征对应的值,最后一列是该行数据的数据类型(用target_name构造).每一行是一个数据.

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

# 先把数据提取出来
data = data_origin['data']
# 处理类标签数据
target= data_origin['target']
target_names = data_origin['target_names']
target_labels=[]
for class_num in target:
    target_labels.append(target_names[class_num])
feature_names = data_origin['feature_names']
# 合成字典
data_dict = {}
column = 0
for feature_name in feature_names:
    data_dict[feature_name] = data[:,column]
    column+=1
data_dict['target_labels'] = target_labels

有了字典后就可以合成pandas DataFrame了

1
2
3
4
5

# 包装成 DataFrame
import pandas as pd
pd_data = pd.DataFrame(data_dict)

###3.1.3 画图

有了数据后,画图就十分方便,只需要调用 pandas 的内置函数 parallel_coordinates() 就好了:

1
2
3
4
5
6
7
8
9

from pandas.tool.plotting import parallel_coordinates
import matplotlib.pyplot as plt
plt.figure()
parallel_coordinates(pd_data,'target-labels')
plt.show()

这样,图就画好了 :

##画一个 500维的数据集 madelon

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
49
50
51
52
53
54
55
56

#coding=utf-8
__author__ = 'anboqing'
from pandas.tools.plotting import parallel_coordinates
import pandas as pd
import numpy as np
import LoadLibSvm as ld
import matplotlib.pyplot as plt
origin_data,origin_label = ld.load_libsvm_data('madelon')
#print type(origin_data)
# 读取到原始数据和数据的标签后,要包装成一个DataFrame对象
#print np.shape(origin_label)
mat_data = np.mat(origin_data)
mat_data = mat_data.transpose()
"""
#print type(mat_data)
arr_data = np.array(origin_data)
#print arr_data.shape
print type(arr_data)
print type(mat_data[1,:])
arr = np.array(mat_data[1,:])
lst = list(arr)
print type(lst)
print np.shape(lst)
print lst[0]
lst = list(lst[0])
print lst[0]
print type(lst[0])
"""
# 先包装成一个dict
data_dict = {}
for idx in range(mat_data.shape[0]):
    arr = np.array(mat_data[idx,:])
    lst = list(arr)
    lst = list(lst[0])
    data_dict[str(idx)] = lst
data_dict['label']=origin_label
pd_df = pd.DataFrame(data_dict)
"""
选了4列来画,能画出来,说明方法是对的,然而画所有列全都是黑的,说明图片尺寸太小了
small_data = pd.DataFrame(pd_df,columns=['1','2','3','label'])
plt.figure()
parallel_coordinates(small_data,'label')
plt.show()
"""
plt.figure(figsize=(100,50),dpi=20)
parallel_coordinates(pd_df,'label')
plt.show()

画出来效果是这样:

下面是大图,可以在新页面打开放大看细节:

以食堂买饭的过程类比并发模型

1. 多进程：

食堂有n个窗口，每个窗口相当于一个进程（只有一个厨师，只能为一个同学做饭），要开一个窗口开销比较大。每个窗口一次为1个同学做饭，后面的同学只能等当前同学饭好了才能买饭。

2. 多线程：

食堂的每个窗口（进程）可以有多个厨师（多个线程），一个窗口可以为多个同学同时做饭，当没有闲着的厨师的时候，该窗口就不能再接待更多的同学了（线程达到上限），并且，买饭的同学必须在窗口前等待（阻塞），此时该窗口也停止接受新的订单。

3. 协程：

食堂的每个窗口有一个厨师和一个接待员（单个线程），每来一个同学，就接一个订单，然后给同学发一个号码牌，让同学去干别的事情，不用等着，然后接待员继续接单，厨师去做饭，等饭好了，接单员就喊相应号码的同学：同学你的饭好了！然后那个同学就能吃上饭了。其他同学则继续干其他事情，接单员处于一个永真循环中一直接单，厨师也一直做饭，从而实现了并发。并且这种并发没有切换的开销。

在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器 进入SYN_RECV状态；
第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入 ESTABLISHED状态，完成三次握手。
通过这样的三次握手，客户端与服务端建立起可靠的双工的连接，开始传送数据。
三次握手的最主要目的是保证连接是双工的，可靠更多的是通过重传机制来保证的。

但是为什么一定要进行三次握手来保证连接是双工的呢，一次不行么？两次不行么？我们举一个现实生活中两个人进行语言沟通的例子来模拟三次握手。

第一次对话：
老婆让甲出去打酱油，半路碰到一个朋友乙，甲问了一句：哥们你吃饭了么？
结果乙带着耳机听歌呢，根本没听到，没反应。甲心里想：跟你说话也没个音，不跟你说了，沟通失败。说明乙接受不到甲传过来的信息的情况下沟通肯定是失败的。
如果乙听到了甲说的话，那么第一次对话成功，接下来进行第二次对话。
第二次对话：
乙听到了甲说的话，但是他是老外，中文不好，不知道甲说的啥意思也不知道怎样回答，于是随便回答了一句学过的中文 ：我去厕所了。甲一听立刻笑喷了，“去厕所吃饭”?道不同不相为谋，离你远点吧，沟通失败。说明乙无法做出正确应答的情况下沟通失败。
如果乙听到了甲的话，做出了正确的应答，并且还进行了反问：我吃饭了，你呢？那么第二次握手成功。
通过前两次对话证明了乙能够听懂甲说的话，并且能做出正确的应答。接下来进行第三次对话。
第三次对话：
甲刚和乙打了个招呼，突然老婆喊他，“你个死鬼，打个酱油咋这么半天，看我回家咋收拾你”，甲是个妻管严，听完吓得二话不说就跑回家了，把乙自己晾那了。乙心想：这什么人啊，得，我也回家吧，沟通失败。说明甲无法做出应答的情况下沟通失败。
如果甲也做出了正确的应答：我也吃了。那么第三次对话成功，两人已经建立起了顺畅的沟通渠道，接下来开始持续的聊天。
通过第二次和第三次的对话证明了甲能够听懂乙说的话，并且能做出正确的应答。
可见，两个人进行有效的语言沟通，这三次对话的过程是必须的。
同理对于TCP为什么需要进行三次握手我们可以一样的理解：
为了保证服务端能收接受到客户端的信息并能做出正确的应答而进行前两次(第一次和第二次)握手，为了保证客户端能够接收到服务端的信息并能做出正确的应答而进行后两次(第二次和第三次)握手。

在此输入正文

课程简介

We’ll learn about the how the brain uses two very different learning modes and how it encapsulates (“chunks”) information. We’ll also cover illusions of learning, memory techniques, dealing with procrastination, and best practices shown by research to be most effective in helping you master tough subjects.

第一课 What is Learning?

Although living brains are very complex, this module uses metaphor and analogy to help simplify matters. You will discover several fundamentally different modes of thinking, and how you can use these modes to improve your learning. You will also be introduced to a tool for tackling procrastination, be given some practical information about memory, and discover surprisingly useful insights about learning and sleep.

Focused versus Diffuse Thinking 集中思维和发散思维

Introduction to the Focused and Diffuse Modes

研究表明，我们的大脑有两种基本的思维模式： Focused , Diffuse

• 集中思维 : 注意力很集中的状态，会用过去已经习得的神经路径去类比要学的新知识，你会找到新知识和你已经很熟悉的知识有很大的相似处。
• 发散思维 : 这是一个更放松的思考方式，和一系列的神经休息状态有关。如果你的工作需要你大脑中没有的新的方法或者创意 ，你如何去开发新的神经路径呢？就要用到发散思维方式，思绪在大脑中随意游走，思绪纷飞，你就会创建新的神经联系和新的神经路径。这就是新知识。
• 你不能同时使用2这两种思维模式

Using the Focused and Diffuse Modes–Or, a Little Dali will do You

在不同的思维模式间切换，当遇到困但问题时，先放松用发散模式思考，然后再带着发散模式的思考灵感去专注思考。

###1. What is Learning?
当安静地学习时，大脑会在走神时切换成发散模式。

记忆储存在成千上亿个神经突触（synapse）里面

传统观点认为大脑一旦发育成熟，可以通过学习来增强神经突触，但认知能力无法改变，除非脑部受到重创，但现在我们得知，大脑在成熟以后的认知能力是平衡的。

随着光学成像技术的发展，我们可以看到神经元中突触的链接，由此我们发现，突触的数量是不变的，新的形成旧的就会消失，但为什么突触神经元来来去去，记忆却没有随着突触神经元的消失而消失？树突接受了来自其他神经元的信息，看图片，上方图片是树突学习前的样子，下方图片是同一树突学习和睡觉以后的样子，用白色箭头标记的为新形成的突触，所以睡觉能让你的大脑升级，把之前散乱的，线状的知识织成一整块的记忆。

###2.拖延症

拖延症的产生：当你不想去做一件事的时候，大脑中相关区域的痛苦会被激发出来，为了避免这种痛苦，大脑将注意力转向其他地方。结果是，你只是感到暂时的愉悦，但是事情被拖延了。

如何克服拖延症： -——立即去做！！研究发现，当人们开始做不喜欢的事不久，大脑中痛苦的感觉就消失了！推荐使用番茄工作法:

• concentrate for 25 min
• no interrupts
• focus
• reward

###3.Practice Makes Permanent (熟能生巧）

为什么数学和科学比较难学？
因为数学和科学不能轻易的就被具象化，比如我们要学cow，可以通过一样牛的图片，cow的发音等等，这些都是是实实在在的东西，而数学公式呢？很难找到一个可以具体化的方法，例如图像或者声音。因为这很抽象，不能用人的知觉去感知。所以，就要通过不断的练习来加强神经元的联系。

Neurons become linked together through repeated use. The more abstract something is ,the more important it is to practice in order to bring those ideas into reality for you.
神经元在不断的练习中链接在了一起。越是抽象的知识，越是需要不断的练习。因为练习可以使这些抽象的概念变得更真实具体.

刚开始学习完，神经元之间的联系很弱，经过不断的练习，这些联系会变强。

Practice makes permanents

4.Inroduction to memmory

• working Memmory:工作记忆是你需要立刻有意识的处理的记忆内容。相当电脑的内存。

  过去的研究认为我们人类的工作记忆只有7个块。但是现在研究表明我们的工作记忆只能存储四个信息块。我们可以下意识的把知识组织成整块，所以我们的工作记忆可以存储更多的东西，这个原理就是说：虽然我们的工作内存只有四个块，但是每个块的容量是可变的，只要我们把知识组织为大块，然后我们的工作记忆就能处理越来越大的块。

• Long term memmory：就是硬盘

  长期记忆空间非常大，可以存储更多的内容，但是，长期记忆太多了，他们之间相互层叠，这就使我们提取信息变得困难。
  长期记忆：类似于仓库，有巨大的存储空间，但需要多次练习才能在众多信息中找到你想要的信息。不同的长期记忆储存在大脑的不同区域。研究发现，当第一次将工作记忆转化成长期记忆储存时，需要不断重复这个过程几次，这样能提高日后在你需要的时候找到他的几率。要将记忆转化为长期记忆，用间隔时间重复练习效果更好（类似艾宾浩斯曲线）。即 If you don’t leave time for the mortar to dry, that is, time for the synoptic connections to form and strengthen ,you won’t have a good structure.

  6、睡眠的重要性

  在醒着的时候，大脑会产生有害物质（toxic），当睡着的时候，脑细胞与脑细胞之间的间距增大，通过脑中的液体将有害物质从脑细胞的间隙冲走，从而清理掉有害物质。所以睡眠不足意味着你的大脑毒素没有清理干净，毒素会导致你不能清晰地思考。长期睡眠不足还会导致头痛、抑郁、心脏病。糖尿病等。
  在睡觉的时候：①大脑将你正在学习和思考的一些内容和概念更紧密地结合在一起；②将记忆中不太重要的部分抹去，同时（simultaneously）将你想要记住的部分进行强化；③大脑会反复练习学习内容中比较难的部分，这样新的神经元模式会不断加深和强化；④增强理解和解决复杂问题的能力。→ 睡觉时，大脑前额皮质层的意识钝化，这使得大脑的其他部分更容易交流，从而将正在学习的内容进行有序的整合，以利于理解和记忆。SO 在睡前多看正在学习的内容，能在睡梦中更好地理解和强化这些内容。

Logistic Regression 编程实现

[toc]

1. Logistic Regression 介绍

首先阅读一下 Logistic Regression的 wiki页面

关于Logistic Regression的方方面面wiki上总结的很好很强大了，我没有必要再重复。直接记录一下编程实现过程吧。

梯度下降法

当我们把问题转化成了目标函数的最优化问题后，我们就要对目标函数求极小值或者极大值，就要用到最优化理论中的方法，求最小值最常用的就是梯度下降方法。

梯度wiki

梯度是什么？

将一维函数中 微分 概念推广到多维函数中对应的概念就是梯度

假设在笛卡尔坐标系和欧几里得空间的定义内有一个函数$f(x_0,x_1,…,x_n)$，它可微分，并且函数值是标量值，那么这个函数的梯度就是一个 vector，这个vector里存储了$n$个变量的偏导数，即vector (partial_derivatives),如果对应于一元函数$f(x)$，那么梯度就是它的导数$\frac {df(x)} {dx}$

Gradient Decent wiki页面

梯度下降法是一种最优化方法，它是一种迭代算法，选取适当的初始值$x^{(0)}$，迭代的每一步，更新$x$的值，进行目标函数的极小化，直到收敛。由于梯度方向是使目标函数值下降最快的方向，在迭代的每一步，以负梯度方向更新x的值，从而达到减少函数值的目的。

算法描述：

• 输入： 目标函数$f(x)$,梯度函数 $g(x) = \nabla f(x) $,计算精度 $\mathcal{E}$;
• 输出： $f(x)$的极小值点$x^*$

1. 取初值$ x^{(0)} \in R^n $,置 k = 0
2. 计算$ f(x^{(k)} ) $
3. 计算梯度 $ g_k = g( x^{(k)}) $,
   • a) 当$ \left \lVert g_k \right \rVert $ $\lt \mathcal{E} $ 时,停止迭代，令 $ x^* = x ^{(k)}$
   • b) 否则 令$p_k = -g(x^{(k)}）$ ,求 $ \lambda_k $，使得 $$ f(x^{(k)}+\lambda_kpk = \min{\lambda \ge 0 } f(x^{(x)} + \lambda p_k) $$
4. 置 $x^{(k+1)} = x ^{(k)} + \lambda_k p_k$, 计算$f(x^{(k+1)})$
   当$\left \lVert f(x^{(k+1)}) - f(x^{(k)}) \right\rVert \lt \mathcal{E}$ 或者 $ \left\lVert x^{(k+1)}- x^{(k)} \right\rVert \lt \mathcal{E} $的时候，停止迭代，令 $x^* = x^{(k+1)} $
5. 否则，置k = k+1 ,跳转到 3

当目标函数是凸函数的时候，梯度下降法的解是全局最优解，一般情况下，起解部保证是全局最优解，梯度下降法的收敛速度也未必是很快的。

梯度下降编程分类

• “batch” gradient descent 批处理梯度下降
  “ Batch” : each step of gradient descent uses all the training examples.

  每一步计算用到了所有的样本点

• stochastic gradient descent 随机梯度下降

  每一步计算使用一个随机选取的样本点来计算

2. 编程实现过程

数据集选取

编程实现

3. Logistic Resgression 特点总结

• 优点： 计算代价不高，容易实现
• 缺点： 容易欠拟合，分类精度不高
• 适用数据类型： 数值型和标称型数据。

##概念

• 均值
  $$ \mu = \frac1n\sum_i^nx_i $$
  描述样本的典型值或者集中趋势

• 方差
  $$ \sigma^2=\frac1n \sum_i^n(x_i-\mu)^2 $$
  描述样本的分散情况

• 统计显著性(statistically significant)
  若一个直观效应不太可能是由随机因素引起的，就是统计显著的

分布

汇总统计量简单明了，但是风险也大，因为他们很有可能会掩盖数据的真想。另一种方法就是看数据的分布（distribution），它描述了各个值出现的频繁程度。

表示分布最常用的方法是直方图（histogram），这种图用于展示各个值出现的频数或者概率。

在这里，*频数*指的是数据集中一个值出现的次数，*概率*就是频数除以样本数量。    

在python中，计算频数最简单的办法就是用字典。给一个序列t:

1
2
3

hist = {}
for x in t:
    hist[x] = hist.get(x, 0) + 1

得到的结果是一个将值映射到其频数的字典。将其除以 $n$ 即可把频数转换成概率，这称为归一化：

1
2
3
4

n = float(len(t))
pmf = {}
for x, freq in hist.items():
    pmf[x] = freq/n

归一化后的直方图成为PMF(probability Mass Function),概率质量函数，这个函数是值到其概率的映射。

直方图的表示

编写一个Pmf的模块，定义了表示直方图的Hist对象，以及表示PMF的Pmf对象。Pmf.py

1
2
3

import Pmf
hist = Pmf.MakeHistFromList([1,1,1,2])
print hist

绘制直方图

python 中有不少画图的包，可以使用复杂的matplotlib,当然也有简单的seaborn。
　　　　
使用matplotlib中的pyplot画：

1
2
3
4
5
6

import Pmf
from matplotlib import pyplot
hist = Pmf.MakeHistFromList([1,2,2,2,2,2,2,4,4,4,4,5])
vals,freqs = hist.Render()
rectangles = pyplot.bar(vals,freqs)
pyplot.show()

作者写了一个绘制图表的函数myplot.文档：文档.

1
2
3
4
5
6
7
8
9
10
11
12
13

from matplotlib import pyplot
def plotBabiesHist(data_dir='.'):
    table,firsts,others = first.MakeTables(data_dir)
    firsts_l = [p.prglength for p in firsts.records]
    others_l = [p.prglength for p in others.records]
    firsts_h = Pmf.MakeHistFromList(firsts_l)
    others_h = Pmf.MakeHistFromList(others_l)
    fst_v,fst_f = firsts_h.Render()
    oth_v,oth_f = others_h.Render()
    pyplot.bar(fst_v,fst_f)
    pyplot.bar(oth_v,oth_f)
    pyplot.show()

[TOC]

感知器的概念

感知器（perceptron)是人工神经网络的基础单元，感知器是以一个实数值向量作为输入，计算这些输入的线性组合，然后如果结果大于某个阈值，就输出1，否则输出-1.更精确的是，如果输入为$x_1$到$x_n$，那么感知器计算的输出为：
$$
o(x_1,…,x_n) = \begin{cases}
1, & \text{ $w_0+w_1x_1+…+w_nx_n $> 0}\
-1, & \text{otherwise }
\end{cases}
$$

其中，每一个$w_i$是一个实数常量，或者叫做权值(weight),用来决定输入$x_i$对感知器输出的贡献率。
实数$w_0$是一个阈值(threshold)，它是为了使感知器输出1，输入的加权和 $w_0+w_1x_1+…+w_nx_n$必须超过的值。

感知机是一种线性分类模型(非线性的不能分)，属于判别模型，感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合 $\lbrace f \mid f(x) = w \cdot x + b \rbrace$。
感知机有如下几何解释：线性方程
$$ w \cdot x +b = 0 $$
对应于特征空间$R^n$中的一个超平面S,其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为2个部分，每一部分是一类。

公式是这样推导出来的：

$ h(x) = sign((\sum_{i=1}^dw_ixi$) - threashold)
= $sign((\sum{i=1}^dw_ixi$) + (-threashold) $\cdot$ (+1))
= sign(($\sum{i=1}^dw_ix_i$) + $w_0x_0$)
= sign($W^T$X)

感知机的历史

1943年，心理学家 Warren McCulloch 和数理逻辑学家 Walter Pitts 在合作的《A logical calculus of the ideas immanent in nervous activity》 论文中提出并给出了人工神经网络的概念及人工神经元的数学模型，从而开创了人工神经网络研究的时代。1949年，心理学家唐纳德·赫布 在《The Organization of Behavior》论文中描述了神经元学习法则。

人工神经网络更进一步被美国神经学家 Frank Rosenblatt 所发展。他提出了可以模拟人类感知能力的机器，并称之为『感知机』。1957年，在 Cornell 航空实验室中，他成功在IBM 704机上完成了感知机的仿真。两年后，他又成功实现了能够识别一些英文字母、基于感知机的神经计算机——Mark1，并于1960年6月23日，展示与众。

为了『教导』感知机识别图像，Rosenblatt，在 Hebb 学习法则的基础上，发展了一种迭代、试错、类似于人类学习过程的学习算法——感知机学习。除了能够识别出现较多次的字母，感知机也能对不同书写方式的字母图像进行概括和归纳。但是，由于本身的局限，感知机除了那些包含在训练集里的图像以外，不能对受干扰（半遮蔽、不同大小、平移、旋转）的字母图像进行可靠的识别。

首个有关感知机的成果，由 Rosenblatt 于1958年发表在《The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain》 的文章里。1962年，他又出版了《Principles of Neurodynamics: Perceptrons and the theory of brain mechanisms》 一书，向大众深入解释感知机的理论知识及背景假设。此书介绍了一些重要的概念及定理证明，例如感知机收敛定理。

虽然最初被认为有着良好的发展潜能，但感知机最终被证明不能处理诸多的模式识别问题。1969年，Marvin Minsky 和 Seymour Papert 在《Perceptrons》书中，仔细分析了以感知机为代表的单层神经网络系统的功能及局限，证明感知机不能解决简单的异或（XOR）等线性不可分问题，但 Rosenblatt 和 Minsky 及 Papert 等人在当时已经了解到多层神经网络能够解决线性不可分的问题。

由于 Rosenblatt 等人没能够及时推广感知机学习算法到多层神经网络上，又由于《Perceptrons》在研究领域中的巨大影响，及人们对书中论点的误解，造成了人工神经领域发展的长年停滞及低潮，直到人们认识到多层感知机没有单层感知机固有的缺陷及反向传播算法在80年代的提出，才有所恢复。1987年，书中的错误得到了校正，并更名再版为《Perceptrons - Expanded Edition》。

近年，在 Freund 及 Schapire (1998)使用核技巧改进感知机学习算法之后，愈来愈多的人对感知机学习算法产生兴趣。后来的研究表明除了二元分类，感知机也能应用在较复杂、被称为 structured learning 类型的任务上（Collins, 2002），又或使用在分布式计算环境中的大规模机器学习问题上（McDonald, Hall and Mann,2011）。

感知机学习策略

1. 数据集的线性可分性

给定一个数据集，如果存在某个超平面S, $w \cdot x+b$=0能够将数据集的正实例点和负实例点都正确的划分到超平面的两侧，即对所有$y_i=+1的实例i，有wx_i+b >０$，$y_i=－1$的实例i，有
$w \cdot x+b＜０$，就称该数据集是*线性可分的。

2. 感知机学习策略

感知机学习策略是：在假设空间中，选取使损失函数值最小的模型参数（权重w,偏置bias)，即感知机模型。

为什么引入损失函数呢？损失函数又是什么呢？

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面（separating hyperplane),为了找出这样的超平面，即确定感知机模型参数w,b,需要确定一个学习策略，即定义经验损失函数并将损失函数极小化。

损失函数可以选择误分类点的总数，也可以选择误分类点到超平面的距离，由于我们要对这个损失函数进行极小化，极小化最好是连续可导的函数，所以就选择后者，因为误分类点的总数是一个离散的函数，不是连续的。

为此，我们先根据点到平面的距离公式写出输入空间$R^n$中任意一点$x_0$到超平面S的距离：
$$
\frac1{\left\lVert w\right\rVert}\left\lvert w \cdot x +b \right\rvert
$$
这里 $\left\lVert w \right\rVert$ 是 w 的norm范数。

其次，对于误分类的数据($x_i,y_i$)来说,
$$ -y_i(w \cdot x_i +b) \gt 0 $$成立。因为对于误分类的数据来说，$y_i和w \cdot x+b $ 永远异号，所以，误分类点到超平面的距离就是：
$$
-\frac1{\left\lVert w\right\rVert} yi \left( w \cdot x +b \right)
$$
这样，假设超平面S的误分类点集合为 M ,那么所有误分类点到超平面S的总距离为
$$
-\frac1{\left\lVert w\right\rVert} \sum{x_i \in M } yi \left( w \cdot x +b \right)
$$
不考虑 $\frac1{\left\lVert w\right\rVert}$（因为它对所有的训练数据样本都是一样的），就得到了感知机学习的损失函数
$$
L(w,b)=- \sum{x_i \in M }y_i \left( w \cdot x +b \right)
$$
其中 M 为 误分类点的集合。这个损失函数就是感知机学习的 经验风险函数。

显然，损失函数是非负的，如果没有误分类点，那么损失函数的值就是0，误分类点越少，误分类点离超平面越近，损失函数值就越小。 针对一个特定的样本点的损失函数值，在分类正确的时候是0，在误分类的时候是参数w,b的线性函数，因此，损失函数 L(w,b) 是 w,b 的连续可导函数。这样，我们就能用数值积分的优化方法对这个函数进行最优化了。优化的过程就是学习的过程。

感知器学习算法

感知机学习算法的原始形式：
输入：　训练数据集T = {$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$},其中　$x_i \in X = R^n , y_i \in Y = {-1,+1},i=1,2,…,N$ ; 学习率$\eta$ ( 0 < $\eta \le 1$);

输出：　w,b; 感知机模型 $ f(x) = sign( w \cdot x + b) $ ;

1. 选取初始值$ w_0,b_0$
2. 在训练集中随机选取一个数据($ x_i , y_i $)
3. 如果 $ y_i(w \cdot x_i + b) \le 0 $
   $$w \leftarrow w + \eta y_ix_i\ b \leftarrow b + \eta y_i$$
4. 转到2，直到训练集合中没有误分类点

这种学习算法直观上有如下解释： 当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整w,b的值，使得分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。

感知机学习算法由于采用不同的初值或者选取不同的误分类点，解可以不同。

梯度下降

• 首先，对每一条数据进行计算　，求出符号
• 然后如果求出的符号和真实的符号不相等，就要修正错误
• 如何修正错误
  • 看右上方y=+1的图，正确的是正的，却算出来负的，说明w 和 x的夹角太大，要把w转向x，因为此时y=+1所以w+yx是　w+x，相当于图中的中间那条向量；
  • 再看y=-1的图，正确的是负的，但是算出来是正的，说明w和x的夹角太小了，要把w向远离x的方向转，此时w+yx=w-x，所以结果就转向远离x的方向了。

算法代码仿真

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
49
50
51
52
53

import os
# set the initial data
data_set = [[(3,3),1],[(4,3),1],[(1,1),-1]]
w = [i-i for i in range(len(data_set)-1)]
b = 0
rate = 1
# update parameters using stochastic gradient descent,define the cost function
def cost_function(item):
  global w,b
  y = item[1]
  x = item[0]
  # get the inner product of w and x
  inner_product = 0.0
  for i in range(len(w)-1):
    inner_product += w[i]*x[i]
  res = y*(inner_product+b)
  return res
# define the update strategy
def update(item):
  global w,b,rate
  y = item[1]
  x = item[0]
  for i in range(len(w)-1):
    w[i] = w[i] + rate*y*x[i]
  # b is the bias
  b = b + rate*y
# check if there is still mis-classified item
def check(data_set,exist_mis):
  for item in data_set:
    if cost_function(item) <= 0:
      update(item)
      exist_mis = True
    if exist_mis == False:
      print 'Result w : ',str(w),' b: ',str(b)
      os._exit(0)
def learn(data_set):
  global w,b
  for turn in range(1000): # iterator 1000 times
    exist_mis= False
    check(data_set,exist_mis)
    exist_mis = False
  print 'the dataset is no linear separatable'
if __name__=='__main__':
  learn(data_set)

[TOC]

机器学习如何学习

机器学习是一门理论和实践相结合的科目

• 理论导向
  • derive everything deeply for solid understanding
  • 不关心普罗大众

• 技术导向

  • flash over the sexiest techniques broadly for shiny coverage.
  • 有太多技术，很难选择，很难正确的使用到合适的场景

  所以纯粹死学理论和不钻研理论只学花哨的技术都不合适，我们要从机器学习的本质基础学起。

  • 要学习关键理论，关键技术，实践中的用法
  • 学习每个机器学习者都必须掌握的东西

从学习到机器学习

• 学习：acquiring skill with experience accumulated from abservations 从观察积累的知识出发学习技能

  观察 —> Learning —-> skill

• 机器学习：aquiring skill with experience accumulated/computed from data;

  data —-> ML ——> skill

• Skill : improve some performance measure ( e.g. prediction accuracy)

  data —-> ML —–> improved performance measure
  机器学习就是从数据出发，学习到技巧，从而对现有方案有促进提高

• 机器可学习的场景

  • 存在需要被学习的模式
  • 但是没有可以很容易的对模式定义的数学描述
  • 并且存在关于该模式的大量数据

机器学习的例子

1. food：从社交网络上挖掘文本和位置信息，学习餐厅的卫生状况对健康的影响
2. Clothing: 用销售数据和客户调查数据来给客户进行穿衣搭配的推荐
3. Housing: 从建筑特征和能耗负载数据来预测建筑的能耗
4. 行：自动驾驶

机器学习和其他领域的关系

机器学习和数据挖掘

• 机器学习：用数据去算出一个和目标函数很接近的假设函数
• 数据挖掘：用大量数据去找到数据里面有用有趣的性质，关联等
  • 如果把数据挖掘的目标限制为找到一个和目标函数很接近的假设函数的话，那么机器学习和数据挖掘没什么本质的不同，他们目标是一致的。
  • 但是数据挖掘的目标并不总是这样，如果interesting property和’hypothesis that approximate target是相关的，那么 数据挖掘 可以帮助机器学习，并且反过来也一样（vice versa)
  • 传统的数据挖掘同样也关注在大数据库里实现高效的计算
• 他们非常相像，但是不完全相同

机器学习和人工智能

• 机器学习： use data to compute hypothesis g that approximates target f
• 人工智能：compute something that shows intelligent behavior。

  * 如果把机器学习要学习的目标函数的功能限定为，这个函数可以让计算机实现智能化的行为（自动驾驶），那么机器学习和人工智能就是相同的。
  * 但是实现智能的途径不只有机器学习一种。
  

机器学习和统计学

• Statistics : use data to make inference about an unknown process
• g is an inference outcome; f is something unknown ; statistics can be used to achieve ML
• 传统的统计学同样也专注于证明数学假设，但是不关心如何计算
• 机器学习用到的许多工具很早就在统计学里面出现了，所以统计学为机器学习提供了有力的工具

机器学习的组成部分

基本符号

• input: x$\in$X
• output: y $\in$ Y
• unknown pattern to be learned $\Leftarrow\Rightarrow$ target function: f: X$\rightarrow$Y
• data $\Leftarrow\Rightarrow$ training examples
• hypothesis $\Leftarrow\Rightarrow$ skill with hopefully good performance: g: X $\rightarrow$ Y
  

##参考资料
經典文獻
F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386-408, 1958. (第二講：Perceptron 的出處)

W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. (第四講：Hoeffding’s Inequality)

Y. S. Abu-Mostafa, X. Song , A. Nicholson, M. Magdon-ismail. The bin model, 1995. (第四講：bin model 的出處)

V. Vapnik. The nature of statistical learning theory, 2nd edition, 2000. (第五到八講：VC dimension 與 VC bound 的完整數學推導及延伸)

Y. S. Abu-Mostafa. The Vapnik-Chervonenkis dimension: information versus complexity in learning. Neural Computation, 1(3):312-317, 1989. (第七講：VC Dimension 的概念與重要性)

參考文獻
A. Sadilek, S. Brennan, H. Kautz, and V. Silenzio. nEmesis: Which restaurants should you avoid today? First AAAI Conference on Human Computation and Crowdsourcing, 2013. (第一講：ML 在「食」的應用)

Y. S. Abu-Mostafa. Machines that think for themselves. Scientific American, 289(7):78-81, 2012. (第一講：ML 在「衣」的應用)

A. Tsanas, A. Xifara. Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy and Buildings, 49: 560-567, 2012. (第一講：ML 在「住」的應用)

J. Stallkamp, M. Schlipsing, J. Salmen, C. Igel. Introduction to the special issue on machine learning for traffic sign recognition. IEEE Transactions on Intelligent Transportation Systems 13(4): 1481-1483, 2012. (第一講：ML 在「行」的應用)

R. Bell, J. Bennett, Y. Koren, and C. Volinsky. The million dollar programming prize. IEEE Spectrum, 46(5):29-33, 2009. (第一講：Netflix 大賽)

S. I. Gallant. Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, 1(2):179-191, 1990. (第二講：pocket 的出處，注意到實際的 pocket 演算法比我們介紹的要複雜)

R. Xu, D. Wunsch II. Survey of clustering algorithms. IEEE Transactions on Neural Networks 16(3), 645-678, 2005. (第三講：Clustering)

X. Zhu. Semi-supervised learning literature survey. University of Wisconsin Madison, 2008. (第三講：Semi-supervised)

Z. Ghahramani. Unsupervised learning. In Advanced Lectures in Machine Learning (MLSS ’03), pages 72–112, 2004. (第三講：Unsupervised)

L. Kaelbling, M. Littman, A. Moore. reinforcement learning: a survey. Journal of Artificial Intelligence Research, 4: 237-285. (第三講：Reinforcement)

A. Blum. On-Line algorithms in machine learning. Carnegie Mellon University,1998. (第三講：Online)

B. Settles. Active learning literature survey. University of Wisconsin Madison, 2010. (第三講：Active)

D. Wolpert. The lack of a priori distinctions between learning algorithms. Neural Computation, 8(7): 1341-1390. (第四講：No free lunch 的正式版)

T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, 14(3):326–334, 1965. (第五到六講：Growth Function)

B. Zadrozny, J. Langford, N. Abe. Cost sensitive learning by cost-proportionate example weighting. IEEE International Conference on Data Mining, 2003. (第八講：Weighted Classification)

G. Sever, A. Lee. Linear Regression Analysis, 2nd Edition, Wiley, 2003. (第九講：Linear Regression

由統計學的角度來分析；第十二到十三講：Polynomial Transform 後再做 Linear Regression)

D. C. Hoaglin, R. E. Welsch. The hat matrix in regression and ANOVA. American Statistician, 32:17–22, 1978. (第九講：Linear Regression 的 Hat Matrix)

D. W. Hosmer, Jr., S. Lemeshow, R. X. Sturdivant. Applied Logistic Regression, 3rd Edition, Wiley, 2013 (第十講：Logistic Regression 由統計學的角度來分析)

T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. International Conference on Machine Learning, (第十一講：Stochastic Gradient Descent 用在線性模型的理論分析)

R. Rifkin, A. Klautau. In Defense of One-Vs-All Classification. Journal of Machine Learning Research, 5: 101-141, 2004. (第十一講：One-versus-all)

J. Fürnkranz. Round Robin Classification. Journal of Machine Learning Research, 2: 721-747, 2002. (第十一講：One-versus-one)

L. Li, H.-T. Lin. Optimizing 0/1 loss for perceptrons by random coordinate descent. In Proceedings of the 2007 International Joint Conference on Neural Networks (IJCNN ’07), pages 749–754, 2007. (第十一講：一個由最佳化角度出發的 Perceptron Algorithm)
G.-X. Yuan, C.-H. Ho, C.-J. Lin. Recent advances of large-scale linear classification. Proceedings of IEEE, 2012. (第十一講：更先進的線性分類方法)

Y.-W. Chang, C.-J. Hsieh, K.-W. Chang, M. Ringgaard, C.-J. Lin. Training and testing low-degree polynomial data mappings via linear SVM. Journal of Machine Learning Research, 11(2010), 1471-1490. (第十二講：一個使用多項式轉換加上線性分類模型的方法)
M. Magdon-Ismail, A. Nicholson, Y. S. Abu-Mostafa. Learning in the presence of noise. In Intelligent Signal Processing. IEEE Press, 2001. (第十三講：Noise 和 Learning)

A. Neumaier, Solving ill-conditioned and singular linear systems: A tutorial on regularization, SIAM Review 40 (1998), 636-666. (第十四講：Regularization)

T. Poggio, S. Smale. The mathematics of learning: Dealing with data. Notices of the American Mathematical Society, 50(5):537–544, 2003. (第十四講：Regularization)

P. Burman. A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods. Biometrika, 76(3): 503–514, 1989. (第十五講：Cross Validation)

R. Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In Proceedings of the 14th International Joint Conference on Artificial intelligence (IJCAI ’95), volume 2, 1137–1143, 1995. (第十五講：Cross Validation)
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377–380, 1987. (第十六講：Occam’s Razor)

本文要介绍一些高效的数据挖掘方法：

• The Downward Closure Property of Frequent Patterns
• The Apriori Algorithm
• Extensions or Improvements of Apriori
• Mining Frequent Patterns by Exploring Vertical Data Format
• FPGrowth: A Frequent Pattern-Growth Approach
• Mining Closed Patterns

The Downward Closure Property of Frequent Patterns : Aprior

首先先介绍一个概念：Frequent Pattern 的Downward Closure 性质 （这个性质应该叫做向下封闭性质吗？what ever..who cares）

狄仁杰大人说：我们先观察，从上一节里面的例子中我们可以观察到 频繁集: {$a1,…,a{50}$} 有很多 子集 ，所有的这些子集也是Frequent的！（元芳!What’s your opinion ?　大人！这背后必有一个惊天的大秘密！！！我们可以一起搞个大新闻！Excited!）

元芳和大人通过观察发现：
如果 {beer,diaper,nuts} 是频繁的，那么 它的子集{beer,diaper}也是频繁的
因为每当出现 {beer,diaper,nuts}的时候，{beer,diaper}也都出现了！（这么奇妙，你每次吃了一碗米饭的时候，你都吃过了一粒米）

The Apriori Algorithm

于是敌人节大人和元芳就穿越到1994年，化身为Rakesh Agrawal 和 Srikant,在VLDB发表了论文说：

• Aprior: Any subset of a frequent itemset must be frequent

这个定理怎么用呢？元芳你怎么看？大人！反着看！这是一把剪枝的好剪刀！，如果任何一个 Itemset S的子集不是频繁的，那么S也不可能频繁，我们就不需要再去挖掘S了，多么痛的领悟！

后来人们基于这个想法，又探索出了2个主要的方法：

• Aprior
• Eclat
• FPgrowth

Apriori wiki 页面

Aprior算法可以用伪代码表示如下：

Wiki上这么说的：

• a transaction database $T$
• a support threshold of $\epsilon$
• $C_k$ is the candidate set for level $k$
• $count[c]$ accesses a field of the data structure that represents candidate set $c$存着support

下面就上面这个伪代码进行解读：

• $L_1$$\leftarrow$ $\lbrace large 1-itemsets \rbrace$

  • 这行是初始化让第一层的frequent set是 1-itemsets

• while $L_{k-1}$ $\neq$ $\emptyset$

  • 这行是说当上一层的frequent sets是空的时候就结束搜索

• $Ck \leftarrow \lbrace a\cup\lbrace b\rbrace \mid a \in L{k-1} \land b \in \bigcup{L_{k-1} \land b \notin a} \rbrace $

  • 这行是用来生成侯选集的
  • 侯选集是从上一层的频繁集$L{k-1}$中选一个子集 $a \in L{k-1}$，然后再从上一层的频繁集$\bigcup L_{k-1}$中选出一个不在a中($ b \notin a$)的元素 $ b $,然后生成一个itemset : $a \cup \lbrace b \rbrace$ 作为新的侯选集中的一个元素。

• for transactions t $ \in T $ 对每一条 transaction

  • $C_t \leftarrow \lbrace c \mid c \in C_k \land c \subseteq t \rbrace$ 选出这条transaction 中属于侯选集 $C_k$ 的 每个item
  • count[c] $\leftarrow $ count[c] + 1 把每个item的 support count 加 1

• $L_k \leftarrow \lbrace c \mid c \in C_k \land count[c] \ge \epsilon \rbrace $ 把侯选集中的support大于阈值minsup的选itemset选出来，作为下一层的 frequent itemset

• return $ \bigcup_k L_k $ 返回所有的 频繁集

下面这是一个直观的例子

实现的技巧

• 如何生成侯选集呢？
  • 首先，$F_k$和自己求并集
  • 然后，剪枝，如何剪枝，如果并集有一个子集不在$F_k$中，就剪枝，例如图中acde的子集cde不在 $F_3$中，所以被剪掉了

WIKI 上是这么说的:

Apriori uses a “bottom up” approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found.

就是说，Aprior算法用了一种自底向上的方法，从上一层的frequent itemsets中（初始化为frequent-1 itemset set）扩展一个item，生成本层的候选集,然后在数据库中测试生成的候选集中的每个itemset是不是frequent的，把本层的候选集中是frequent的那些选为本层的frequent itemset，直到上一层没有frequent itemset为止，然后就返回所有层的 frequent itemsets；

Extensions or Improvements of Apriori

• 由于database存在磁盘上，所以磁盘访问开销很大，所以要减少数据库访问的次数

  • partioning 方法，这是我们接下来要讲的
  • Dynamic itemset counting(Brin 这个作者吊炸天了！他就是谷歌的创始人之一！发表这个论文的第二年98年他就创办了谷歌)

• 另一种思路是 减少候选集的数量

• 第3种方法是 使用一些特殊的数据结构
  • 我们要用的是一个 FP tree

下面我们就简要看一下第一种方法 Partioning method:

这个方法的发明者观察到了一个非常有趣的现象：TDB中任何一个潜在的频繁集至少在该transaction database 的一个partition里是frequent的；

证明过程是这样的：

1. 首先如果一个itemset X在图中六个partition里面的任何一个里不是frequent的
2. 那么就有 $sup_i$(X) $\lt$ $\sigma$|$TDB_i$| (这是说X的support 小于 sigma 乘以 size($TDB_i$))
   • 这个乘积其实就是阈值 minsup，为什么呢，因为$\sigma$是一个比率，它用来表示在一个itemsets里面满足support大于多少就算是 frequent pattern
3. 最后把每个partition里的support(X)加起来还是小于总共的TDB里的阈值 $\sum_{i=1}^6 SUP_i(X) \lt \sigma |TDB| $
4. 也就是说，它在每一个分区里面都不频繁，那么它在整体里面也不可能频繁，所以，只有在至少一个TDB里面 itemset 是frequent的，它才可能在全集里面frequent；

那么具体怎么实现呢呢？需要两次扫描：

• 第一次： 切分database,怎么切分呢？ Each partition you want them to fit into the main memory.

  • 为什么呢？因为无论你怎么扫描，你不需要进行任何的数据库I/O操作
  • 这样就能生成所有的 local frequent patterns 局部频繁集

• 第二次： 选出全局的global patterns,怎么选呢？

  • 由于每一个分区里面的frequent pattern 很有称为全局frequent pattern的潜在可能
  • 所以第二遍扫描就count each database combos counts of the global candidate set(把每个分区里面的频繁集count求和）有点类似map-reduce的意思；

这样就保证了这种方法只扫描两次数据库；

##直接散列再剪枝法

在生成frequent 1-itemset 的时候，我们可以先为每个transaction 生成所有的frequent 2-itemset ， 把它们都hash到hash表中，并且统计每个bucket 的数量，如果这个数量低于频繁集的阈值，那么这个集合的子集都可以剪枝了。

##Exploring Vertical Data Format

这个和搜索引擎的倒排索引是一个道理！
把数据库中的每一个item想象成切分好的词，然后给这个数据表建立倒排索引，就是图中说的把 horizontal Data format 转换成了 vertical Data format;
用这个 tid-list : 可以方便的生成候选集 ；
比如， t(e) = { $T_10,T_20,T_30$ }; t(a) = { $T_10,T_20$ } ; t(ae) = { $T_10,T_20$ },生成 t(ae)的时候就是用 t(e)和t(a)求交集。对于t(ae)如果其中的任何一个item不是frequent那么t(ae)就不是frequent,t(ae)就可以忽略不计了; 如果t(ae)的两个成员都是frequent,那么判断t(ae)也很简单，就看它的size是多大；

FPGrowth: A Pattern Growth Approach

正如我们看到的，虽然很多时候Aprior生成与测试方法显著地减少了侯选集的大小，使性能得到了很大的提高。但是，这种方法有两种缺点：

• 它仍然需要生成一个海量的侯选集。例如，如果有$10^4$个frequent 1-itemsets ,Aprior算法需要生成至少$10^7$个 candidate 2-itemsets;
• 它需要重复扫描扫描全部数据库，并且要检索巨大的侯选集来进行模式匹配。而且每次需要遍历所有数据项才能确定候选pattern的support count，这样耗费太大了;

所以就有人提出，能不能不生成侯选集就挖掘出频繁集呢？于是，Frequent Pattern growth 算法就应运而生了。
FP-growth算法主要使用了分治法。首先，它吧数据库里的频繁集信息用一种压缩的方式表示，这种数据结构叫做FP-tree（类似字典树）。这棵树保存着itemset的关联信息。然后，它把这个压缩后的数据库分成一组conditional
databases（就是一种特殊的投影数据库）,每个conditional database一个frequent item(或者称之为模式片段）,然后分别挖掘这些conditional databases。对每个模式片段来说，只有和他相关的数据集才需要被检测。因此，这个方法用“让被检测模式growth的方式”切实的减少了需要检索的数据集的数量

FP-growth算法的第一步是：检索数据库一次，生成1-itemset 频繁集，以及统计每个frequent item的support count。然后把频繁集按照support count 从高到低排序；

第二步是生成FP—Tree：先构造一个空的树根root,对每个数据项做下面的操作：
先把每个数据项中的item按照上面的顺序排序，然后选择每一个item，将这个item插入到FP-tree里去 （insert_tree([p|P],T) p是第一个item,P是剩下的item），插入的方法如下：
如果如果这个item跟树中的某个item N 相同，那么就把树中该节点的count+1,否则就生成一个新节点N，并且初始化它的count为1，把它的父节点指针指向T.如果剩下的item不为空的话，就递归的调用insert_tree(P,N);

为了方便树的遍历，还要构建一个item header table，让table中每一个item，指向它在树中出现的每个节点，用链表连起来。
有了这两个数据结构，我们就把挖掘数据库的任务转化成了挖掘FP-tree的任务。

FP-tree是这样挖掘的：

1. 从每一个frequent length 1-pattern （当做一个起始后缀） 开始，把它在树中的所有前缀路径找出来，作为它的conditional pattern base
2. 然后针对每个conditional pattern base 构建相应的conditional FP-tree
   其实conditional这个词在这里我们可以理解成向贝叶斯公式里面的意义，为什么把前缀叫conditional呢，因为当这个后缀发生的时候，它的前缀已经出现了
3. 然后递归的挖掘每个conditional FP-tree。