划重点

40分简答 60分计算

题型差不多，会改数据

有10分左右的调整空间

聚类

• 概念定义（简答题）一般实现启发式的方法层次方法（重要的是关于距离的定义）纯度的概念

EM算法

• jensen不等式（快速过了）会有一个12分的计算

分类算法

• 概念让你说说分类的场景贝叶斯：基础知识一定要知道的（意思就是肯定考）决策树 信息增益 选择分裂属性改进后面其他的不用看

gamma函数

• 去年有个计算题（一句带过）

beta分布

• 数学推导四个分布（猜测抽一个考）前面四个看，beta太难了（意思是beta不考）

NLP基础

• mekf链，也去熟悉一下会挑一个gram，出计算题tf-idf词袋会考计算隐含dilikelei不考

题目

• em算法 复述优缺点应用统计nlp 任务 代表应用分类的case简答聚类里面挑（kmeans or 层次聚类）em考最大似然估计mle分类考决策树 or k near 邻居x gram

往年卷

简答题

1. 简述聚类的定义，给出两个经典聚类算法。
2. 简述EM算法的原理。
3. 分类中数据集、验证集、测试集的作用和区别。
4. C4.5相比ID3的改进。
5. 给出泊松分布的概率密度函数概率质量函数，描述参数k和 \lambda的含义。
6. 给出正态分布的概率密度函数，以及均值和方差。
7. 给出典型的NLP任务，以及特征应用。
8. 什么是词项-文档矩阵，如何构造？

计算题

1. Kmeans算法，给定一些坐标和两个初始中心点，计算第一次迭代。
2. 给出正态分布的似然函数、最大似然函数，以及求偏导后的极大似然值。
3. 给定先验概率和条件概率，计算朴素贝叶斯算法（要用全概率公式算分母）。
4. Bigram计算句子概率。
5. 词袋模型。

聚类

懒得写了，跟知识仓库的大差不差

纯度： (每个簇的最大类别数之和) / 总样本数，得预先知道真实类别才能算

EM算法

E步骤：Expectation算期望

M步骤：Maximization最大化

分类算法

常用分类方法：SVM bayes KNN 决策树等

贝叶斯

略

ID3（Iterative Dichotomiser 3）

就是决策树用信息增益的那一套，在每个节点，选择信息增益最大的属性进行分裂

计算过程：

• 求系统总熵 H = \sum -plogp
• 对所有属性，求某个属性的 H1
  • 假如属性有2个取值A和B，我们按照A B 先分组数据
  • 现在每个组内，我们视为一个新系统，可以重新计算混乱度Ha Hb
  • H1 = Ha Hb的加权平均
• 求出一堆 H1 H2 H3 H4。
• gain1 = H – H1 gain2 = H – H2 。。。（实际可以不用，直接比较哪个H最小即可）
• 比较gain，取最大的

C4.5

核心思想是使用信息增益率替代信息增益

为什么？就是ID3有局限性呗，如果某个属性取值很多（当然相应的划分很清晰），那他就一定准吗？不一定啊。来个极端情况，假如我用编号（1、2、3）来划分，同时发现1、2、3编号的数据恰好又是不同的类别，这时候按信息增益算，我去，怎么这么好，直接算出log3来了？但是没用啊，这个其实是无效信息。

C4.5干了一件事情：换成信息增益率来衡量，信息增益率 = 信息增益 / 分裂信息。

信息分类太多是有代价的，这个代价我们用分裂信息来衡量

分裂信息是什么？它是属性本身的熵！，就是 \sum – p log p，衡量了关于”这个属性如何划分数据”的熵。分裂信息就是：用这个属性分组有多麻烦？你既然越麻烦，就要给我分得越好，信息收益率就是：考虑分组麻烦程度后的真正收益

新的计算过程：

