Java虚拟机

2019-05-26

机器生汇编，汇编生B，B生C，C生万物

JVM 内存区域主要分为线程私有区域【程序计数器、虚拟机栈、本地方法区】、线程共享区域【JAVA 堆、方法区】、直接内存

线程私有数据区域生命周期与线程相同, 依赖用户线程的启动/结束而创建/销毁。

线程共享区域随虚拟机的启动/关闭而创建/销毁。

Java栈(虚拟机栈)

Java线程执行方法的内存模型，一个线程对应一个栈，每个方法在执行的同时都会创建一个栈帧（用于存储局部变量表，操作数栈，动态链接，方法出口等信息）不存在垃圾回收问题，只要线程一结束该栈就释放，生命周期和线程一致。

本地方法栈

登记native方法，在Execution Engine执行时加载本地方法库

程序计数器

就是一个指针，指向方法区中的方法字节码（用来存储指向下一条指令的地址,也即将要执行的指令代码），由执行引擎读取下一条指令，是一个非常小的内存空间，几乎可以忽略不记。

方法区（永久代，Permanent Generation）

类的所有字段和方法字节码，以及一些特殊方法如构造函数，接口代码也在此定义。简单说，所有定义的方法的信息都保存在该区域，静态变量+常量+类信息(构造方法/接口定义)+运行时常量池都存在方法区中，虽然Java虚拟机规范把方法区描述为堆的一个逻辑部分，但是它却有一个别名叫做 Non-Heap（非堆），目的应该是与 Java 堆区分开来。
方法区是JVM规范里的一个概念，HotSpot在JDK7之前使用永久代来实现方法区。GC也不会在主程序运行期对永久区域进行清理。在JDK8中， HotSpots使用元空间取代了永久代。永久代属于堆，元空间属于直接内存。元空间只存储类的元信息，永久代中的静态变量和常量池等并入堆中。

堆（运行时数据区）

虚拟机启动时创建，用于存放对象实例，几乎所有的对象（包含常量池）都在堆上分配内存，当对象无法再该空间申请到内存时将抛出OutOfMemoryError异常。同时也是垃圾收集器管理的主要区域。可通过 -Xmx –Xms 参数来分别指定最大堆和最小堆。堆也是垃圾收集器进行垃圾收集的最重要的内存区域。由于现代 VM 采用分代收集算法, 因此 Java 堆从 GC 的角度还可以细分为: 新生代(Eden区、From Survivor区和 To Survivor区)和老年代。

新生代

是用来存放新生的对象。一般占据堆的 1/3 空间。由于频繁创建对象，所以新生代会频繁触发MinorGC 进行垃圾回收。新生代又分为 Eden 区、ServivorFrom、ServivorTo 三个区。

Eden 区，Java 新对象的出生地。（如果新创建的对象占用内存很大，则直接分配到老年代）。当 Eden 区内存不够的时候就会触发 MinorGC，对新生代区进行一次垃圾回收
ServivorFrom区，上一次 GC 的幸存者，作为这一次 GC 的被扫描者。
ServivorTo区，保留了一次 MinorGC 过程中的幸存者。

MinorGC 的过程（复制->清空->互换）

eden、servicorFrom 复制到 ServicorTo，如果有对象的年龄以及达到了老年的标准，则赋值到老年代区，，同时把这些对象的年龄+1
清空 eden、servicorFrom
ServicorTo 和 ServicorFrom 互换

老年代

主要存放应用程序中生命周期长的内存对象。老年代的对象比较稳定，所以 MajorGC 不会频繁执行。

MajorGC 采用标记清除算法：首先扫描一次所有老年代，标记出存活的对象，然后回收没有标记的对象。MajorGC 的耗时比较长，因为要扫描再回收。当老年代也满了装不下的时候，就会抛出 OOM（Out of Memory）异常。

常量池

Class文件常量池
运行时常量池
字符串常量池

堆、栈和方法区

堆

存储的是对象，每个对象都包含一个与之对应的class
JVM只有一个堆区(heap)被所有线程共享，堆中不存放基本类型和对象引用，只存放对象本身
对象由垃圾回收器负责回收，因此大小和生命周期不需要确定

栈

每个线程包含一个栈区，栈中只保存基础数据类型的对象和自定义对象的引用(不是对象)
每个栈中的数据(原始类型和对象引用)都是私有的
栈分为3个部分：基本类型变量区、执行环境上下文、操作指令区(存放操作指令)
数据大小和生命周期是可以确定的，当没有引用指向数据时，这个数据就会自动消失

方法区

静态区，跟堆一样，被所有的线程共享
方法区中包含的都是在整个程序中永远唯一的元素，如class，static变量

展开全文 >>

机器学习（6）支持向量机

2019-02-22

一、支持向量机

支持向量机(Support Vector Machines，SVM)，是现成最好的分类器。SVM有很多实现算法，如序列最小优化（Sequential Minimal Optimization，SMO）算法。

基于最大间隔分隔数据

将数据集分隔开来的直线称为分隔超平面(separating hyperplane)。分隔二维平面，分隔超平面是一条直线。当数据集是N维的，就是用来分隔的N-1维的对象被称为超平面。

我们把这些数据点到分隔面的距离称为间隔，也就是该点到分隔平面的法线（或垂线）长度。在训练分类器时，希望间隔尽可能的大。

支持向量，就是离分隔超平面最近的那些点，需要试着最大化支持向量到分隔面的距离。

原理推导

为了寻找最大间隔，分隔超平面可以写成w^Tx+b。

点A到分隔超平面的距离为(w^Tx+b)/||w||。

使用了类似单位阶跃函数类似的函数，返回类别标签，值为-1和+1。当数据点处于正方向时，label为+1。当数据点处于负方向是时，label为-1。保证label*(w^Tx+b)仍然是正数。

支持向量(取最近的n个点)的表示如下：

\min_n(label \cdot (w^Tx+b) \cdot \dfrac{1}{||w||})

需要对该间隔最大化，写作

arg max_{(w,b)}{\{min_{(n)}(label \cdot (w^Tx+b) \cdot \dfrac{1}{||w||})\}}

该求解相当困难，加上约束条件label * (w^Tx+b) >=1.0，并使用拉格朗日乘子法，可以将优化目标函数最后写成：(尖括号为内积)

max_{(\alpha)}[\sum_{i=1}^m\alpha - \dfrac{1}{2}\sum_{i,j=1}^mlabel^{(i)} \cdot label^{(j)} \cdot a_i \cdot a_j \langle x^{(i)},x^{(j)} \rangle]

再引入松弛变量C后，约束条件为:

C \ge \alpha \ge 0,\sum_{i-1}^m \cdot label^{(i)}=0

展开全文 >>

机器学习（5）线性回归

2019-02-18

一、线性回归

回归

回归是监督学习的一个重要问题，回归用于预测输入变量和输出变量之间的关系，目的是预测数值型的目标值。
回归模型（回归方程）是表示输入变量到输出变量之间映射的函数。
回归问题的学习等价于函数拟合：使用一条函数曲线使其很好的拟合已知函数且很好的预测未知数据。

回归问题分为模型的学习和预测两个过程。基于给定的训练数据集构建一个模型，根据新的输入数据预测相应的输出。

