lecture 1 introduction to supervised learning
1)expectatin maximization(em) algorithm (期望值最大)
2)linear regression algorithm(线性回归)
3)local weighted regression(局部加权回归)
4)k-nearest neighbor algorithm for regression(回归k近邻)
5)linear classifier(线性分类)
6)perceptron algorithm (线性分类)
7)fisher discriminant analysis or linear discriminant analysis(lda)
8)k-nn algorithm for classifier(分类k近邻)
9)bayesian decision method(贝叶斯决策方法)
lecture 2 feed-forward neural networks and bp algorithm
1)multilayer perceptron(多层感知器)
2)bp algorithm
lecture 3 rudiments of support vector machine
1)support vector machine(支持向量机) (此算法是重点,必考题)
此处有一道必考题。
lecture 4 introduction to decision rule mining
1)decision tree algorithm
2)id3 algorithm
3)c4.5 algorithm
4)粗糙集……
lecture 5 classifier assessment and ensemble methods
1)bagging
2)booting
3)adaboosting
lecture 6 introduction to association rule mining
1)apriori algorithms
2)fp-tree algorithms
lecture 7 introduction to custering analysis
1)k-means algorithms
2)fuzzy c-means algorithms
3)k-mode algorithms
4)dbscan algorithms
lecture 8 basics of feature selection
1)relief algorithms
2)relieff algorithms
3)mrmr algorithms最小冗余最大相关算法。
4)attribute reduction algorithms
比较了几种分类算法性质。(以下两个**来自两篇该领域经典**)
lecture 1 introduction to supervised learning
1)expectatin maximization(em) algorithm (期望值最大)
算法思想:
em算法又称期望最大化算法,是对参数极大似然估计的一种迭代优化策略,它是一种可以从非完整的数据集中对参数进行极大似然估计的算法,应用于缺损数据,截尾数据,带有噪声的非完整数据。
最大期望算法经过两个步骤交替进行计算:
第一步计算期望(e):也就是将隐藏的变量对象能够观察到的一样包含在内,从而计算最大似然的期望值;
另外一步是最大化(m),也就是最大化在e步上找到的最大似然期望值,从而计算参数的似然估计。m步上找到的参数然后用于另一个e步计算。
重复上面2步直至收敛。
优点:1)m步仅涉及完全数据极大似然,通常计算比较简单。
2)收敛是稳定的,因为每次迭代的似然函数是不断增加的。
缺点:1)表现在对缺失数据较多或是多维高斯分布的情形下,计算量大,收敛速度较慢。
2)对于某些特殊的模型,要计算算法中的m步,即完成对似然函数的估计是比较困难的。
3)在某些情况下,要获得em算法中e步的期望显式是非常困难的。
4)em算法的收敛速度,非常依赖初始值的设置,设置不当,计算代价相当大。
5)em算法中的m-step依然是采用求导函数的方法,所以它找到的是极值点,即局
部最优解,而不一定是全局最优解。
改进:针对1)改进:扩大参数空间来加快收敛。
针对2)改进:ecm算法,该算法通过在m步构建计算比较简单的小循环对em
算法进行了改进,从而使期望函数极大化更加容易和有效,从而解决这一问题。
针对3)改进:mcem算法,将e步积分求期望用蒙特卡洛模拟方法来实现,使。
得e步求期望更容易实现。
针对4)初始值的获取可以通过k-means算法,层次聚类算法或是数据数据进行随
机分割,然后重复em效果进行初始点选择。
针对5)结合遗传算法的全局搜索能力,扩大em算法的搜索空间,有效降低em
算法对初始值的依赖度,改善局部最优值的缺陷。
2)linear regression algorithm(线性回归)
算法思想:线性回归(linear regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。
只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。
回归模型:其中和c是未知参数,对于每个训练样本(,)可得到,用来**真实值。损失函数: 即误差值的平方。
1:对于训练集,求取θ,使得损失函数最小。(使用最小二乘法,梯度下降法)
2:对于新输入x,其**输出为θtx
优点:结果易于理解,实现简单,计算简单
缺点:1)对于非线性的数据拟合效果不好(原因:因为线性回归将数据视为线性的,可能出现欠拟合现象,导致结果不能取得最好的**效果)
2)如果训练数据如果有些数据偏差特别大,这回造成最后训练的模型可能对整体数据都不具备很好的准确性
改进:针对2)改进 :局部加权回归。
3)local weighted regression(局部加权回归)
算法思想:给每个待**点周围的点赋予一定的权重,越近的点权重越高,以此来选出该**点对应的数据子集,然后在此数据子集上基于最小均方差进行普通的回归。局部加权回归实质上是对于需要**的点,只是根据其附近的点进行训练,其他的没有改变。
对于局部线性加权算法:
1:对于输入x,找到训练集中与x邻域的训练样本。
2:对于其邻域的训练样本,求取θ,使得其∈x的邻域 )最小。其中w(i)为权重值。
3.**输出为θtx
4.对于新输入,重复1-3过程。
其中 τ 为带宽(bandwidth)常量,距离输入越远,权重越小。
反之越大。优点:1)局部加权回归还是对训练数据拟合的比较好。
2)不太依赖特征的选择,而且只需要用线性模型就能够训练出不错的拟合模型、
缺点:1)计算量较大。(因为局部加权回归的损失数随着**值的不同而不同,这样θ
就无法事先确定,每次**时都需要扫描所有的数据并重新计算θ)
2)局部加权回归容易出现过拟合现象,过拟合现象很明显。
3)关注局部的训练数据,忽略了全局数据,如果**点在出现偏差的训练数据附。
近,那么**值会偏差很大。
改进:4)k-nearest neighbor algorithm for regression(回归k近邻)
算法思想:通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
knn算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成反比。
优点: 1)简单、有效。
2)重新训练的代价较低(类别体系的变化和训练集的变化,在web环境和电子商务应用中是很常见的)。
3)计算时间和空间线性于训练集的规模(在一些场合不算太大)。
4)由于knn方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,knn方法较其他方法更为适合。
5)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
缺点:1)knn在对属性较多的训练样本进行分类时,由于计算量大而使其效率大大降低,效果不是很理想。
2)当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的k个邻居中大容量类的样本占多数。
3)对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域,那**相对比其他稀疏集来说更准确。
4)对k值敏感。
5)维数灾难:临近距离可能被不相干属性主导(因此特征选择问题)
改进:1)分类效率:事先对样本属性进行约简,删除对分类结果影响较小的属性,快速的得出待分类样本的类别。
该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
算法设计与分析学习心得
班级 物联网1201 姓名 刘潇学号 1030612129 1 实验内容 这学期的算法与设计课,老师布置了这四个问题,分别是货郎担问题,动态生成二维数组,对话框下拉列表,排序问题。2 学习掌握 基本程序描述 1 货郎担问题 货郎担问题属于易于描述但难于解决的著名难题之一,至今世界上还有不少人在研究它...
算法和算法的描述
1 1节 1 2节算法和算法的描述。一 教学目标。1 知识与技能。1 了解算法的定义及其表达方法 2 认知流程图的六种基本符号 3 理解计算机解决问题的一般过程。2 方法与过程。1 理解用不同的表达方法描述算法的优缺点 2 掌握用流程图描述简单的算法。3 情感态度和价值观。以生活中的实例引入算法,激...
算法和算法的描述教学设计
算法和算法的描述 教学设计。广东省佛山市南海区第一中学郭小喜。一 教材分析 本节课是高中信息技术选修模块一 算法与程序设计 第一章第二节的内容,主要是一些概念和理论,而算法的概念和理论都太抽象,讲起来非常的枯燥乏味,那么就要把这些抽象的东西变得通俗易懂,使学生能轻松而又愉快的接受并理解。二 学生分析...