• 求系统总熵 H = \sum -plogp
• 对所有属性，求某个属性的 H1
  • 假如属性有2个取值A和B，我们按照A B 先分组数据
  • 这个属性有取值A和B，求出“按照A B 先分组数据” 这个划分的熵 H’
  • 现在每个组内，我们视为一个新系统，可以重新计算混乱度Ha Hb
  • H1 = Ha Hb的加权平均
  • rating1 = H1 / H
• 求出一堆 rating1 rating2 rating3 rating4。
• 直接比较哪个rating最小即可

总结，另外要了解克服了两个缺点：

• 用信息增益选择属性时偏向于选择分枝 比较多的属性值，即取值多的属性
• 不能处理连续属性

gamma函数

了解即可

取值为整数时，就是熟悉的阶乘

为了解决 1/2！ = ? 的问题

表达式 ：\Gamma(\alpha) = \int_{0}^{\infty} t^{\alpha-1} e^{-t} dt

性质：\Gamma(\alpha + 1) =\alpha \Gamma(\alpha)

特殊值：\quad \Gamma\left(\frac{1}{2}\right) = \sqrt{\pi}

Beta分布

描述“概率的概率”的分布。A说明天60%概率下雨，B说70%，C说80%，那么下雨的概率到底是多少？这个下雨概率我们也可以用一个函数来衡量，大概是集中在0.7左右，一个跟正态分布差不多的函数图像（差不多的意思是积分后的值也是1，符合概率公理）。

说是太难了，不考应该。稍微记一下：

B(\alpha,\beta) =\frac{\Gamma(\alpha) * \Gamma(\beta)}{\Gamma(\alpha + \beta)}

二项分布

场景：抛n次硬币，求k次正面

P(k) = C(n,k) × p^k × (1-p)^(n-k)

泊松分布

场景：开了一个个人博客，平均每天有两个人来看（x），想知道明天恰好来了三（k）个访客的概率？

两个人（λ），这是唯一需要的参数，

P(k) = (λ^k × e^(-λ)) / k!

推导？二项分布的极限形式。我们把题面变一下：假设世界上有无数人（记为n），所有人都有很小的概率来看我的博客，这个概率是λ/n(虽然我不知道具体多少，但我知道每天会来λ个人)。这样我们就发现泊松分布其实是在极限下的二项分布：有无穷（n）个人，求来3个人的概率。

P(k) = C(n,k) × p^k × (1-p)^(n-k)
     = n*(n-1)*...*(n-k+1) / k! × (λ/n)^k × (1-λ/n)^(n-k)
     = n*(n-1)*...*(n-k+1)/n^k  ×  λ^k/k! × (1-λ/n)^(n-k)
当n→+∞时，有n*(n-1)*...*(n-k+1)/n^k = 1 ，
    且 (1-λ/n)^(n-k) = (1-λ/n)^n = e^-λ
于是
P(k) = λ^k × e^-λ / k!

指数分布

场景：还是个人博客，现在想要回答的是：下一个访客什么时候来的问题。怎么算？

可以从泊松分布推导出来。回到刚刚的题面，我们知道博客每天有两个人来看，这里我们换成更抽象的概念：定义单位时间t（按1天来作为单位时间，这样理解），那我们知道，在t时间内，来的访客人数是2t（λt）。ok了，那我们是不是可以求出t时间内没有人来的概率了（即为k=0）：

生存函数：
S(t) = P(k=0，t) = (λ^k × e^(-λt)) / k! = e^(-λt)

t 时间内有人来的概率就是

累积分布函数CDF:
F(t) =  1 - S(t) = 1 -  e^(-λt)

这就是我们想要的结果啦。

对F(t)求个导就可以得到概率密度函数，即在某时刻来的概率。

概率密度函数PDF:
f(t) = F'(t) = λe^(-λt)