回归问题按照输入变量的个数可以分为一元回归和多元回归；
按照输入变量和输出变量之间关系的类型，可以分为线性回归和非线性回归。如果你和的线是一条直线，则被称为线性回归。非线性回归有常用的逻辑回归模型。

线性回归

一元线性回归最简单：y=ax+b(x为价格，y为销量，则该线性回归用来描述价格与销量的关系，一元代表输入只有一个维度-价格，求a和b的值)

多元回归，代表输入有多个维度。

可以用最小二乘法，梯度下降法求解线性预测函数的系数

逻辑回归（logistic ）

逻辑回归的模型是一个非线性模型，它本质上又是一个线性回归模型，因为通过sigmoid映射函数（又称逻辑回归函数）关系，转换成线性回归问题来解决。

二、最小二乘法

最小二乘法适用于任意多维度的线性回归参数求解，它可求解出一组最优解，使得对于样本集中的每一个样本，用y=f(x1,x2,…xi,…xn)来预测样本，使得预测值与实际值的方差最小。

模型公式

h_{\theta}(x) = \sum_{i=0}^m{\theta_i x_i}=\theta^T X

θ和X都是列向量。

目标函数（损失函数）

根据最小二乘法定义，目标函数表示是预测值和真实值的差距。

J(\theta) = \dfrac{1}{2} \sum_{i=0}^m (h_{\theta}(x_i)-y_i)^2

直观的理解，为了避免正负抵消，是每个样本值与全体样本值的平均数之差的平方，和方差类似。如通过模型函数推导，较为复杂：

多维参数的数学推导

首先模型函数包含噪音项，根据中心极限定理，满足均值为0的高斯分布

\varepsilon_i \sim N(0,\sigma^2)

有：

\varepsilon_i =y_i-\theta^T x_i

高斯分布表示如下：

p(y_i|x_i;\theta)=\dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}

通过极大似然MLE求得似然函数为所有样本的乘积

L(\theta) = \prod_{i=1}^m p(y_i|x_i;\theta) = \prod_{i=1}^m \dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}

求log，将极大似然最大值转为log函数的最大值，

l(\theta) = \log{L(\theta)} =\log{\prod_{i=1}^m \dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}} = \sum_{i=0}^m \log{\dfrac{1}{\sqrt{2\pi}\sigma}e^{(- \dfrac{(y_i-\theta^T x_i)^2}{2\sigma^2})}}

= m \log{ \dfrac{1}{\sqrt{2\pi}\sigma}} - \dfrac{1}{\sigma^2} \dfrac{1}{2} \sum_{i=0}^m (y_i-\theta^T x_i)^2

要使得最大似然最大，则需要最小二乘最小。有：

J(\theta) = \dfrac{1}{2} \sum_{i=0}^m (h_{\theta}(x_i)-y_i)^2 = \dfrac{1}{2} (X\theta-y)^T(X\theta-y)

得出

\dfrac{dJ(\theta)}{d\theta} = X^T X\theta-X^T y

当矩阵满秩时，求导后取极值点，令函数值为0，得出

\theta = (X^T X)^{-1} X^T y

也可以通过贝叶斯最大后验概率进行推导。

三、线性回归实例

有数据如下，需要计算最优回归系数。

x0-偏移量	x1-x轴	x2-y轴
1.000000	0.067732	3.176513
1.000000	0.427810	3.816464
…	…	…
1.000000	0.995731	4.550095
1.000000	0.738336	4.256571
1.000000	0.981083	4.560815

import numpy as np
import matplotlib.pyplot as plt

def loadDataSet(fileName):
    '''

    :param fileName: 文件名
    :return: dataMat 数据集，labelMat 标签
    '''
    numFeat = len(open(fileName).readline().split('\t')) - 1
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr =[]
        curLine = line.strip().split('\t')
        for i in range(numFeat):
            lineArr.append(float(curLine[i]))
        dataMat.append(lineArr)
        labelMat.append(float(curLine[-1]))
    return dataMat,labelMat

def plotDataSet():
    '''
    绘制数据集
    :return:
    '''
    xArr, yArr = loadDataSet('ex0.txt')                                    #加载数据集
    n = len(xArr)                                                        #数据个数
    xcord = []; ycord = []                                                #样本点
    for i in range(n):
        xcord.append(xArr[i][1]); ycord.append(yArr[i])                    #样本点
    fig = plt.figure()
    ax = fig.add_subplot(111)                                            #添加subplot
    ax.scatter(xcord, ycord, s = 20, c = 'blue',alpha = .5)                #绘制样本点
    plt.title('DataSet')                                                #绘制title
    plt.xlabel('X')
    plt.show()

if __name__ == '__main__':
    plotDataSet()

def standRegres(xArr, yArr):
    '''
    计算回归系数
    :param xArr:数据集
    :param yArr:标签
    :return:
    '''
    xMat = np.mat(xArr);
    yMat = np.mat(yArr).T #T方法为转置
    xTx = xMat.T * xMat  # 根据文中推导的公示计算回归系数
    if np.linalg.det(xTx) == 0.0: #奇异矩阵的性质是，其行列式的值为0
        print("矩阵为奇异矩阵,不能求逆")
        return
    ws = xTx.I * (xMat.T * yMat) # I方法为求逆
    return ws


def plotRegression():
    '''
    绘制回归曲线和数据集
    :return:
    '''
    xArr, yArr = loadDataSet('ex0.txt')  # 加载数据集
    ws = standRegres(xArr, yArr)  # 计算回归系数
    xMat = np.mat(xArr)  # 创建xMat矩阵
    yMat = np.mat(yArr)  # 创建yMat矩阵
    xCopy = xMat.copy()  # 深拷贝xMat矩阵
    xCopy.sort(0)  # 排序
    yHat = xCopy * ws  # 计算对应的y值
    fig = plt.figure()
    ax = fig.add_subplot(111)  # 添加subplot
    ax.plot(xCopy[:, 1], yHat, c='red')  # 绘制回归曲线
    ax.scatter(xMat[:, 1].flatten().A[0], yMat.flatten().A[0], s=20, c='blue', alpha=.5)  # 绘制样本点
    plt.title('DataSet')  # 绘制title
    plt.xlabel('X')
    plt.show()
    
if __name__ == '__main__':
    plotRegression()

求解出的ws回归系数为，用函数表示为：y=3.00774324+1.69532264x

1 2	[[3.00774324] [1.69532264]]

四、局部加权线性回归

定义

局部加权线性回归（Locally Weighted Linear Regression，LWLR），是为了解决线性回归可能出现的欠拟合现象，在该方法中，我们给待预测点附近的每个点赋予一定的权重。形式如下：

\theta = (X^TWX)^{-1} X^TWy

对比之前的公式，区别在于多了W，来给每个点赋予权重。LWLR使用“核”（类似于向量机的核）来对附近的点赋予更高的权重，常用的核是高斯核，k被称为平滑参数，如下：

w(i,i)=exp(\dfrac{|x^{(i)}-x|}{-2k^2})

代码实现

还是之前回归的数据，使用k=1，k=0.01，k=0.003进行局部加权线性回归，

from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
import numpy as np
import linear_regression

