Python实现线性判别，参考周志华机器学习第三章
 

 import numpy as np
import matplotlib.pyplot as plt
mat=np.loadtxt('gua.txt')
X1=mat[0:8,1:3]        #好瓜的数据
X0=mat[8:,1:3]         #坏瓜的数据
mean1=np.mean(X1, axis=0)   #计算每一列的平均值
mean0=np.mean(X0,axis=0)
mean1=mean1.reshape(2,1)
mean0=mean0.reshape(2,1)
cov0 = np.cov(X0,rowvar=False)        #坏瓜协方差矩阵
cov1 = np.cov(X1,rowvar=False)        #好瓜协方差矩阵
Sw=cov0+cov1
w=np.dot(Sw**(-1),mean1-mean0)
print(w)
plt.scatter(X0[:,0],X0[:,1],label='0')
plt.scatter(X1[:,0],X1[:,1],label='1')
plt.plot([0,1],[0,-w[0]/w[1]],label='y')
plt.show()

 

 

 很多机器学习分类算法，比如支持向量机（SVM），的介绍都说了假设数据要是线性可分。
 
 如果数据不是线性可分的，我们就必须要采用一些特殊的方法，比如SVM的核技巧把数据转换到更高的维度上，在那个高维空间数据更可能是线性可分的（Cover定理）。
 
 
 
 
 现在的问题是，如何判断数据是线性可分的？
 
 最简单的情况是数据向量是一维二维或者三维的，我们可以把图像画出来，直观上就能看出来。
 
 比如Håvard Geithus网友的图，非常简单就看出两个类的情形下X和O是不是线性可分。
 
 
 
 
 
 
 
 但是数据向量维度一旦变得很高，我们怎么办？
 
 答案是检查凸包（convex hull）是否相交。
 
 
 
 
 什么是凸包呢？
 
 简单说凸包就是一个凸的闭合曲线（曲面），而且它刚好包住了所有的数据。
 
 举个例子，下图的蓝色线就是一个恰好包住所有数据的闭合凸曲线。
 
 
 
 
 
 
 
 知道了什么是凸包，我们就能检查我们的数据是不是线性可分了。
 
 
 以二维的情况为例，如果我们的数据训练集有两类：M+和M-，
 
 当我们画出两个类的凸包，如果两者不重叠，那么两者线性可分，反之则不是线性可分。
 
 下图就是个线性可分的情况。
 
 
 
 
 
 虽然现在我们比直接看数据判断是不是线性可分进了一步，但是好像还是靠画出图来人眼判断，这对高维度数据依然无效。
 
 是这样么？当然不是。
 
 因为判断两个凸包是不是有重叠可以通过判断凸包M+的边和凸包M-的边是否相交来实现，这就无需把凸包画出来了。
 
 
 
 
 如何高效的找到一组数据的凸包？
 
 
 如何高效的判断两个凸包是否重合？
 
 网友Darren Engwirda 给出了很好的建议：
 
