月见樽'blog

抽象数据结构抽象数据结构（ADT）是一些操作的集合，集合了一些必要且重用性高的操作，这些操作在一个项目中只被编写一次。抽象数据结构只定义操作的存在，并不定义操作的实现 表概念表是一种基础的数据结构，是一系列逻辑上”顺序”的数据（顺序指具有连续的数值索引）。例如$A{0},A{1},A_{2}$就是一个表，数据具有连续索引1,2,3。此外，还有前驱元和后继元的概念： 前驱元：某个元素之前的元素被称为该元素的前驱元（不定义第一个元素的前驱元） 后继元：某个元素之后的元素被称为该元素的后继元（不定义最后一个元素的后继元） 表的实现方法 数组实现：查找快，插入与删除慢，大小固定，内存中一般连续 链表实现：查找较慢，插入与删除相对较快，大小可变，内存中一般不连续 表需要的方法 is_empty：判断是否为空表 is_last：判断是否为结尾 find：根据值获得在表中的节点（find_previous：获得前驱元） visit：根据位置获得值（find） delete：删除元素 insert：插入元素 实现接口与结构体123456789101112131415161718192021 ...

logN复杂度估算logN复杂度的算法可以认为具有以下特性： 用常数时间将问题的大小削减为某一部分（通常是1/2） 例如分治法求最大子串问题，将一个$O(N^{2})$的问题削减为每个的1/2，每个问题复杂度为$O(N)$（有循环），所以该算法的复杂度估计为$O(NlogN)$ logN复杂度算法举例对分查找问题已知一串整数按顺序排布，寻找某个指定数的下标 求解考虑已经按顺序排列，那么使用二分查找的方法即可。对于For循环内部算法的复杂度是O(1)，且每次循环都将问题缩小一半，所以认为这是一个O(logN)的算法 123456789101112131415func binary_search(data []int, target int) int { left, right, mid := 0, len(data), 0 for left != right { mid = int((left + right) / 2) // fmt.Println(mid) if data[mid] == target { return mid } ...

算法复杂度分析算法复杂度基本定义算法复杂度分析基于以下四条定义： 如果存在常数c与$n{0}$使$N \geq n{0} $时，有$T(N) \leq cf(N)$，则记 $T(N) = O(f(N))$ 如果存在常数c与$n{0}$使$N \geq n{0} $时，有$T(N) \geq cf(N)$，则记 $T(N) = \Omega(f(N))$ 当且仅当$T(N) = O(f(N))$且$T(N) = \Omega(f(N))$时，记$T(N) = \Theta(f(N))$ 若$T(N) = O(f(N))$且$T(N) \neq \Theta(f(N))$时，记$T(N) = o(f(N))$ 若使用比较简单（不甚准确）的表达： 当T(N)增长的比f(N)慢的时候，认为$T(N) = O(f(N))$ 当T(N)增长的比f(N)快的时候，认为$T(N) = \Omega(f(N))$ 当T(N)和f(N)一样快的时候，认为$T(N) = \Theta(f(N))$ 算法复杂度分析运算 加法：T1(N)=O(f(x))，T2(N)=O(g(x))，则T1(N) + ...

理论基础决策树决策树是一种树形结构的机器学习算法，所有的样本起始于根节点，每个具有子节点的父节点都有一个判断，根据判断结果将样本向子节点分流，测试样本从根节点开始向下流动，通过判断最终到达某个没有子节点的叶子节点，这个节点就是该样本所属的类别。例如，判断一个动物是鸭子，狗还是兔子，可以具有以下的决策树： 判断是否有四条腿 没有，是鸭子 有，判断眼睛颜色 红色，是兔子 非红色，是狗 决策树训练算法训练决策树时，可以描述如下 从父节点找到最优划分属性 根据属性划分出子节点 若子节点为空/属性相同（无需划分）或样本相等（无法划分），返回，否则返回第一步继续递归划分 找到最优划分属性时，计算按每个属性划分的信息熵，取信息熵最大的属性为最优划分属性 代码实现载入数据——泰坦尼克号数据导入1import pandas as pd 12titan = pd.read_csv("http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt")print(titan.head()) row ...

概念KNN（K临近）分类器应该算是概率派的机器学习算法中比较简单的。基本的思想为在预测时，计算输入向量到每个训练样本的欧氏距离（几何距离），选取最近的K个训练样本，K个训练样本中出现最多的类别即预测为输入向量的类别（投票） 代码实现载入数据集——鸢尾花数据集12from sklearn.datasets import load_irisdataset = load_iris() 12print(dataset.data.shape)print(dataset.DESCR) (150, 4) Iris Plants Database ==================== Notes ----- Data Set Characteristics: :Number of Instances: 150 (50 in each of three classes) :Number of Attributes: 4 numeric, predictive attributes and the class :Attribute Information: - ...

理论内容贝叶斯定理贝叶斯定理是描述条件概率关系的定律 P(A|B) = \cfrac{P(B|A) * P(A)}{P(B)}朴素贝叶斯分类器朴素贝叶斯分类器是一种基于概率的分类器，我们做以下定义： B：具有特征向量B A：属于类别A 有了这个定义，我们解释贝叶斯公式 P(A|B)：具有特征向量B样本属于A类别的概率（计算目标） P(B|A)：在A类别中B向量出现的概率（训练样本中的数据） P(A)：A类出现的概率（训练样本中的频率） P(B)：B特征向量出现的概率（训练样本中的频率） 对于朴素贝叶斯分类器，进一步假设特征向量之间无关，那么朴素贝叶斯分类器公式可以如下表示P(A|B) = \cfrac{P(A)\prod P(B_{i} |A)}{P(B)} 以上公式右侧的值都可以在训练样本中算得。进行预测时，分别计算每个类别的概率，取概率最高的一个类别。 特征向量为连续值的朴素贝叶斯分类器对于连续值，有以下两种处理方式 将连续值按区间离散化 假设特征向量服从正态分布或其他分布（很强的先验假设），由样本中估计出参数，计算贝叶斯公式时带入概率密度 代码实现导入数据——文本新闻 ...

原理分类器机器学习的分类器，均可以看成一个或一组超平面，将label不同的数据点在数据空间中分开。对于线性可分问题，属于相同label的数据点在数据空间中可以看成是“类聚”的，即具有相同label的点会聚在一起。这样，分类效果最好的超平面应该满足：对于其分割的两种label，距离最近的两个不同label的数据点距离超平面的距离都足够大，即超平面离两个类聚的空间都足够远。 支持向量对于支持向量机来说，最关心的并不是所有数据的分布情况，而是所谓类聚空间边界的相互位置，这些边界上的数据点，即两个空间间隔最小的两个数据点被称为支持向量，支持向量机分类器就是针对这些点优化的分类器 核函数以上的所有说明都是针对线性可分问题的，当处理线性不可分问题的时候，线性分类器就无能为力了。那么需要使用一个叫核函数的东西，将线性不可分问题变成线性可分问题。核函数是一种对应关系，可以将数据映射到更高的维度上去，即认为：在当前维度不可分的问题，到达更高维度的时候有可能变的线性可分。在支持向量机的范畴中，核函数是一种先验，即人工在训练前就指定的。在当前的神经网络算法中，可以将输出层看成线性分类器，将隐藏层看成核函数， ...

导入可能用到的Python库1234import pandas as pdimport matplotlib.pyplot as pltimport numpy as npimport re 目标 学习机器学习算法——线性分类器 使用良性/恶性乳腺癌肿瘤数据集进行预测 理论学习线性分类器特征与分类结果存在线性关系的模型为线性分类器，模型通过累积特征和对应权值的方式决策，几何学上可看成一个n维空间中的超平面，学习的过程就是不断调整超平面的位置与倾斜程度，使该超平面可以最完美的将属于不同类别的特征点区分开，公式为：f(w,x,b) = w^{T}x+b logistic 函数线性分类器输出的是一个数，我们希望这个数在区间[0,1]之间，需要一个映射关系，这个映射关系就是logistic函数g(x) = \cfrac{1}{1 + e^{-x}}下面使用numpy和matplot绘制该函数的图像 1234x = np.linspace(start=-10,stop=10,num=1000)y = 1 / (1 + np.exp(-x))plt.plot(x,y)plt.show() 将线 ...

MLP中实现dropout，批标准化基本网络代码 三层MLP 使用MNIST数据集 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import torch as ptimport torchvision as ptvimport numpy as nptrain_set = ptv.datasets.MNIST("../../pytorch_database/mnist/train",train=True,transform=ptv.transforms.ToTensor(),download=True)test_set = ptv.datasets.MNIST("../../pytorch_database/mnist/test",train=False,transform=ptv.transforms.ToTensor(),download=True)train_dataset = pt.u ...

基于Pytorch的MLP实现目标 使用pytorch构建MLP网络 训练集使用MNIST数据集 使用GPU加速运算 要求准确率能达到92%以上 保存模型实现数据集：MNIST数据集的载入MNIST数据集是一种常用的数据集，为28*28的手写数字训练集，label使用独热码，在pytorch中，可以使用torchvision.datasets.MNIST()和torch.utils.data.DataLoader（）来导入数据集,其中 torchvision.datasets.MNIST():用于下载，导入数据集 torch.utils.data.DataLoader（）:用于将数据集整理成batch的形式并转换为可迭代对象 123import torch as ptimport torchvision as ptvimport numpy as np 12train_set = ptv.datasets.MNIST("../../pytorch_database/mnist/train",train=True,transform=ptv.transforms.T ...