def plotlwlrRegression():
    '''
    绘制多条局部加权回归曲线
    :return:
    '''
    font = FontProperties(fname=r"/Library/Fonts/Songti.ttc", size=14)
    xArr, yArr = linear_regression.loadDataSet('ex0.txt')  # 加载数据集
    yHat_1 = lwlrTest(xArr, xArr, yArr, 1.0)  # 根据局部加权线性回归计算yHat
    yHat_2 = lwlrTest(xArr, xArr, yArr, 0.01)  # 根据局部加权线性回归计算yHat
    yHat_3 = lwlrTest(xArr, xArr, yArr, 0.003)  # 根据局部加权线性回归计算yHat
    xMat = np.mat(xArr)  # 创建xMat矩阵
    yMat = np.mat(yArr)  # 创建yMat矩阵
    srtInd = xMat[:, 1].argsort(0)  # 排序，返回索引值
    xSort = xMat[srtInd][:, 0, :]
    fig, axs = plt.subplots(nrows=3, ncols=1, sharex=False, sharey=False, figsize=(10, 8))
    axs[0].plot(xSort[:, 1], yHat_1[srtInd], c='red')  # 绘制回归曲线
    axs[1].plot(xSort[:, 1], yHat_2[srtInd], c='red')  # 绘制回归曲线
    axs[2].plot(xSort[:, 1], yHat_3[srtInd], c='red')  # 绘制回归曲线
    axs[0].scatter(xMat[:, 1].flatten().A[0], yMat.flatten().A[0], s=20, c='blue', alpha=.5)  # 绘制样本点
    axs[1].scatter(xMat[:, 1].flatten().A[0], yMat.flatten().A[0], s=20, c='blue', alpha=.5)  # 绘制样本点
    axs[2].scatter(xMat[:, 1].flatten().A[0], yMat.flatten().A[0], s=20, c='blue', alpha=.5)  # 绘制样本点
    # 设置标题,x轴label,y轴label
    axs0_title_text = axs[0].set_title(u'局部加权回归曲线,k=1.0', FontProperties=font)
    axs1_title_text = axs[1].set_title(u'局部加权回归曲线,k=0.01', FontProperties=font)
    axs2_title_text = axs[2].set_title(u'局部加权回归曲线,k=0.003', FontProperties=font)
    plt.setp(axs0_title_text, size=8, weight='bold', color='red')
    plt.setp(axs1_title_text, size=8, weight='bold', color='red')
    plt.setp(axs2_title_text, size=8, weight='bold', color='red')
    plt.xlabel('X')
    plt.show()

def lwlr(testPoint, xArr, yArr, k=1.0):
    '''
    使用局部加权线性回归计算回归系数w
    :param testPoint: 测试样本点
    :param xArr: 数据集
    :param yArr: 标签y
    :param k: 高斯核的k,自定义参数
    :return: 回归系数
    '''
    xMat = np.mat(xArr);
    yMat = np.mat(yArr).T
    m = np.shape(xMat)[0]
    weights = np.mat(np.eye((m)))  # 创建权重对角矩阵
    for j in range(m):  # 遍历数据集计算每个样本的权重
        diffMat = testPoint - xMat[j, :]
        weights[j, j] = np.exp(diffMat * diffMat.T / (-2.0 * k ** 2))
    xTx = xMat.T * (weights * xMat)
    if np.linalg.det(xTx) == 0.0:
        print("矩阵为奇异矩阵,不能求逆")
        return
    ws = xTx.I * (xMat.T * (weights * yMat))  # 计算回归系数
    return testPoint * ws

def lwlrTest(testArr, xArr, yArr, k=1.0):
    '''
    局部加权线性回归测试
    :param testArr: 测试数据集
    :param xArr: 数据集
    :param yArr: 标签y
    :param k:高斯核的k,自定义参数
    :return:回归系数向量
    '''
    m = np.shape(testArr)[0]  # 计算测试数据集大小
    yHat = np.zeros(m)
    for i in range(m):  # 对每个样本点进行预测
        yHat[i] = lwlr(testArr[i], xArr, yArr, k)
    return yHat

if __name__ == '__main__':
    plotlwlrRegression()

可以看出当k越小（比如k=0.01），拟合效果越好。但是k=0.003时过小，导致考虑了太多噪声，进而导致了过拟合现象。

五、岭回归

上面提到，计算回归参数需要保证X^TX可逆（满秩）。那么如果数据的特征点比样本数还多，那么矩阵X肯定不是满秩矩阵，无法求逆，导致无法使用正常的线性回归。因此统计学家引入岭回归（ridge regression）的概念。

定义

岭回归就是在矩阵X^TX上加一个λI从而使得矩阵非奇异，进而能对X^TX + λI求逆。其中矩阵I是一个m×m的单位矩阵，对角线上元素全为1，其他元素全为0。而λ是一个用户定义的数值。回归系数的计算公式将变成：

\theta = (X^T X + \lambda I)^{-1} X^T y

这里通过引入λ来限制了所有θ之和，通过引入该惩罚项，能减少不重要的参数，这个技术在统计学中叫做缩减(shrinkage)

六、梯度上升和梯度下降

梯度上升（下降）法基于的思想是:要找到某函数的最大（小）值，最好的方法是沿着该函数的梯度方向探寻。函数f(x,y)的梯度由下面公式表示:

\nabla(x,y)=\begin{pmatrix} \dfrac{\partial{f(x,y)}}{\partial{x}} \\ \dfrac{\partial{f(x,y)}}{\partial{y}} \end{pmatrix}

梯度是三维以上坐标系的概念，它在平面坐标系对应的概念是导数。二维平面中，导数代表线的倾斜方向和倾斜程度。三维空间中，梯度代表面的倾斜方向和倾斜程度。线的倾斜方向只用正负表示，导数为正代表右斜，导数为负代表线左斜。面的倾斜方向是无穷的，由向量表示。

梯度上升和梯度下降，指的是你要计算的结果是函数的极大值还是极小值。计算极小值，就用梯度下降，计算极大值，就是梯度上升。

梯度上升

梯度上升的算法如下：

w := w+ \alpha \nabla_w{f(w)}

可以根据简化的二维平面y=-x^2函数来求最大值来理解，当x<0时导数为正，函数值在0时最大。

当取w<0时，导数为正，因此迭代后的w会往右侧（最大值所在的x=0）靠近。
当取w>0时，导数为负，因此迭代后的w会往左侧（最大值所在的x=0）靠近。

梯度下降

梯度下降的算法如下：

w := w- \alpha \nabla_w{f(w)}

可以根据简化的二维平面y=x^2函数来求最小值来理解，当x>0时导数为正，函数值在0时最小。

当取w<0时，导数为负，因此迭代后的w会往右侧（最大值所在的x=0）靠近。
当取w>0时，导数为正，因此迭代后的w会往左侧（最大值所在的x=0）靠近。

当三维甚至多维时，w变成向量。

当矩阵不满秩时，可采用梯度下降算法来求局部最优解的方法。

七、Logistic回归和Sigmoid函数的分类

我们想要的函数应该是，能够接受所有的输入然后预测出类别。例如在两个类的情况下，分类函数能够输出0或1，这种函数称为“海威赛德阶跃函数”，然而这个函数的问题在于，该函数直接在跳跃点从0跳跃到1，这个瞬间的跳跃有点难处理。

