《数据挖掘导论》总结之分类篇

分类定义

分类任务就是通过学习得到一个目标函数(target function)\(f\),把每个属性集\(x\)映射到一个预先定义的类标号\(y\)。 分类和回归的区别之处就是类标号是否是离散的。回归的目标属性\(y\)是连续的。 分类的一般方法有决策树,基于规则的分类,神经网络,支持向量机和朴素贝叶斯算法。

(改动中-2014年1月24日)

Read More

一般形式的EM算法

问题定义

先给出一般EM算法的问题定义。 给定一个训练集\(X=\{x^{\{1\}},\ldots,x^{\{m\}}\}\)。根据模型的假设,我们希望能够通过这些数据来估计参数\(\theta\),但是每个我们观察到的\(x^{i}\) 还受着一个我们观察不到的隐含变量\(z^{i}\)(也是\(\theta\)生成的)控制,我们记\(Z=\{z^{\{1\}},\ldots,z^{\{m\}}\}\), 整个模型\(p(X,Z|\theta)\)是个关于变量\(X,Z\)的联合分布。

我们通过求最大似然\(L(\theta|X)\)来估计\(\theta\)的值。

\[ \theta=\arg\max_{\theta} L(\theta|X)\]

其中

\[ L(\theta|X)=\ln p(X|\theta)=\ln \sum_{Z}{p(X,Z|\theta)}\]

这里要注意\(p(X|\theta)\)是一个边缘分布,需要通过聚合\(Z\)得到。由于右边的式子在对数函数中又存在加和,所以我们直接对似然求导是没办法得到\(\theta\)的。

这里EM算法可以比较好地解决这个问题。对于EM的一般算法,有从期望的角度解释,用Jensen不等式证明正确性的方法(见参考2)。这里我讲的是另一种从相对熵角度解释,来自PRML的方法。这两种方法各有特定,对比如下:

  • 使用期望的角度来讲,可以地了解EM算法是如何绕过未知\(Z\)下难以计算的问题,即通过最大化它的期望。但是对E和M步如何逼近极大似然的过程,需要对Jensen不等式和单调逼近\(\theta\)最优值过程的理解。

  • 使用相对熵角度解释,可以看清似然函数和它的下界函的迭代增长过程。但是对\(Q(Z)\)和KL散度的引入,以及为什么要最大化下界函数这一点讲的不是很明白(个人看法)。2013年9月25日更新:这里应该是设一个分布Q(z)来近似P(Z),KL散度描述了这两个分布之间的差异,这里只是没有提到下界函数刚好是似然关于后验概率的期望,要求的是下界函数也就是期望的最大值。

Read More

关于二叉树非递归遍历

首先,这里先给出二叉树的节点定义以及递归的二叉树先序遍历:

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
//节点定义
typedef class node
{
public:
node()
{
lchild=NULL;
rchild=NULL;
};
char data;
class node *lchild;
class node *rchild;
//bool isFromRight;//非递归后序遍历用
}BiNode;
//递归先序遍历
void preorder(BiNode* p)
{
if(p==NULL)
return;
cout<<p->data<<" ";//先序遍历
preorder(p->lchild);
//cout<<p->data<<" ";//放在这就是中序遍历
preorder(p->rchild);
//cout<<p->data<<" ";//放在这就是后序遍历
}

下面我们要将先序遍历由递归形式变成非递归形式。按照常理来说,只要模拟递归函数中的隐含的栈操作,就能够把递归变成非递归。所以,二叉树先序遍历的非递归形式应该是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//非递归先序遍历
void iterativePreorderClassical(BiNode* p)
{
stack<BiNode*> s;
if(p!=NULL)
{
s.push(p);
while(!s.empty())
{
p=s.top();
s.pop();
cout<<p->data<<" ";//对V节点的访问已经完成
if(p->rchild!=NULL)
s.push(p->rchild);//先将右子节点压入栈
//cout<data<<endl;//放在这并不能实现中序遍历!
if(p->lchild!=NULL)
s.push(p->lchild);//将左子节点压入栈
//cout<data<<endl;//放在这并不能实现后序遍历!
}
}
}

这里有一个问题,将输出语句放到两个push()操作之间或者之后,能使二叉树遍历形式变成中序或者后序吗?答案是不能。要注意这里对当前节点的访问和两个子节点的压栈操作是同级别的,而子节点的访问必定在下一次循环中,所以对当前节点的访问必定在子节点之前,所以输出不管放哪儿都是先序遍历。

Read More

多项分布概率公式的理解

多项分布是二项分布的推广。二项分布(也叫伯努利分布)的典型例子是扔硬币,硬币正面朝上概率为\(p\), 重复扔\(n\)次硬币,\(k\)次为正面的概率即为一个二项分布概率。而多项分布就像扔骰子,有6个面对应6个不同的点数。二项分布时事件\(X\)只有2种取值,而多项分布的\(X\)有多种取值,多项分布的概率公式为  \[P(X_{1}=x_1,\cdots ,X_{k}=x_{k})= \begin{cases}&\frac{n!}{x_{1}!,\cdots,x_{k}!}p^{x_{1}}\cdots p^{x_{k}}\quad \textrm{when}\sum^{k}_{i=1}{x_{i}=n}\\&0 \qquad\qquad\qquad\qquad\qquad\;\textrm{otherwise.} \end{cases}\]  这个公式看上去像是莫名其妙地冒出来的,想要了解它首先必须要知道组合数学中的多项式定理。

多项式定理:\(n\)是一个正整数时,我们有   \[(x_{1}+x_{2}+\ldots+x_{k})^n=\sum{\frac{n!}{r_1!r_2!\cdots r_k!}x_1^{r_1}\ldots x_k^{r_k}}\]   其中\(r_1+ \ldots + r_k=n,r_i \geq 0\)

Read More