简单说，他的建议就是用quickhull算法来
找到
数据的凸包，sweepline算法
判断
凸包边缘是否有相交，两个步骤的复杂度都是O(nlogn)。
其中quickhull已经在软件包qhull(http://www.qhull.org/)实现了。 
 英文原话:There are efficient algorithms that can be used both to find the convex hull (the qhull algorithm is based on an O(nlog(n))quickhull approach I think), and to perform line-line intersection tests for a set of segments (sweepline at  O(nlog(n))), so overall it seems that an efficient O(nlog(n)) algorithm should be possible.
 
 This type of approach should also generalise to general k-way separation tests (where you have k groups of objects) by forming the convex hull and performing the intersection tests for each group.
 
 It should also work in higher dimensions, although the intersection tests would start to become more challenging...
 
 
 
 
 
 
 
 
 
 
 参考链接和图片来源：
 
 更数学的对凸包的定义：http://www.nanshan.edu.cn/lxy/shuxuejm/jiao%20cai/31%E7%AC%AC%E4%B8%89%E5%8D%81%E4%B8%80%E7%AB%A0%20%20%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA.pdf
 
 wikipedia对凸包的介绍：http://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85
 
 Håvard Geithus和Darren Engwirda（以及其他人）的问答：http://stackoverflow.com/questions/9779179/determine-whether-the-two-classes-are-linearly-separable-algorithmically-in-2d
 
 
 
 

学过线性代数都知道，先求出秩，根据秩的大小与向量的阶数比较判断出线性是否相关。求秩matlab用rank函数
 
rank函数格式
 
rank(A)
 
求下列矩阵判断是否线性相关并求出极大无关组
 
 
>> a1=[1 2 2 3]';
>> a2=[1 4 -3 6]';
>> a3=[-2 -6 1 -9]';
>> a4 = [1 4 -1 7]';
>> a5 = [4 8 2 9]';
>> A=[a1,a2,a3,a4,a5];
>> r=rank(A)

r =

     3

>> 
 
然后根据线性代数学科中极大无关组定义将阶梯形矩阵求出来，从右边往做取就行了。
 化为阶梯形矩阵
 
[R,j]=rref(A)
A是矩阵
R是简化后的阶梯形
j是主元
 
>> [R,j]=rref(A)

R =

     1     0    -1     0     4
     0     1    -1     0     3
     0     0     0     1    -3
     0     0     0     0     0


j =

     1     2     4

>> A1=A(:,j)

A1 =

     1     1     1
     2     4     4
     2    -3    -1
     3     6     7

>> 
 
然后从这里就会发现A1就是它的极大线性无关组。

 
 
 

 
(2)   隐藏层Hidden Layer的处理。
 
例如，TensorFlow的可视化图中，输入层x1，x2接收所有的数据，汇聚起来然后在隐藏层的第一层的第一个神经元进行非线性的转换，第一个隐藏层接收的数据是输入层的数据，第二个隐藏层接收的是第一个隐藏层的数据……，在神经元节点进行非线性转换，本节中使用的是Sigmoid函数转换，非线性转换需处理什么内容？这里继续再进行一个循环，循环用于非线性转换的计算，这是非常核心的地方。之前还没有进行计算，只是将数据输入到输入层x1，x2，在隐藏层计算的节点不能为Bias节点，之前隐藏层获得不为Bias节点的方式是跳过了第一个Bias，这个是与我们自研盘古框架相关的。循环内部隐藏层所有的节点，先进行一个判断神经元节点不能是Bias，nodes[j].get_is_bias_unit()必须为False，同时，神经元节点的层次level必须大于0，只有在这种情况下，节点才可能处于隐藏层Hidden Layer，同时过滤掉了Bias的内容。
 
       接下来设置节点的值。循环遍历Weight。例如，TensorFlow的可视化图中，完成了输入层x1，x2的输入以后，如果要计算隐藏层的第一层的第一个神经元的所有Weight，这时涉及一个问题，当前处理的神经元节点是谁？必须把当前处理的神经元节点记录下来。读者如读过Pytorch的源码可能感觉理解比较轻松。要获得目标神经元最快的方式是通过节点的索引ID来获得，对所有节点遍历的时候获取index，获得当前Neuron的ID。例如，获得隐藏层的第一层的第一个神经元，要找所有和它相关的Weight，然后通过Weight找到它所有输入的数据来源。既有Weight，又有输入的数据来源，而输入的数据来源有值，如x1是0，x2是1，就可以进行线性变换和非线性变换的处理，for循环所有Weight，获取到达的目标是第一个隐藏层的第一个神经元。循环的目标是找出所有Weights的目的地，输入层和第一个隐藏层之间有很多Weights，如果Weight的目的地是第一个隐藏层的第一个神经元，这就是我们需要的。通过判断target_index== weights[k].get_to_index()，之前我们设置权重的时候设置目的地的ID（to_index()），例如，TensorFlow的可视化图中，对于第0个Weight，其Weight连接的2个节点是x1和第一个隐藏层的第一个神经元，x1的ID是它的from_index ，第一个隐藏层的第一个神经元是它的to_index()。第一个隐藏层的第一个神经元有2个连接Weights，2个Weights分别有自己的值，输入层的x1，x2也都有自己的值，x1的值是0，x2的值是1，如果Weight的to_index()和当前节点的ID是一样的，接下来是获取它们的值。
 
第一步，首先获取weight本身的值value。第二步，weight权重有一个来源，例如第0个weight关联的节点是x1，x1的值是0，要获取x1的值，需先获得该Weight的来源的Neuron的ID。
 
线性转换
 
获得节点的ID以后，关键是获得这个ID的神经元节点的值，需再次循环遍历，获得该来源Neuron的Value。判断一下from_index 等于nodes[m].get_index()的索引，则获得该ID的Neuron，然后获得该Neuron的具体的Value。例如，TensorFlow的可视化图中，输入层的节点x1，x2，获取它们的值，要么获取0，要么获取1。从输入层的角度，获得第一层输入层的神经元的值，接下来将值进行相乘，设置一个全局变量target_neuron_input，初始值为0，接收上一个层次Layer中所有的和自己相关的神经元节点Neurons和权重Weights的乘积之和。例如，TensorFlow的可视化图中，输入层x1节点和隐藏层的第一个神经元之间的权重的值是0.46，x1节点的值是0，将0乘以0.46；输入层x2节点和隐藏层的第一个神经元之间的权重的值是-0.034，x2节点的值是1，将1乘以-0.034；然后进行累加0*0.46+1*（-0.034）=-0.034，把Weight和相应的Value相乘，然后累加。
 
这样我们就完成了一个非常重要的步骤，即线性处理部分。
 
如图1-25所示，将输入层的数据收集进来（输入层的第1个节点的值是1，第2个节点的值是0，第3个节点的值是1），获取权重及来源的值，然后将它们相乘进行累加。节点值及权重系数乘积的累加计算：（1*3+0*8+1*4）-1 =6。
 

 
                          

 
图 1- 25权重计算
 
回到ForwardPropagation.py代码，这里有个问题：如果找到了来源的神经元，并且获取了神经元的值，然后也知道权重的值，有没有必要循环下去，看其他的神经元？一个权重是一条边，一条边连接2个节点，一旦找到了来源节点，没必要再循环其他的节点，一个Weight只连接一个上一个层次Layer的Neuron，所以不需要继续循环整个神经网络的其它Neurons。因此在代码中进行break。
 
       接下来是本节中最重要的时刻，应用激活函数Sigmoid函数进行非线性转换。
 
 
 
非线性转换
 
例如，TensorFlow的可视化图中，已经获得了输入层节点x1，x2的值，已经把权重和相应的值相乘，然后累加，现在是要设置隐藏层的第一个神经元的值。设置一个变量target_neuron_output为经过非线性转换Non-Linearity后的输出，我们这里使用Sigmoid激活函数。
 
接下来的代码编写，按Tab退格键到if语句下，非线性转换是对前面所有结果的计算，因此，接下来的代码不可能写在break语句下；再按Tab退格键，也不可能是前一个for循环下，因为这里只计算了一个节点的结果；继续按Tab退格键，也不可能是if语句下，因为if语句对应的是一个weight的边，以及源神经元节点的处理；再按一个Tab退格键，和上一个for循环语句对齐，这个时候获取了所有的数据。从和Break语句对齐出发，一共按了4次后退键，第1次和if语句对齐，第2次和for语句对齐，第3次和前一个if语句对齐，第4次和前一个for语句对齐，接下来是要应用Sigmoid激活函数对当前的Neuron的所有的输入累计后的值进行操作。
 
 
 
如图1-26所示，对于Sigmoid函数我们将实现f(x) = 1/(1+                              ))公式，通过代码target_neuron_output= 1 / (1 + math.exp(- target_neuron_input))计算出值，就是神经元节点具体的值。接下来把输入值和当前Neuron采用Sigmoid Activation计算后的值设置进当前的Neuron。
 

 
图 1- 26 Sigmoid激活函数