\epsilon(t-t_0)=\begin{cases} 1 &\text{if } t>t_0 \\ 0 &\text{if } t<t_0 \end{cases}

幸好有个函数有类似的性质，并且在数据上更容易处理，这就是Sigmoid函数：

g(z)=\dfrac{1}{1+e^{-z}}

该函数的特性为：当x趋近于负无穷时，y趋近于0；当x趋近于正无穷时，y趋近于1；当x= 0时，y=0.5。

回归系数

为了实现Logistic回归分类器，我们可以在每个特征上都乘以一个回归系数，然后把所有的结果值相加，将这个总和代入Sigmoid函数中，进而得到一个范围在0~1之间的数值。任何大于0.5的数据被分入1类，小于0.5被归入0类。所以，Logistic回归也可以被看成是一种概率估计。

什么是回归系数呢？可由下面公式得出

z=w_0x_0+w_1x_1+w_2x_2+...+w_nx_n

向量写法如下，其中向量x是分类器的输入数据，向量w就是回归系数。

z=[x_0,x_1,...,x_n] \begin{bmatrix} w_{1} \\ w_{2} \\ \vdots \\ w_{n} \\ \end{bmatrix} = x w^T

more >>

展开全文 >>

机器学习（4）朴素贝叶斯

2019-02-16

贝叶斯的学习需要概率论的基本知识，条件概率、全概率、加乘法定理、贝叶斯公式等等基础知识可参考博客“数学素养”的“概率论”相关章节。

一、朴素贝叶斯假设和公式

朴素贝叶斯是贝叶斯决策理论的一部分，我们称之为“朴素”(native)，是因为整个形式化过程只做最原始、最简单的假设。朴素贝叶斯分类器中的假设是：

每个特征都是独立的
每个特征同等重要

贝叶斯决策理论的核心思想是，分类时，我们会选择高概率对应的类别，即选择具有最高概率的决策。

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{\sum_{i=1}^n{P(B_i)P(A | B_i)}}

可得到如下形式：

P(A|B)= \dfrac{P(A)P(B|A)}{P(B)}

怎么理解？

P(A)称为”先验概率”（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。
P(A|B)称为”后验概率”（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。
P(B|A)/P(B)称为”可能性函数”（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

所以，条件概率可以理解成下面的式子：

后验概率　＝　先验概率ｘ调整因子

这就是贝叶斯推断的含义。我们先预估一个”先验概率”，然后加入实验结果，看这个实验到底是增强还是削弱了”先验概率”，由此得到更接近事实的”后验概率”。

在这里，如果”可能性函数”P(B|A)/P(B)>1，意味着”先验概率”被增强，事件A的发生的可能性变大；如果”可能性函数”=1，意味着B事件无助于判断事件A的可能性；如果”可能性函数”<1，意味着”先验概率”被削弱，事件A的可能性变小。

二、朴素贝叶斯公式计算实例

为方便理解上述公式，对于规律总结来讲，可写成：

P(规律|现象)=P(现象|规律)P(规律)/P(现象)

对于分类任务来讲，可写成：

P(类别|特征)=P(特征|类别)P(类别)/P(特征)

实例1

有两个碗，1号碗里有30颗水果糖和10块巧克力糖，2号碗里有20颗水果糖和20块巧克力糖。然后把碗盖住。随机选择一个碗，从里面摸出了一颗水果糖。问题：这颗水果糖来自1号碗的概率是多少？

我们希望得到概率P(1号碗|水果糖)，但怎样进行计算并非显而易见。问题如果换成在1号碗中水果糖的概率P(水果糖|1号碗)则简单的多，但可惜的是条件概率并不满足交换律，P(1号碗|水果糖)和P(水果糖|1号碗)并不相同。那么可以使用贝叶斯定理。

P(1号碗|水果糖)=(P(水果糖|1号碗)/P(水果糖))*P(1号碗)

其中两个碗的选择是随机的，P(1号碗)=1/2。
P(水果糖|1号碗)=30颗水果糖/(30颗水果糖和10块巧克力糖)=3/4。
P(水果糖)，可以使用全概率公式计算，其实是1/2 × 30/40 + 1/2 × 20/40=5/8。
可能性函数为(3/4)/(5/8)=6/5

最终得出P(1号碗|水果糖)=1/2 × 6/5 =3/5。

可以看出先验概率为1/2，当有了抓出的是水果糖这个条件后，可能性函数为6/5，使得后验概率提升到了3/5。

实例2

男士的条件会影响到女士是否愿意嫁，数据如下：

样貌	性格	身高	上进心	嫁不嫁
帅	不好	矮	不上进	不嫁
不帅	好	矮	上进	不嫁
帅	好	矮	上进	嫁
不帅	好	高	上进	嫁
帅	不好	矮	上进	不嫁
不帅	不好	矮	不上进	不嫁
帅	好	高	不上进	嫁
不帅	好	高	上进	嫁
帅	好	高	上进	嫁
不帅	不好	高	上进	嫁
帅	好	矮	不上进	不嫁
帅	好	矮	不上进	不嫁

那么有一个男生，四个特点分别是不帅，性格不好，身高矮，不上进，请你判断（分类）一下女生是嫁还是不嫁？

问题可以变为P(嫁|不帅,性格不好,矮,不上进) 和P(不嫁|不帅,性格不好,矮,不上进) 这两个概率哪个高？

根据贝叶斯公式，有以下2个：

1、P(嫁|不帅,性格不好,矮,不上进) = P(嫁) × P(不帅,性格不好,矮,不上进|嫁)/P(不帅,性格不好,矮,不上进)

2、P(不嫁|不帅,性格不好,矮,不上进) = P(不嫁) × P(不帅,性格不好,矮,不上进|不嫁)/P(不帅,性格不好,矮,不上进)

P(嫁)=P(不嫁)=6/12
P(不帅,性格不好,矮,不上进|嫁)这个是联合概率，=P(不帅|嫁) × P(性格不好|嫁) × P(矮|嫁) × P(不上进|嫁)=1/2 × 1/6 × 1/6 × 1/6 =1/432
P(不帅,性格不好,矮,不上进|不嫁)=P(不帅|不嫁) × P(性格不好|不嫁) × P(矮|不嫁) × P(不上进|不嫁)=1/3 × 1/2 × 1 × 2/3 =1/9
P(不帅,性格不好,矮,不上进)套用全概率公式，=P(嫁) × P(不帅,性格不好,矮,不上进|嫁)+ P(嫁) × P(不帅,性格不好,矮,不上进|不嫁)=1/2 × 1/392 + 1/2 × 1/9=49/392

可得出P(嫁|不帅,性格不好,矮,不上进) =(1/432)/(49/432)=1/49，P(不嫁|不帅,性格不好,矮,不上进)==(1/9)/(49/432)=48/49。可以看出不嫁的概率远远大于嫁的概率。

三、关键词过滤分类器的代码实现

以社区留言评论为例，我们要屏蔽侮辱性的言论，所以要构建一个快速过滤器，如果某条留言使用了负面或者侮辱性的语言，那么就将该留言标志为内容不当。过滤这类内容是一个很常见的需求。

准备数据和标签

对此问题建立两个类型：侮辱类和非侮辱类，使用1和0分别表示。

