数据挖掘主要算法.docx

朴素贝叶斯:
有以下几个地方需要注意：
如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类 为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。
计算公式如下：
心网=eg
过程为：
计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离 等）；
对上面所有的距离值进行排序；
选前k个最小距离的样本；
根据这k个样本的标签进行投票，得到最后的分类类别；
如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪 声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取， 比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。
近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法 错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。
注：马氏距离一定要先给出样本集的统计性质，比如均值向量，协方差矩阵等。关于马氏距 离的介绍如下：
马氏距离是由印度统计学家巨哈拉诺比斯（：提出的，表示数据的协方差距离。它是一种有效的t 同的是它考虑到冬种持性之间豹联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联约） 丁测量尺度，充于一个均值为口 =（四1，网，pw，…,岫*,协方差拒降为£；的含变量向号j;=（明，迎？均，...，
Dm⑴ =一闵丁****3—闵
马氏距离也可以定义为两个服从同一分布并且其协方差拒阵为£的随机变量£与廿的差异程度：
4（W y） = 矿）
如具协方差拒阵相单■■立矩阵，马氏距离就简化为欧氏距哀：如果协方差矩降为对角降，其也可称K正成化的欧氏口离。
岖力=\8
其中CT湿也的标准差.
KNN算法的优点：
思想简单，理论成熟，既可以用来做分类也可以用来做回归；
可用于非线性分类；
训练时间复杂度为O（n）；
准确度高，对数据没有假设，对outlier不敏感；
缺点：
计算量大；
样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
需要大量的内存；
SVM :
要学会如何使用libsvm以及一些参数的调节经验，另外需要理清楚svm算法的一些思路：
svm中的最优分类面是对所有样本的几何裕量最大（为什么要选择最大间隔分类器，请
从数学角度上说明？网易深度学****岗位面试过程中有被问到。答案就是几何间隔与样本的误分次
误分次"町
数间存在关系： r ，其中的分母就是样本到分类间隔距离，分子中的R是所有
样本中的最长向量值），即：
S-t. g⑴(u丁:r⑴ + b) > 7, t = 1,. .. ,m || 刎 | = 1-
经过一系列推导可得为优化下面原始目标：
mi】】M
. /)(&'/)+ fr) > 1, i = 1,... j w
I I
：
/(w)
s-i.. 9血j) < 0; i = L .,. ： &
h*出)=0, t = 1,... J.
T<j solvp it. we start }jy dpfliiiiig the g^ti^raliz^d Lagrangian
& i
£() = /(w) +工皿条®) + E目而即).
i=l i=l
可以将1中的优化目标转换为拉格朗日的形式(通过各种对偶优化，KKD条件)，最后目 标函数为：
£(w,&,a) = ^||w||2 - [舟他了抑 + 6) - 1].
我们只需要最小化上述目标函数，其中的a为原始优化问题中的不等式约束拉格朗日系数。
对2中最后的式子分别w和b求导可得：
m
w = ^2 皿 〃")/')■
2=1
而 £(叫"y=°
由上面第1式子可以知道，如果我们优化出了 a,则直接可以求出w 了，即模型的参数搞 定。而上面第2个式子可以作为后续优化的一个约束条件。
对2中最后一个目标函数用对偶优化理论可以转换为优化下面的目标函数:
] m
VF(a)= 由一三(亦).3).
i=l i .j = l
. a, > 0. i = 1,... .m
m
i=l
而这个函数可以用常用的优化方法求得a，进而求得w和b。
按照道理，svm简单理论应该到此结束。不过还是要补充一点，即在预测时有:
wTx + b
m
£ 总舟£0 + k.
1=1
那个尖括号我们可以用核函数代替，这也是svm经常和核函数扯在一起的原因。
，因此原始的目标优化公式为:
此时对应的对偶优化公式为: