机器学习算法-EW帮帮网

基础概念

监督学习：分类：决策树、临近取样KNN、支持向量机SVM、神经网络算法

回归：线性回归、非线性回归、

非监督学习：用K-mean算法聚类、用hierarchical clustering 算法聚类

决策树（判定树）

1.决策树是一个类似于流程图的树结构。其中，每个内部节点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树节点代表类或类分布。树的最顶层是根节点

如上所示，根节点为((play,9),(don’t,5))然后根据属性往下分，兄弟节点互斥。直到属性不可分，即类似((play,2),(don’t,0))这样

2.熵

一条信息的信息量大小和它的不确定性有直接关系，越是不确定，需要的信息量就越大，即信息量的度量就等于不确定性的大小。

变量的不确定性越大，熵也越大

3.决策树归纳算法

选择属性判断节点

信息获取量：Gain(A)=Info(D)-Info_A(D)

以下图信息为例：

该图有9个yes，5个no

①熵值

②Age列的熵值为：14人中年轻人的概率为5/14，中年人4/14，老年人5/14

而5个年轻人中yes的概率为2/5。

那么，age的信息获取量为：

同理，可以算出，以Income，student，credit_rating的信息获取量

根据信息获取量最大的作为第一个根节点，即age

③

可以得到下面的图

根据age来拆分表，看到age=middle_aged的时候，都是yes，那么可以不用拆了，其他的还是根据步骤②来选择接下来的子节点，直到不可拆

④总结算法

树以代表训练样本的单个节点开始
如果样本都在同一个类，则该节点成为树叶，并用该类标号（类似middle_age情况）
否则，根据信息增益的基于熵的度量作为启发信息，信息获取量最大的属性成为判定属性
所有的属性都是分类的，即，离散的，若是连续的必须离散化（比如，age是从1到17分类的，那么选择比如10作为分界将小于10的分类大于等于10的也分类）
重复1,2,3,4形成判定树
停止条件：

（1）所有样本属于同一个类

（2）没有剩余属性可以用来进一步划分，这时，使用多数表决

5. 树剪枝叶（避免分的太细，在训练集表现好，在测试集表现不好，即overfitting）

（1）先剪枝（即，在一个类中，分到一定程度就不往下分了）

（2）后剪枝（即，先完完全全的建好，然后根据预值剪枝）

6. 决策树的优点和缺点

（1）优点：直观，便于理解，小规模数据集有效

（2）缺点：处理连续变量不好，类别较多时，错误增加的比较快，可规模性一般

7. 应用

（1）数据预处理

在age中有youth、 middle_aged 、senior 三类

则，当age=youth时，为( 1,0,0 ) ，age=middle_aged时，为( 0,1,0 )

featureList = []   #特征值列表

labelList = []



for row in reader:

    labelList.append(row[len(row)-1])

    rowDict = {}

    for i in range(1, len(row)-1):

        rowDict[headers[i]] = row[i]

    featureList.append(rowDict)



print(featureList)   #每一行转化为字典形式,再放到list里面例：[{“age”:”youth”,”income”:”high”,”student”:”no”,...},...]

# Vetorize features

vec = DictVectorizer()

dummyX = vec.fit_transform(featureList) .toarray()

#转化特征值为0,1格式

print("dummyX: " + str(dummyX))

print(vec.get_feature_names())

print("labelList: " + str(labelList))


# vectorize class labels

lb = preprocessing.LabelBinarizer()

dummyY = lb.fit_transform(labelList)

print("dummyY: " + str(dummyY))


# Using decision tree for classification

# clf = tree.DecisionTreeClassifier()

clf = tree.DecisionTreeClassifier(criterion='entropy')

clf = clf.fit(dummyX, dummyY)#参数为dummyX,dummyY

print("clf: " + str(clf))


# Visualize model

with open("allElectronicInformationGainOri.dot", 'w') as f:

    f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)


oneRowX = dummyX[0, :]

print("oneRowX: " + str(oneRowX))


newRowX = oneRowX

newRowX[0] = 1

newRowX[2] = 0

print("newRowX: " + str(newRowX))


predictedY = clf.predict(newRowX)

print("predictedY: " + str(predictedY))

（2）图形化

     dot -Tpng *.dot -o *.png   其中，*为文件名字

KNN

1.以下图电影分类为例

2. 算法描述

（1）为了判断未知实例的类别，以所有已知类别的实例作为参照，选择参数K计算未知实例与所有已知实例的距离，选择最近的K个已知实例，根据少数服从多数的投票法则，让未知实例归类为K个最邻近样本中最多数的类别。（K一般选择奇数）
（2）距离的衡量方法

 其他的衡量方法，余弦值，相关度，曼哈顿距离

（3）算法优缺点

   ①优点：简单、容易实现、通过对K的选择可具备丢噪音数据的健壮性
   ②缺点：需要大量空间存储所有已知实例，算法复杂度高（需要比较所有已知的实例与要分类的实例）、当样本分布不平衡时，容易被归为主导分类

支持向量机SVM

（1）例如画出一条线可以最好的区分两个类，SVM寻找区分两类的超平面（hyper plane），使得边际（margin）最大。即，该线与各类最靠近的两个点的距离和最大，并且该线与两点的距离相同。
（2）线性可区分与线性不可分
    例如上图中，可以画出一条线可以区分这两类点集，则称为线性可区分。
    否则，便为线性不可区分，例如下图。