'''
@File    :   bayes.py  
@Version : 1.0  
@Author :   iherr
@Desciption : None
'''

import numpy as np

def loadDataSet():
    '''
    创建数据集和分类
    :return: 数据集和分类
    '''
    postingList = [['my', 'dog', 'has', 'flea', 'problems', 'help', 'please'],
                   ['maybe', 'not', 'take', 'him', 'to', 'dog', 'park', 'stupid'],
                   ['my', 'dalmation', 'is', 'so', 'cute', 'I', 'love', 'him'],
                   ['stop', 'posting', 'stupid', 'worthless', 'garbage'],
                   ['mr', 'licks', 'ate', 'my', 'steak', 'how', 'to', 'stop', 'him'],
                   ['quit', 'buying', 'worthless', 'dog', 'food', 'stupid']] #切分的词条
    classVec = [0, 1, 0, 1, 0, 1]  # 1是侮辱类, 0是非侮辱类
    return postingList, classVec

数据处理

我们把文本看成单词向量或者词条向量，也就是说将句子转换为向量。考虑出现所有文档中的单词，再决定将哪些单词纳入词汇表或者说所要的词汇集合，然后必须要将每一篇文档转换为词汇表上的向量。简单起见，我们先假设已经将本文切分完毕，存放到列表中，并对词汇向量进行分类标注。

more >>

展开全文 >>

机器学习（3）决策树

2019-02-11

一、决策树

决策树(decision tree)是一种基本的分类与回归方法。

分类决策树模型是一种描述对实例进行分类的树形结构。
决策树由结点(node)和有向边(directed edge)组成。
结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

我们可以将决策树转换成if-then规则：由决策树的根结点(root node)到叶结点(leaf node)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

决策树要如何构建呢？通常，这一过程可以概括为3个步骤：

特征选择
决策树的生成
决策树的修剪

二、特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。

通常特征选择的标准是信息增益(information gain)。在划分数据集之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

香农熵

信息论之父克劳德·香农，威廉庞德斯通在05年出版的《财富公式》中这样描述香农：“贝尔实验室和MIT有很多人将香农和爱因斯坦相提并论，而其他人则认为这种对比是不公平的–对香农是不公平的。”

熵本来是个热力学名词，热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。冯诺依曼建议使用“熵”来定义信息的期望值。

待分类的事务可能划分在多个分类之中，则符号 $x_i$ 的信息定义为 $l(x_i)=- \log_2{p(x_i)}$ ，其中 $p(x_i)$ 是选择该分类的概率。

所有类别所有可能值包含的信息期望值，可通过公式得到： $H=- \sum_{i=1}^n{p(x_i) \log_2{p(x_i)}}$ ，其中n是分类的数目，熵越大，随机变量的不确定性就越大。

要说信息为啥定义成这样？不知道，记住用就好。因为我至今也不知道为啥1+1=2。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？浅显的解释就是，这概率是我们根据数据数出来的。我们定义训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类C_k, = 1,2,3,…,K,|C_k|为属于类Ck的样本个数，因此经验熵公式就可以写为:

H(D)=- \sum_{k=1}^K {\dfrac{|C_k|}{|D|} \log_2{\dfrac{|C_k|}{|D|}}}

信息增益

信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

H(Y|X) = \sum_{i=1}^n{p_i H(Y|X=x_i)}

其中，当条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的条件熵称为条件经验熵(empirical conditional entropy)。

p_i = P(X=x_i),i=1,2,...,n

信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g(D,A)=H(D)-H(D|A)

设特征A有n个不同的取值{a1,a2,···,an}，根据特征A的取值将D划分为n个子集{D1,D2，···,Dn}，|Di|为Di的样本个数。记子集Di中属于Ck的样本的集合为Dik，即Dik = Di ∩ Ck，|Dik|为Dik的样本个数。于是经验条件熵的公式：

H(D|A) = \sum_{i=1}^n{\dfrac{|D_i|}{|D|} H(D_i)} = - \sum_{i=1}^n{\dfrac{|D_i|}{|D|} \sum_{k=1}^K {\dfrac{|D_{ik}|}{|D_i|} \lg{\dfrac{|D_{ik}|}{|D_i|}}} }

上面的公式看着头有些晕，下面对概念进行通俗解释，并且找个简单的例子实际计算一下，应该就豁然开朗了。

通俗解释

1、熵：表示一个随机变量的复杂性或者不确定性。

假我要剁手买一件衣服，但是我一直犹豫着要不要买，我决定买这件事的不确定性（熵）为2.5。

2、条件熵：表示在直到某一条件后，某一随机变量的复杂性或不确定性。

我在看了这件衣服的评价后，我决定买衣服这件事的不确定性是1.2。

我在线下实体店试穿衣服后，我决定买衣服这件事的不确定性是0.9。

3、信息增益：表示在知道某一条件后，某一随机变量的不确定性的减少量。

一个是看了网上的评价，此时的信息增益是Gain1=2.5−1.2=1.3。

另一个是线下试穿了衣服，此时的信息增益Gain2=2.5−0.9=1.6。

熵和信息增益实例1

问题背景

对海洋生物的两个特征“不浮出水面是否可以生存”和“是否有脚蹼”，是否属于鱼类。有数据如下：

海洋生物	不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	是	是	是
2	是	是	是
3	是	否	否
4	否	是	否
5	否	是	否

熵的计算

按照定义，整体数据集的经验熵为：-2/5 lg(2/5)- 3/5 lg(3/5)=0.9709505944546686。

如果“是否是鱼类”的结果都是yes或者no，那么可计算得到 -5/5 * lg(5/5)=0。熵为0，变量的不确定性为0，即结果是确定的。

熵的代码实现

'''
trees.py
'''
from math import log

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

import trees

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

if __name__ == '__main__':
    dataSet,label=createDataSet()
    shannonEnt=trees.calcShannonEnt(dataSet)
    print(shannonEnt) #0.9709505944546686

信息增益的计算

设定特征A1-不浮出水面是否可以生存，特征A2-是否有脚蹼。

more >>

展开全文 >>

机器学习（2）k近邻算法

2019-02-05

一、k-近邻

