EM算法

极大似然估计

Apriori算法

面向问题

关联规则分析

目标：找出频繁项集，和置信度大的关联

  • 支持度：项集出现的频次/总数 （项集：部分元素的集合）
  • 置信度：条件概率

支持度和置信度大于规定值则有关联规则X->Y

穷举过于复杂，因此有Apriori算法。

算法优化方法

频繁项集 前提定理：

  1. 如果一个项集是频繁的，那么其所有的子集（subsets）也一定是频繁的。
  2. 如果一个项集是非频繁的，那么其所有的超集（supersets）也一定是非频繁的。

含代码的文档

PageRank

网页权重排序：根据的是用户最有可能打开网页的概率

假设：

  1. 用户面对一个网站里的n个链接，打开是等概率的（平均）

方法

有对所有的网页的转移概率矩阵H，$p_0$对网页的初始访问概率。

上式为第n次访问到网站的概率，理论上可以用这个来排序。

修改

上式存在一些问题，用户可能不会点网站里的链接而选择重新搜索，无出度的网站问题。因此改进转移概率矩阵：

S用于生成随机矩阵闭包，α表示用户重新搜索的概率。

α越大pageRank方法越强，越小运算量越少，一般去0.85.

动态规划 （Dynamic Programming）

思想：重复的运算就算一次，将结果保留下来

关键：写出状态转移方程

贪心算法

算出局部最优解，来近似全局最优解

C4.5

一种决策树分类策略，同类型的策略有很多。

C4.5将信息熵最小的项作为分类依据。

KNN （K-NearestNeighbor）

在训练集中选取离输入的数据点最近的k个邻居，根据这个k个邻居中出现次数最多的类别（最大表决规则），作为该数据点的类别。

K-means

1
2
3
4
5
选取k个初始质心（作为初始cluster）；
repeat：
    对每个样本点，计算得到距其最近的质心，将其类别标为该质心所对应的cluster；
    重新计算k个cluser对应的质心；
until 质心不再发生变化

和KNN关系：利用近邻信息来标注类别。

CART Classification and Regression Trees

二叉决策树？

AdaBoost

集成学习，针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。

SVM

朴素贝叶斯