话说为什么这个是叫概率密度函数？尽管每时每刻事件发生的概率都是0，但是在不同的时刻，人来的概率是有大小之分的，这个大小就用概率密度函数来刻画。可以用物理来类比一下：有一根杆子，杆子质量为1，它的长度无限，这个杆子的质量分布很奇特，长度越长的地方质量分布越低，即杆子的密度逐渐降低。那我们知道了，密度就是对这个质量函数求导。同样，概率密度就是对概率函数求导得到。

有个重要的概念：概率密度函数只存在于连续性变量的情形，如指数分布、正态分布，诸如二项分布、泊松分布这种没有概率密度函数，只有概率质量函数（就是P）

正态分布

高中学过了

σ是标准差，μ是中心点
f(x) = (1 / (σ√(2π))) × e^{-(x-μ)²/(2σ²)}

记住这个，应该都会算

NLP基础

自然语言处理要做的事情就是让计算机理解、解释和生成人类语言的技术

典型应用

（会作为考题）

联想一下实际场景写吧。

• 分词
• 命名实体识别
• 情感分析
• 文本分类
• 机器翻译
• 问答
• 文本摘要
• 文本生成

马尔可夫链

核心假设：当前的状态与前面的状态有关，可以由之前的状态推断出现的状态。

P(未来状态 | 现在状态, 过去所有状态) = P(未来状态 | 现在状态)

状态转移矩阵：有很多状态ABC，描述了由A状态变为B状态的概率。这个矩阵就是状态转移矩阵

矩阵相乘的含义？假设状态有t0 t1 t2 ，矩阵P如下：

	A	B	C
A	0.1	0.3	0.6
B	0.3	0.5	0.2
C	0.6	0.2	0.2

P每一行表示在已知为状态X的情况下，下次会发生状态Y的可能性。

P²如下:

	A	B	C
A	0.46	0.3	0.24
B	0.3	0.38	0.32
C	0.24	0.32	0.44

怎么理解？直接看A行。假设现在状态为t0，下次状态为t1，下下次为t2.那么P的A行就代表了t1的各个状态发生概率，P²的A行代表了t2的各个状态的发生概率。

n gram

是马尔可夫链的典型场景，会出计算题！！

就是预测下一个词出现的概率，n gram的n代表我看前几个词。

unigram考虑一个词，bigram考虑2个词这样

计算怎么算？以bigram为例，题目应该会给很多个句子，然后：

• 句子有很多词，先做单个词的统计，可能要加上起始符和终止符？
• 对于每两个词，统计它们出现的次数，可以用转移矩阵（例如：根据语料我发现，“我”这个词后面有4次接“是”，2次接“很”，2次接“喜欢”）
• 算转移概率，愉快地乘一乘

BoW

词袋模型

很简单，就是统计所有的词，作为label；每一个句子为一个向量，向量有n维，对应每个词的出现次数。例如“man what can i say ha ha ”“yes i can”“i say yes”，构造如下

	MAN	WHAT	CAN	I	SAY	HA	YES
s1	1	1	1	1	1	2	0
s2	0	0	1	1	0	0	1
s3	0	0	0	1	1	0	1

tf-idf

衡量词语在文本中的重要性，找关键词用的

tf(𝑤) = 单词𝑤在某文本中出现的次数/该文本单词数

idf(𝑤) = log(文本数量/(包含w的文本数量+1) )

tf-idf = tf(𝑤)*idf(𝑤)

反映了该词在该文档中的重要程度。

词项文档矩阵？具体矩阵画出来跟上面有点像，只不过次数换成了tf-idf值，然后横纵翻转一下（因为是词项-文档）

	S1	S2	S3
man	1/7* log(3/2)	0	0
what	1/7* log(3/2)	0	0
can	1/7* log(3/3)=0	1/3* log(3/3)=0	0
i	1/7* log(3/4)	1/3* log(3/4)	1/3* log(3/4)
say	1/7* log(3/3)=0	0	1/3*log(3/3)=0
ha	2/7* log(3/2)	0	0
yes	0	1/3* log(3/3)=0	1/3* log(3/3)=0