k近邻法(k-nearest neighbor,k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的算法的描述为：

计算测试数据与各个训练数据之间的距离（欧式距离或曼哈顿距离）；
按照距离的递增关系进行排序；
选取距离最小的K个点；
确定前K个点所在类别的出现频率；
返回前K个点中出现频率最高的类别作为测试数据的预测分类。

优点：

精度高
对异常值不敏感
无数据输入假定

缺点：

计算复杂度高
空间复杂度高

二、分类示例1-电影分类

问题背景

根据电影的打斗镜头和接吻镜头，来判定电影类型

电影	打斗镜头	接吻镜头	电影类型
电影1	3	104	爱情片
电影2	2	100	爱情片
电影3	1	81	爱情片
电影4	101	10	动作片
电影5	99	5	动作片
电影6	98	2	动作片
？	18	90	？

采用欧式距离（可理解为直线距离）计算未知电影和已知的距离，当前示例有2个特征，为2维空间，通过计算可得：

电影	与未知电影的距离
电影1	20.5
电影2	18.7
电影3	19.2
电影4	115.3
电影5	117.4
电影6	118.9

假定k=3，则3个靠近的电影依次是电影2、电影3和电影1，这三部电影都是爱情片，则我们判定未知电影是爱情片。

python实现

主要算法实现：kNN.py

'''
kNN: k Nearest Neighbors

Input:      inX: 用于分类的数据 (1xN，测试集)
            dataSet: 用于训练的数据 (MxN，训练集)
            labels: 已知数据集的分类标签 (1xM)
            k: 选择距离最小的k个点
            
Output:     结果-分类标签
'''
from numpy import *

def classify0(inX, dataSet, labels, k):
    #dataSet的行数
    dataSetSize = dataSet.shape[0]
    #tile在列向量方向复制dataSetSize，重复dataSetSize次
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    #二维相减后分别平方
    sqDiffMat = diffMat**2
    #sum(1)为行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方得到欧式距离
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndicies = distances.argsort()     
    classCount={}
    #排序后取k个距离最近的数据
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #降序排列字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    #返回最可能的数据集分类
    return sortedClassCount[0][0]

测试数据集分类

import kNN
import numpy as np

def createDataSet():
    groups = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
    return groups, labels

groups,labels=createDataSet()
result =kNN.classify0([18,90],groups,labels,3)
print(result)

三、分类示例2-男士魅力分类

收集数据

海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以进行如下分类：

没有魅力的人
魅力一般的人
极具魅力的人

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingDataSet.txt中，每个样本数据占据一行，总共有1000行。

海伦收集的样本数据主要包含以下3种特征：

每年获得的飞行常客里程数
玩视频游戏所消耗时间百分比
每周消费的冰淇淋公升数

准备数据

'''
file2matrix: 文件转矩阵

Input:      filename: 文件路径

Output:     returnMat： 数据集
            classLabelVector： 标签向量
'''

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

调用方法将文件转成矩阵

1	datingDataMat,datingLabels = kNN.file2matrix('datingDataSet.txt')

more >>

展开全文 >>

机器学习（1）基础

2019-02-01

一、概论

三大机器学习类别：

监督学习：有标准答案的试错学习。
无监督学习：根据一定的假设寻找数据内部的结构，无监督学习是未来。
强化学习：延迟满足，根据结果来调整行为。和监督学习比，强化学习的反馈是不及时的。

监督学习：

分类
回归

无监督学习：

聚类
密度估计

用于执行分类、回归、聚类和密度估计的机器学习算法：

监督学习的用途：

k-近邻算法
线性回归
朴素贝叶斯算法
局部加权线性回归
支持向量机
Ridge回归
决策树
Lasso最小回归系数估计

无监督学习的用途：

K-均值
最大期望算法
DBSCAN
Parzen窗设计

算法选择：

如果想预测目标变量的值，选择监督学习算法。如目标变量是离散型，选择分类器算法；如果是连续型选择回归算法。

如果不想预测目标变量的值，可选择无监督学习算法。如果只想将数据划分为离散的组，使用聚类算法；如果还需要估计数据与每个分组的相似程度，则使用密度估计算法。

下图是sk-learn对算法选择的总结。

数据标注是第一生产力。

线性回归，根据特征，赋予特征的权重，计算cost代价，检验估算值和正确价格的偏离程度。

代价函数

怎么去寻找

过拟合，追求完美，会导致过拟合。允许一定的误差，增加数据量，将样本分成训练集和测试集，来避免过拟合。

欠拟合，误差太大，比如把树认为树叶。

生活永远是去找次有解，没有最优解

强化学习，马尔科夫决策树

Real trainging pineline
SL network classification （supervised learning）
RL network classification
Evaluation network regressioin

alphago的启示：人工智能的潜力是无限的，但人工智能发挥作用是有条件的：目标明确，规则明确，信息完全。但真实的世界和围棋不一样。

使用机器学习应用程序的步骤：

收集数据
准备输入数据
分析输入数据
训练算法
测试算法
使用算法

一般来说，大部分机器学习都要求：

线性代数：矩阵/张量乘法、求逆，奇异值分解/特征值分解，行列式，范数等

统计与概率：概率分布，独立性与贝叶斯，最大似然(MLE)和最大后验估计(MAP)等

优化：线性优化，非线性优化(凸优化/非凸优化)以及其衍生的求解方法如梯度下降、牛顿法、基因算法和模拟退火等

微积分：偏微分，链式法则，矩阵求导等

信息论、数值理论等

一般人如果想要把这些知识都补全再开始机器学习往往需要很长时间，容易半途而废。而且这些知识是工具不是目的，我们的目标又不是成为运筹学大师。建议在机器学习的过程中哪里不会补哪里，这样更有目的性且耗时更低。

展开全文 >>

一个程序员的数学素养（4）概率论

2018-12-27

一、简介

边缘概率（又称先验概率）：某个事件发生的概率。边缘概率是这样得到的：在联合概率中，把最终结果中那些不需要的事件通过合并成它们的全概率，而消去它们（对离散随机变量用求和得全概率，对连续随机变量用积分得全概率），这称为边缘化（marginalization），比如A的边缘概率表示为P(A)，B的边缘概率表示为P(B)。

联合概率，表示两个事件A和B共同发生的概率，记为P(AB),P(A,B)或P(A ∩ B)。

条件概率（又称后验概率）

条件概率，就是事件A在另外一个事件B已经发生条件下的发生概率，记为P(A | B)，读作“在B条件下A的概率”。根据定义，可得出P(A | B)=P(A ∩ B)/P(B)。

证明：样本空间有N个等可能的基本事件，随机事件A包含M1个事件，B包含M2个事件。设A和B的联合概率包含M个事件（M是M1和M2的共有事件），则P(A ∩ B)=M/N。有P(A|B)=M/M2=M/N / M2/N=P(AB)/P(B)。

实例：100件产品中有5件不合格品，不合格品中又有3件是次品，2件是废品。设A表示“抽到的产品是次品”，B表示“抽到的产品是不合格品”。5件不合格品种有3件次品，则P(A|B)=3/5。P(B)=5/100。
同时是不合格品和次品的联合概率：P(A ∩ B)=3/100。

概率的加法定理：

P(A ∪ B)=P(A)+P(B)-P(A,B)

概率的乘法公式：

P(AB)=P(A)P(B|A)=P(B)P(A|B)

全概率公式

设Ω为实验E的样本空间，B1,B2,…,Bn为一组事件，两两互不相容且并集为全集，则称B1,B2,…,Bn是样本空间Ω的一个划分。且P(Bi)>0，则有公式：

P(A)=\sum_{i=1}^n{P(B_i)P(A | B_i)}

贝叶斯定理（Bayes’ theorem）

根据概率乘法定理，有

P(A)P(B_i|A)=P(B_i)P(A|B_i)

得到

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{P(A)}

再根据全概率公式，得到

P(B_i|A)= \dfrac{P(B_i)P(A|B_i)}{\sum_{i=1}^n{P(B_i)P(A | B_i)}}

怎么理解？

我们把P(B)称为”先验概率”（Prior probability），即在A事件发生之前，我们对B事件概率的一个判断。P(B|A)称为”后验概率”（Posterior probability），即在A事件发生之后，我们对B事件概率的重新评估。P(A|B)/P(A)称为”可能性函数”（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

所以，条件概率可以理解成下面的式子：

后验概率　＝　先验概率ｘ调整因子

在这里，如果”可能性函数”P(A|B)/P(A)>1，意味着”先验概率”被增强，事件A的发生的可能性变大；如果”可能性函数”=1，意味着B事件无助于判断事件A的可能性；如果”可能性函数”<1，意味着”先验概率”被削弱，事件A的可能性变小。

P(规律|现象)=P(现象|规律)P(规律)/P(现象)

展开全文 >>

一个程序员的数学素养（3）线性数学

2018-12-22

一、概论

线性代数，实用，普适性强，比高数更难。

一个问题，一旦无法用线性代数解决的，可能就是无法解决的。非线性的容易进入混沌领域，尽量把非线性问题转换为线性问题。

狭义相对论，洛伦兹变换
电磁场张量
量子力学

二、行列式

定义

n阶行列式，是所有取自不同行不同列的n个元素的乘积的代数和。用τ(j1j2…jn)表示该排列的逆序数，当偶排列时为正。

\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{vmatrix} = \sum_{j_1j_2 \cdots j_n}(-1)^{\tau (j_1j_2 \cdots j_n)}a_{1j_1}a_{2j_2} \cdots a_{nj_n}

行列式性质

转置后值不变
两行（列）互换位置，值变号
某行（列）有公因子k可提出行列式记号外
某行（列）是两个元素的和，可以拆成两个行列式之和
某行（列）的k倍加到另一行（列），值不变
值等于它的任何一行（列）元素，与其对应的代数余子式乘积之和

常用公式

1、上下三角形行列式的值等于主对角线元素的乘积

\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ & a_{22} & \cdots & a_{2n} \\ & & \ddots & \vdots \\ & & & a_{nn} \\ \end{vmatrix}= \begin{vmatrix} a_{11} & & & \\ a_{21} & a_{22} & & \\ \vdots & \vdots & \ddots & \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{vmatrix}= a_{1j_1}a_{2j_2} \cdots a_{nj_n}

2、特殊的拉普拉斯展开式

如果A和B分别是m和n阶矩阵，有

\begin{vmatrix} A & * \\ O & B \\ \end{vmatrix}= \begin{vmatrix} A & O \\ * & B \\ \end{vmatrix}=|A||B|

克莱姆法则（Cramer）

含有n个未知数的n个线性方程组，

\begin{cases} a_{11}x_1 + a_{12}x_2 + ... +a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + ... +a_{2n}x_n = b_2 \\ ...... \\ a_{n1}x_1 + a_{n2}x_2 + ... +a_{nn}x_n = b_n \\ \end{cases}

若线性方程组的系数行列式不为0，

D=\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{vmatrix} \neq 0

则它的解可以用n阶行列式表示

x_1=\dfrac{D_1}{D},x_2=\dfrac{D_2}{D},...,x_n=\dfrac{D_n}{D},

D(j)是将D中的第j列元素换成方程组右端的常数项得到的行列式，即

D_j=\begin{vmatrix} a_{11} & \cdots & a_{1,j-1} & b_1 & a_{1,j+1} & \cdots & a_{1n} \\ a_{21} & \cdots & a_{2,j-1} & b_2 & a_{2,j+1} & \cdots & a_{2n} \\ \vdots & & \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & \cdots & a_{n,j-1} & b_n & a_{n,j+1} & \cdots & a_{nn} \\ \end{vmatrix}

三、矩阵

定义

由m×n个数排成m行n列的数表，称为m行n列矩阵。

A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{bmatrix}

其中， $a_ij$ 表示矩阵第i行第j列的元素，称为矩阵A的(i,j)元。

特殊矩阵

只有一行元素，称为行矩阵
只有一列元素，称为列矩阵
元素都为0，称为零矩阵
行数和列数n相同，称为n阶方阵
n阶方阵主对角线外的元素全部为0，称为对角方阵，如对角线上元素全部为1，称为单位矩阵。

矩阵的运算

设矩阵 $A=(a_{ij})_{m \times s},B=(b_{ij})_{s \times n}$ ，则规定矩阵A与矩阵B的乘积是一个m*n的矩阵 $C=(c_{ij})_{m \times n}$ ，其中

c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+ \cdots + a_{is}b_{sj}= \sum_{k=1}^s a_{ik}b_{kj} (i=1,2,...,m;j=1,2,...,n)

加法是交换律和结合律
数和矩阵相乘有结合律、分配律
矩阵相乘，只有当左矩阵的列数等于右矩阵的行数时才能相乘。没有交换律，有结合律

矩阵的转置

将m×n的矩阵 $A=(a_{ij})_{m \times n}$ 的行换成同序数的列得到的一个n×m矩阵，称为A的转置矩阵，记作 $A^T$

有以下规律:
1、 $(A^T)^T=A$

2、 $(A+B)^T=A^T+B^T$

3、 $(\lambda A)^T=\lambda A^T$

4、 $(AB)^T=B^T A^T$

方阵的行列式

由n阶方阵A的元素构成的行列式，称为方阵A的行列式，记为|A|。

运算规律如下：

1、 $|A^T|=|A|$

2、 $|\lambda ^T|= \lambda^n |A|$

3、 $|AB|= |A||B|$

当方阵的行列式|A|不等于0，称A为非奇异矩阵，否则是奇异矩阵。奇异矩阵的秩不是满秩。

逆矩阵和伴随矩阵

设A为n阶矩阵，若存在另一个n阶矩阵B，使得： AB=BA=E（单位矩阵），则我们称B是A的逆矩阵，而A则被称为可逆矩阵。

设A为n阶矩阵，记

A^*=\begin{bmatrix} A_{11} & A_{21} & \cdots & A_{n1} \\ A_{12} & A_{22} & \cdots & A_{n2} \\ \vdots & \vdots & & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \\ \end{bmatrix}

其中，

A_{ij}

是|A|的元素

a_{ij}

的代数余子式，

A^*

称为A的伴随矩阵。

有 $AA^*=A^T A=|A|E$ ，则n阶方阵A可逆的充分必要条件是|A|不等于0，且有 $A^{-1}=\dfrac{1}{|A|}A^*$

奇异矩阵不可逆。

矩阵的秩

矩阵中的最大的不相关的向量的个数，就叫秩。

设在m×n的矩阵A中，任取k行k列（k<=min{m,n}），位于这些行列交叉处的k^2个元素按照原来次序构成的k阶行列式，称为A的k阶子式。A中有不等于0的r阶子式D，且所有的r+1阶子式（存在的话）全为0，则D称为矩阵A的最高阶非0子式，数r称为矩阵A的秩，记作R(A)。

矩阵的初等变换

有3种变换称为矩阵的初等行（列）变换，初等变换是可逆的

对调矩阵的两行（列）
某一行（列）所有元素乘以数k
把某一行（列）所有元素的k倍加到另一行（列）对应元素上去

矩阵A经过有限次初等行（列）变换变成矩阵B，则称矩阵A与矩阵B行（列）等价。经过有限次行变换或列变换，则称矩阵A与矩阵B等价，记作A~B。

初等矩阵：

由单位矩阵E经过一次初等变换得到的方阵称为初等矩阵。

四、向量组

n个有序的数组成的数组称为n维向量，把n个分量写成一列的形式，称为n维列向量。

a=\begin{pmatrix} a_1 \\ a_2 \\ \cdots \\ a_n \end{pmatrix}

n维行向量：

a^T =(a_1,a_2, \cdots ,a_n)

五、线性空间

线性空间+范数定义=线性赋范空间
线性赋范空间+完备性=Banach空间（巴拿赫空间）
线性空间+内积=内积空间
内积空间+完备性=Hilbert空间（希尔伯特空间）
Hilbert空间+拓宽范数定义=索伯列夫空间

线性空间的8条法则：

设V是一个非空集合，P是一个域。

α+β=β+α，对任意α，β∈V（交换律）
α+(β+γ)=(α+β)+γ，对任意α，β，γ∈V（结合律）
存在一个元素0∈V，对一切α∈V有α+0=α，元素0称为V的零元（零元）
对任一α∈V，都存在β∈V使α+β=0，β称为α的负元素，记为-α（逆元）
对P中单位元1，有1α=α(α∈V)（数乘单位元）
对任意k，l∈P，α∈V有(kl)α=k(lα)（数乘结合律）
对任意k，l∈P，α∈V有(k+l)α=kα+lα（数乘分配律）
对任意k∈P，α，β∈V有k(α+β)=kα+kβ

则称V为域P上的一个线性空间，或向量空间。V中元素称为向量，V的零元称为零向量，P称为线性空间的基域.当P是实数域时，V称为实线性空间.当P是复数域时，V称为复线性空间。

函数f(x)是线性空间。

加法	e	a	b	c
e	e	a	b	c
a	a	a	e	a
b	b	e	b	e
c	c	a	e	c

傅里叶变换：

g(k) = \int_{-\infty}^{+\infty} f(x)e^{-ikx}dx

可逆：

f(x) = \dfrac{1}{2\pi} \int_{-\infty}^{+\infty} g(k)e^{ikx}dk

离散傅里叶变换(Discrete Fourier Transform,缩写为DFT)

展开全文 >>

一个程序员的数学素养（2）高等数学

2018-12-18

一、实数

定义

N-自然数，“数羊”产生
Z-整数，自然数减法不封闭，“借羊”产生
Q-有理数：q/p,其中q和p属于Z。整数的除法不封闭，毕达哥拉斯提出。
R-实数
无理数=实数-有理数
虚数单位i^2=-1，i^3=-i,i^4=1。实数和虚数
复数，实数和虚数合在一起，构成了复数。如a+bi

戴德金分划，全集为Q，分为AB两个集合。A并B为全集，A交B为空集，且A中的任意元素小于B中的任意元素。戴德金分划存在三种情况，

A中存在最大值，且B中不存在最小值。
A中不存在最大值，且B中存在最小值。
A中不存在最大值，且B中不存在最小值。

前两种为有理分划，切到的点是有理数。
第三种为无理分划，切到的点是无理数。

实数的定义：每一个分划，对应一个实数。

稠密性
有序性

引理1：单调有界序列存在极限。

R的元素个数，如等势，则个数相等。

自然数、整数、有理数的势是相同的
实数R的势，和0-1之间的实数的势相同。0-1之间的实数，大于自然数的势。因此，实数R的势大于自然数的势。
单元连续函数的势，大于实数R的势。

无穷大之比较

无穷大从小到大，其中a1,a2,a3大于1

序号	数列
1	$\ln{n}$
2	$n^{1/a_1}$
3	n
4	$n^{a_2}$
5	$a_3^n$
6	n!
7	$n^n$

级数的收敛

可以根据无穷大的比较，比较无穷小，从大到小。

序号	数列
1	$\dfrac{1}{\ln{n}}$
2	$\dfrac{1}{n^{1/a_1}}$
3	$\dfrac{1}{n}$
4	收敛分界线
5	$\dfrac{1}{n^{a_2}}$
6	$\dfrac{1}{a_3^n}$
7	$\dfrac{1}{n!}$
8	$\dfrac{1}{n^n}$

收敛分界线：

1/n级数是发散的，分划成n个大于1/2的值。
1/(n**a)级数，a>1，是收敛的。
a=1时，1/(n**a)

二、极限

分为数列极限、函数极限

想要目标ε任意近，只要范围δ足够近。ε是目标，δ是足够近的范围。（当自变量趋向于无穷时，δ会换成N）

ε-δ语言定义，对于任意小的给定的正数ε，都存在δ>0，使得当 $\left| x-x_0 \right|<\delta$ 时，有不等式 $\left| f(x)-a \right|<\varepsilon$ 成立。

极限的四则运算，条件是：A、B 的极限，各自存在，也就是极限不是无穷大，即

{\lim\limits_{x\to\infty}} f(x)=A

，

{\lim\limits_{x\to\infty}} g(x)=B

。

${\lim\limits_{x\to\infty}} \left[ f(x) \pm g(x) \right] = {\lim\limits_{x\to\infty}f(x) \pm \lim\limits_{x\to\infty}g(x)} = A \pm B$
${\lim\limits_{x\to\infty}} \left[ f(x) \cdot g(x) \right] = {\lim\limits_{x\to\infty}f(x) \cdot \lim\limits_{x\to\infty}g(x)} = A \cdot B$
${\lim\limits_{x\to\infty}} \dfrac{f(x)}{g(x)} = \dfrac{\lim\limits_{x\to\infty}f(x)}{\lim\limits_{x\to\infty}g(x)} = \dfrac{A}{B}$

极限的复合

有 ${\lim\limits_{x\to x_0}}f(x)=L1$ ， ${\lim\limits_{x\to L1}}g(x)=L2$ ，则 ${\lim\limits_{x\to x_0}}g(f(x))=L2$

连续性

f(x)在x0处连续，即 ${\lim\limits_{x\to x_0}}f(x)=f(x_0)$ 。左极限和右极限都有极限，且相等。

两个重要极限

{\lim\limits_{n\to\infty}} \left( 1+ \dfrac{1}{n} \right)^n=e

，

{\lim\limits_{n\to 0}} \dfrac{\sin{x}}{x}=1

夹逼定理

f(x)与g(x)在x0连续且存在相同的极限A， ${\lim\limits_{x\to x_0}} f(x)= {\lim\limits_{x\to x_0}} g(x) =A$ ，若有函数f(x)在x0的某邻域内恒有f(x)≤k(x)≤g(x)，则有 ${\lim\limits_{x\to x_0}} k(x) =A$

牛顿二项式定理

\left(x+y \right)^n =\sum_{k=0}^n{\dbinom{n}{k}x^{n-k}y^k}

，其中

\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}

三、导数

定义

f' \left( x_0 \right) = {\lim\limits_{\Delta x\to 0}} \dfrac{\Delta y}{\Delta x} = {\lim\limits_{\Delta x\to 0}} \dfrac{f(x_0+\Delta x)}{\Delta x}= {\lim\limits_{x\to x_0}} \dfrac{f(x)-f(x_0))}{x-x_0}

如果函数y=f(x)在开区间内每一点都可导，就称函数f(x)在区间内可导。这时函数y=f(x)对于区间内的每一个确定的x值，都对应着一个确定的导数值，这就构成一个新的函数，称这个函数为原来函数y=f(x)的导函数，记作y’、f’(x)、dy/dx或df(x)/dx，简称导数。

more >>

展开全文 >>