（3）线性可区分

   ①定义与公式建立

④特性

1.训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生overfitting

2.SVM训练出来的模型完全依赖于支持向量，即使训练集里面所有支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。

3.一个SVM如果训练出的支持向量个数比较少，SVM训练出的模型比较容易被泛华。

（4）线性不可分

①两个步骤来解决

1.利用一个非线性的映射把源数据集中的向量点转化到一个更高维度的空间中

2.在这个维度的空间中找一个线性的超平面来根据线性可分的情况处理

线性回归

（1）统计量：描述数据特征

集中趋势衡量：

①均值（mean）

②中位数（median）

③众数

离散程度衡量

①方差

②标准差

（2）介绍：回归：Y变量为连续数值型，如：房价、人数、降雨量

分类：Y变量为类别型，如：颜色、电脑类别、有无信誉

简单线性回归

（1）介绍

①很多做决定过程通常是根据两个或者多个变量之间的关系

②回归分析用来建立方程模拟两个或者多个变量之间如何关联

③被预测的变量叫做：因变量Y

④被用来进行预测的变量叫做：自变量X

⑤简单线性回归包括一个自变量和一个因变量

⑥以上两个变量的关系用一条直线来模拟

⑦如果包含两个以上的自变量，则称作多元回归分析

介绍一下集成学习方法，GBDT与XGBoost的关系？

集成学习：

Bagging：在Bagging方法中，利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集，在每个数据集上学习出一个模型，最后的预测结果利用N个模型的输出得到，具体地：分类问题采用N个模型预测投票的方式，回归问题采用N个模型预测平均的方式。

Boosting：提升方法（Boosting）是一种可以用来减小监督学习中偏差的机器学习算法。主要也是学习一系列弱分类器，并将其组合为一个强分类器。Boosting中有代表性的是AdaBoost（Adaptive boosting）算法：刚开始训练时对每一个训练例赋相等的权重，然后用该算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在每次学习以后更注意学错的样本，从而得到多个预测函数。

Stacking：Stacking方法是指训练一个模型用于组合其他各个模型。首先我们先训练多个不同的模型，然后把之前训练的各个模型的输出为输入来训练一个模型，以得到一个最终的输出。理论上，Stacking可以表示上面提到的两种Ensemble方法，只要我们采用合适的模型组合策略即可。但在实际中，我们通常使用logistic回归作为组合策略。

Bagging方法与Boosting方法的区别：

1. Bagging中每个训练集互不相关，也就是每个基分类器互不相关，而Boosting中训练集要在上一轮的结果上进行调整，也使得其不能并行计算
2. Bagging中预测函数是均匀平等的，但在Boosting中预测函数是加权的

关系：

①提升树的思想是基于加法模型，不断拟合残差。

②GBDT和Xgboost都是基于提升树的思想。

③GBDT的全称是Gradient Boosting Decision Tree，之所以有Gradient是因为GBDT中引入了梯度作为提升树中“残差”的近似值（提升树的每次迭代都是为了使当前模型拟合残差，就是使求得的增量模型尽可能等于残差）。

④Xgboost可以说是GBDT的一种，因为其也是基于Gradient和Boosting思想，但是和原始GBDT的不同是：Xgboost中引入了二阶导数和正则化，除此之外，Xgboost的作者陈天奇博士在工程实现方面做了大量的优化策略。

逻辑回归是用于回归还是分类？

用于分类。

训练决策树流程

1 T为特征集合，D为训练数据集合；

2 选择一个划分训练数据集效果最好的特征t，并将特征t从特征集T中移除；

3 创建一个树节点，属性为上一步选择的特征t，将训练数据集划分为2个或多个子数据集，每个子数据集作为下一次迭代的训练数据集。

在步骤 3 中，划分得到子数据集，要是已经达到决策树停止生长的条件，则子数据集已经到达叶子节点，无需继续向下划分，而停止生长的条件有很多种，包括：

①对应特征集T中的特征元素数量为零；

②子数据集中数据量过少，已经低于数据集包含数据量的最小值；

③子数据集继续划分得到的信息增益量很小，或子数据集继续划分的熵值很小。

决策树有哪些特征选择依据

信息增益，信息增益比，基尼系数

决策树有哪些优缺点

优点

• 决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。

• 对于决策树，数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。

• 能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。

• 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

• 对缺失值不敏感

• 可以处理不相关特征数据

• 效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

缺点

1)对连续性的字段比较难预测。

2)对有时间顺序的数据，需要很多预处理的工作。

3)当类别太多时，错误可能就会增加的比较快。

4)一般的算法分类的时候，只是根据一个字段来分类。

5)在处理特征关联性比较强的数据时表现得不是太好。

简要阐述boost思想

多个弱分类器的加权平均，可以比得上一个强分类器。三个臭皮匠，顶个诸葛亮。

Svm函数间距和几何间距的区别？

SVM如何用于多分类

一对多法（one-versus-rest,简称1-v-r SVMs）。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

一对一法（one-versus-one,简称1-v-1 SVMs）。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

层次支持向量机（H-SVMs）。层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。

机器学习算法