Wetts's blog

k 近邻法（k-nearest neighbor, k-NN）是一种基本分类与回归方法。

k 近邻算法

k 近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最临近的 k 个 实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

k 近邻法的特殊情况是 k=1 的情形，称为最近邻算法。

k 近邻模型

k 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k 值的选择和分类决策规则决定。

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k 近邻模型的特征空间一般是 n 维实数向量空间 Rn。使用的距离是欧式距离，但也可以是其他距离。

k 值的选择

k 值的选择会对 k 近邻法的结果产生重大影响。

如果选择较小的 k 值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果近邻的实例点恰好是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的 k 值，就相当于用较大领域中的训练实例进行预测。其有点是可以减小学习的估计误差。但缺点是学习的近邻误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k 值的增大就意味着整体的模型变得简单。

在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。

分类决策规则

k 近邻法的分类决策规则往往是多数表决，即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类。

k 近邻法的实现：kd 树

k 近邻法最简单的实现方法是线性扫描（linear scan）。这时计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。

为了提高 k 近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。

构造 kd 树

kd 树是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd 树是二叉树，表示对 k 维空间的一个划分（partition）。构造 kd 树相当于不断地用垂直于坐标轴的超平面将 k 维空间切分，构成一系列的 k 维超矩形区域。kd 树的每个结点对应于一个 k 维超矩形区域。

构造 kd 树的方法如下：构造根结点，使根结点对应于 k 维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对 k 维空间进行切分，生成子节点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子节点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数（median）为切分点，这样得到的 kd 树是平衡的。注意，平衡的 kd 树搜索时的效率未必是最优的。

搜索 kd 树

给定一个目标点，搜索其最近邻。首选找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父节点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。

包含目标点的叶结点对应包含目标点的最小超矩形区域。依次叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。然后返回当前结点的父节点，如果父节点的另一子节点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法赚到更上一级的父节点，继续上述过程。如果父节点的另一子节点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。

参考：https://zhuanlan.zhihu.com/p/36173202

• 单前导下划线：_var
• 单末尾下划线：var_
• 双前导下划线：__var
• 双前导和末尾下划线：__var__
• 单下划线：_

单前导下划线 _var

下划线前缀的含义是告知其他程序员：以单个下划线开头的变量或方法仅供内部使用。 该约定在PEP 8中有定义。

这不是Python强制规定的。 Python不像Java那样在“私有”和“公共”变量之间有很强的区别。

看看下面的例子：

1
2
3
4

class Test:
   def __init__(self):
       self.foo = 11
       self._bar = 23

如果你实例化此类，并尝试访问在__init__构造函数中定义的foo和_bar属性，会发生什么情况？ 让我们来看看：

1
2
3
4
5

>>> t = Test()
>>> t.foo
11
>>> t._bar
23

你会看到_bar中的单个下划线并没有阻止我们“进入”类并访问该变量的值。

这是因为Python中的单个下划线前缀仅仅是一个约定 - 至少相对于变量和方法名而言。

但是，前导下划线的确会影响从模块中导入名称的方式。

1
2
3
4
5
6
7

# This is my_module.py:

def external_func():
   return 23

def _internal_func():
   return 42

现在，如果使用通配符从模块中导入所有名称，则Python不会导入带有前导下划线的名称（除非模块定义了覆盖此行为的__all__列表）：

1
2
3
4
5

>>> from my_module import *
>>> external_func()
23
>>> _internal_func()
NameError: "name '_internal_func' is not defined"

顺便说一下，应该避免通配符导入，因为它们使名称空间中存在哪些名称不清楚。 为了清楚起见，坚持常规导入更好。

与通配符导入不同，常规导入不受前导单个下划线命名约定的影响：

1
2
3
4
5

>>> import my_module
>>> my_module.external_func()
23
>>> my_module._internal_func()
42

我知道这一点可能有点令人困惑。 如果你遵循PEP 8推荐，避免通配符导入，那么你真正需要记住的只有这个：

单个下划线是一个Python命名约定，表示这个名称是供内部使用的。 它通常不由Python解释器强制执行，仅仅作为一种对程序员的提示。

单末尾下划线 var_

有时候，一个变量的最合适的名称已经被一个关键字所占用。 因此，像class或def这样的名称不能用作Python中的变量名称。 在这种情况下，你可以附加一个下划线来解决命名冲突：

1
2
3
4
5

>>> def make_object(name, class):
SyntaxError: "invalid syntax"

>>> def make_object(name, class_):
...    pass

总之，单个末尾下划线（后缀）是一个约定，用来避免与Python关键字产生命名冲突。 PEP 8解释了这个约定。

双前导下划线 __var

双下划线前缀会导致Python解释器重写属性名称，以避免子类中的命名冲突。

这也叫做名称修饰（name mangling） - 解释器更改变量的名称，以便在类被扩展的时候不容易产生冲突。

我知道这听起来很抽象。 因此，我组合了一个小小的代码示例来予以说明：

1
2
3
4
5

class Test:
   def __init__(self):
       self.foo = 11
       self._bar = 23
       self.__baz = 23

让我们用内置的dir()函数来看看这个对象的属性：

1
2
3
4
5
6
7
8

>>> t = Test()
>>> dir(t)
['_Test__baz', '__class__', '__delattr__', '__dict__', '__dir__',
'__doc__', '__eq__', '__format__', '__ge__', '__getattribute__',
'__gt__', '__hash__', '__init__', '__le__', '__lt__', '__module__',
'__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__',
'__setattr__', '__sizeof__', '__str__', '__subclasshook__',
'__weakref__', '_bar', 'foo']

以上是这个对象属性的列表。 让我们来看看这个列表，并寻找我们的原始变量名称foo，_bar和__baz - 我保证你会注意到一些有趣的变化。

• self.foo变量在属性列表中显示为未修改为foo。
• self._bar的行为方式相同 - 它以_bar的形式显示在类上。 就像我之前说过的，在这种情况下，前导下划线仅仅是一个约定。 给程序员一个提示而已。
• 然而，对于self.__baz而言，情况看起来有点不同。 当你在该列表中搜索__baz时，你会看不到有这个名字的变量。
  __baz出什么情况了？

如果你仔细观察，你会看到此对象上有一个名为_Test__baz的属性。 这就是Python解释器所做的名称修饰。 它这样做是为了防止变量在子类中被重写。

让我们创建另一个扩展Test类的类，并尝试重写构造函数中添加的现有属性：

1
2
3
4
5
6

class ExtendedTest(Test):
   def __init__(self):
       super().__init__()
       self.foo = 'overridden'
       self._bar = 'overridden'
       self.__baz = 'overridden'

现在，你认为foo，_bar和__baz的值会出现在这个ExtendedTest类的实例上吗？ 我们来看一看：

1
2
3
4
5
6
7

>>> t2 = ExtendedTest()
>>> t2.foo
'overridden'
>>> t2._bar
'overridden'
>>> t2.__baz
AttributeError: "'ExtendedTest' object has no attribute '__baz'"

等一下，当我们尝试查看t2.__baz的值时，为什么我们会得到AttributeError？ 名称修饰被再次触发了！ 事实证明，这个对象甚至没有__baz属性：

1
2
3
4
5
6
7

>>> dir(t2)
['_ExtendedTest__baz', '_Test__baz', '__class__', '__delattr__',
'__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__',
'__getattribute__', '__gt__', '__hash__', '__init__', '__le__',
'__lt__', '__module__', '__ne__', '__new__', '__reduce__',
'__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__',
'__subclasshook__', '__weakref__', '_bar', 'foo', 'get_vars']

正如你可以看到__baz变成_ExtendedTest__baz以防止意外修改：

1
2

>>> t2._ExtendedTest__baz
'overridden'

但原来的_Test__baz还在：

1
2

>>> t2._Test__baz
42

双下划线名称修饰对程序员是完全透明的。 下面的例子证实了这一点：

1
2
3
4
5
6
7
8
9
10
11

class ManglingTest:
   def __init__(self):
       self.__mangled = 'hello'

   def get_mangled(self):
       return self.__mangled

>>> ManglingTest().get_mangled()
'hello'
>>> ManglingTest().__mangled
AttributeError: "'ManglingTest' object has no attribute '__mangled'"

名称修饰是否也适用于方法名称？ 是的，也适用。名称修饰会影响在一个类的上下文中，以两个下划线字符（”dunders”）开头的所有名称：

1
2
3
4
5
6
7
8
9
10
11

class MangledMethod:
   def __method(self):
       return 42

   def call_it(self):
       return self.__method()

>>> MangledMethod().__method()
AttributeError: "'MangledMethod' object has no attribute '__method'"
>>> MangledMethod().call_it()
42

这是另一个也许令人惊讶的运用名称修饰的例子：

1
2
3
4
5
6
7
8

_MangledGlobal__mangled = 23

class MangledGlobal:
   def test(self):
       return __mangled

>>> MangledGlobal().test()
23

在这个例子中，我声明了一个名为_MangledGlobal__mangled的全局变量。然后我在名为MangledGlobal的类的上下文中访问变量。由于名称修饰，我能够在类的test()方法内，以__mangled来引用_MangledGlobal__mangled全局变量。

Python解释器自动将名称__mangled扩展为_MangledGlobal__mangled，因为它以两个下划线字符开头。这表明名称修饰不是专门与类属性关联的。它适用于在类上下文中使用的两个下划线字符开头的任何名称。

双前导和双末尾下划线 __var__

也许令人惊讶的是，如果一个名字同时以双下划线开始和结束，则不会应用名称修饰。 由双下划线前缀和后缀包围的变量不会被Python解释器修改：

1
2
3
4
5
6

class PrefixPostfixTest:
   def __init__(self):
       self.__bam__ = 42

>>> PrefixPostfixTest().__bam__
42

但是，Python保留了有双前导和双末尾下划线的名称，用于特殊用途。 这样的例子有，__init__对象构造函数，或__call__ — 它使得一个对象可以被调用。

这些dunder方法通常被称为神奇方法。

最好避免在自己的程序中使用以双下划线（“dunders”）开头和结尾的名称，以避免与将来Python语言的变化产生冲突。

单下划线 _

按照习惯，有时候单个独立下划线是用作一个名字，来表示某个变量是临时的或无关紧要的。

例如，在下面的循环中，我们不需要访问正在运行的索引，我们可以使用“_”来表示它只是一个临时值：

1
2

>>> for _ in range(32):
...    print('Hello, World.')

你也可以在拆分(unpacking)表达式中将单个下划线用作“不关心的”变量，以忽略特定的值。 同样，这个含义只是“依照约定”，并不会在Python解释器中触发特殊的行为。 单个下划线仅仅是一个有效的变量名称，会有这个用途而已。

在下面的代码示例中，我将汽车元组拆分为单独的变量，但我只对颜色和里程值感兴趣。 但是，为了使拆分表达式成功运行，我需要将包含在元组中的所有值分配给变量。 在这种情况下，“_”作为占位符变量可以派上用场：

1
2
3
4
5
6
7
8
9

>>> car = ('red', 'auto', 12, 3812.4)
>>> color, _, _, mileage = car

>>> color
'red'
>>> mileage
3812.4
>>> _
12

除了用作临时变量之外，“_”是大多数Python REPL中的一个特殊变量，它表示由解释器评估的最近一个表达式的结果。

这样就很方便了，比如你可以在一个解释器会话中访问先前计算的结果，或者，你是在动态构建多个对象并与它们交互，无需事先给这些对象分配名字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

>>> 20 + 3
23
>>> _
23
>>> print(_)
23

>>> list()
[]
>>> _.append(1)
>>> _.append(2)
>>> _.append(3)
>>> _
[1, 2, 3]

Python下划线命名模式 - 小结

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取 +1 和 -1 二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。

感知机模型

由输入空间到输出空间的如下函数 称为感知机。其中，w 和 b 为感知机模型参数， w 叫作权值（weight）或权值向量（weight vector），b 叫作偏置（bias）。sign 是符号函数，即

感知机学习策略

数据集的线性可分性

如果存在某个超平面 S 能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集 T 为线性可分数据集（linearly separable data set）；否则，称数据集 T 线性不可分。

感知机学习策略

感知机的损失函数定义为 其中 M 为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。

显然，损失函数 L(w, b) 是非负的。如果没有误分类点，损失函数值是 0.而且，误分类点越少，误分类点离超平面越近，损失函数值越小。

感知机学习的策略是在假设空间中选取使损失函数式最小的模型参数 w 和 b，即感知机模型。

感知机学习算法

感知机学习问题转化为求解损失函数式的最优化问题，最优化的方法是随机梯度下降法。

感知机学习算法的原始形式

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整 w, b 的值，使分离超平面向该误分类点的一侧移动，以减小该误分离点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

算法的收敛性

感知机学习算法的对偶形式

实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类（越容易分错，超平面一动不多就容易将这些点分错），换句话说，这样的实例对学习结果影响最大（在支持向量机中，这些点代表着支持向量）。

转自：https://blog.csdn.net/dcrmg/article/details/52416832

向量是由n个实数组成的一个 n 行 1 列（n1）或一个 1 行 n 列（1n）的有序数组；

向量的点乘,也叫向量的内积、数量积，对两个向量执行点乘运算，就是对这两个向量对应位一一相乘之后求和的操作，点乘的结果是一个标量。

点乘

点乘公式

对于向量a和向量b：

a和b的点积公式为：

要求一维向量a和向量b的行列数相同。

点乘几何意义

点乘的几何意义是可以用来表征或计算两个向量之间的夹角，以及在b向量在a向量方向上的投影，有公式：

推导过程如下，首先看一下向量组成：

叉乘

叉乘公式

两个向量的叉乘，又叫向量积、外积、叉积，叉乘的运算结果是一个向量而不是一个标量。并且两个向量的叉积与这两个向量组成的坐标平面垂直。

对于向量a和向量b：

a和b的叉乘公式为：

其中：

叉乘几何意义

在三维几何中，向量a和向量b的叉乘结果是一个向量，更为熟知的叫法是法向量，该向量垂直于a和b向量构成的平面。

在3D图像学中，叉乘的概念非常有用，可以通过两个向量的叉乘，生成第三个垂直于a，b的法向量，从而构建X、Y、Z坐标系。如下图所示：

在二维空间中，叉乘还有另外一个几何意义就是：aXb等于由向量a和向量b构成的平行四边形的面积。

统计学习

统计学习主要特点：

1. 统计学习以计算机及网络为平台，是建立在计算机及网络之上的；
2. 统计学习以数据为研究对象，是数据驱动的学科；
3. 统计学习的目的是对数据进行预测与分析；
4. 统计学习以方法为中心，统计学习方法构建模型并应用模型进行预测与分析；
5. 统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科，并且在发展中逐步形成独立的理论体现与方法论。

统计学习的组成：

• 监督学习（supervised learning）
• 非监督学习（unsupervised learning）
• 半监督学习（semi-supervised learning）
• 强化学习（reinforcement learning）

统计学习方法的三要素：

• 模型（model）
• 策略（strategy）
• 算法（algorithm）

监督学习

监督学习的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。

统计学习三要素

模型

在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间（hypothesis space）包含所有可能的条件概率分布或决策函数。

策略

损失函数和风险函数

损失函数

监督学习问题是在假设空间 F 中选取模型 f 作为决策函数，对于给定的输入 X，由 f(X) 给出相应的输出 Y，这个输出的预测值 f(X) 与真实值 Y 可能一致也可能不一致，用一个损失函数（loss function）或代价函数（cost function）来度量预测错误的程度。损失函数是 f(x) 和 Y 的非负实值函数，记作 L(Y, f(X))。

常用的损失函数：

1. 0-1损失函数（0-1 loss function)
   
2. 平方损失函数(quadratic loss function)
   
3. 绝对损失函数（absolute loss function）
   
4. 对数损失函数（logarithmic loss function）或对数似然损失函数（loglikelihood loss function）
   

风险函数

损失函数数值越小，模型就越好。由于模型的输入、输出 (X, Y) 是随机变量，遵循联合分布 P(X, Y)，所以损失函数的期望是

这是理论上模型 f(X) 关于联合分布 P(X, Y) 的平均意义下的损失，称为风险函数（risk funciton）或期望损失（expected loss）。

学习的目标就是选择期望风险最小的模型。由于联合分布是未知的，所以损失函数的期望不能直接计算。

给定一个训练数据集。模型 f(X) 关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失风险（empirical loss），记作：

根据大数定律，当样本容量 N 趋于无穷时，经验风险趋于期望风险。

经验风险最小化与结构风险最小化

经验风险

在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数式就可以确定。经验风险最小化（empirical risk minimization，ERM）的策略认为，经验风险最小的模型是最优的模型。

当样本容量足够大时，经验风险最小化能保证有很好的学习效果。比如，极大似然估计（maximum likelihood estimation）就是经验风险最小化的例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等驾驭极大似然估计。

但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，就产生“过拟合（over-fitting）“现象。

结构风险

结构风险最小化（structural risk minimization，SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（penalty term）。在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义是：。其中 J(f) 为模型的复杂度，是定义在假设空间 F 上的泛函。模型 f 越复杂，复杂度 J(f) 就越大；反之，模型 f 越简单，复杂度 J(f) 就越小。

比如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation，MAP）就是结构风险最小化的例子。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等驾驭最大后验概率估计。

算法

算法是指学习模型的具体计算方法。

模型评估与模型选择

训练误差与测试误差

统计学习方法具体采用的损失函数未必是评估时使用的损失函数。当然，让两者一致是比较理想的。

过拟合与模型选择

如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高，这种现象称为过拟合（over-fitting）。过拟合是指学习时选择的模型所包含的参数过多，以至于出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。

当模型的复杂度增大时，训练误差会逐渐减小并趋向于0；而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过于大时，过拟合现象就会发生。这样，在学习时就要防止过拟合，进行最优的模型选择，即选择复杂度适当的模型，以达到使测试误差最小的学习目的。下面介绍两种常用的模型选择方法：正则化与交叉验证。

正则化与交叉验证

正则化

模型选择的典型方法使正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值越大。

正则化符合奥卡姆剃刀（Occam’s razor）原理。奥卡姆剃刀原理应用于模型选择时为以下想法：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型，也就是应该选择的模型。从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

交叉验证

如果给定的样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分成三部分，分为训练集（training set）、验证集（validation set）和测试集（test set）。训练集用来训练模型，验证集用于模型的选择，而测试集用于最终学习方法的评估。

但是，在许多实际应用中数据是不充足的。为了选择好的模型，可以采用交叉验证方法。交叉验证的基本想法是重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。

简单交叉验证

简单交叉验证方法是：首先随机地将已给数据分为两部分，一部分作为训练集，另一部分作为测试集；然后用训练集在各种条件下训练模型，从而得到不同的模型；在测试集上评价各个模型的测试误差，选出测试误差最小的模型。

S 折交叉验证

应用最多的是 S 折交叉验证（S-flod cross validation)，方法如下：首先随机地将已给数据切分为 S 个互不相交的大小相同的子集；然后利用 S-1 个子集的数据训练模型，利用余下的子集测试模型；将这一过程对可能的 S 种选择重复进行；最后选出 S 次评测中平均测试误差最小的模型。

留一交叉验证

S 折交叉验证的特殊情形是 S=N，称为留一交叉验证（leave-one-out cross validation），往往在数据缺乏的情况下使用。这里，N 是给定数据集的容量。

泛化能力

泛化误差

学习方法的泛化能力（generalization ability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。现实中采用最多的办法是通过测试误差来评价学习方法的泛化能力。

事实上，泛化误差就是所学习到的模型的期望风险。

泛化误差上界

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界（generalizaiton error bound）。具体来说，就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。泛化误差上界通常具有以下性质：它是样本容量的函数，当样本容量增加时，泛化上界趋于0；它是假设空间容量（capacity）的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

生成模型与判别模型

监督学习的任务就是学习一个模型，应用这一模型，对给定的输入预测相应的输出。这个模型的一般形式为决策函数：Y=f(X) 或者条件概率分布：P(Y|X)。

监督学习方法又可分为生成方法（generative approach）和判别方法（discriminative approach）。所学习到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。

生成方法由数据学习联合概率分布 P(X, Y)，然后求出条件概率分布 P(Y|X) 作为预测的模型。这样的方法之所以称为生成方法。是因为模型表示了给定输入 X 产生输出 Y 的生成关系。典型的生成模型由：朴素贝叶斯法和隐马尔可夫模型。

判别方法由数据直接学习决策函数 f(X) 或者条件概率分布 P(Y|X) 作为预测的模型，即判别模型。判别方法关系的是对给定的输入 X，应该预测什么样的输出 Y。典型的判别模型包括：k 近邻法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。

生成方法的特点：生成方法可以还原出联合概率分布 P(X, Y)，而判别方法则不能；生成方法的学习收敛更快，即当样本容量增加的时候，学习的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时判断方法就不能用。

判别方法的忒点：判别方法直接学习的是条件概率 P(Y|X) 或决策函数 f(X)，直接面对预测，往往学习的准确率更高；由于直接学习 P(Y|X) 或 f(X)，可以对数据进行个各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。

分类问题

在监督学习中，当输入变量 Y 取有限个离散值时，预测问题便称为分类问题。这时，输入变量 X 可以是离散的，也可以是连续的。监督学习从数据中学习一个分离诶模型或分类决策函数，称为分类器（classifier）。分类器对新的输入进行输出的预测（prediction），称为分类（classification）。可能的输出称为类（class）。分类的类别为多个时，称为多类分类问题。

评价分类器性能的指标一般是分类准确率（accuracy），其定义是：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。也就是损失函数是 0-1 损失时测试数据集上的准确率。

标注问题

标注（tagging）也是一个监督学习问题。可以认为标注问题是分类问题的一个推广，标注问题又是更复杂的结构预测（structure prediction）问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学一个模型，使它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合所成的标记序列的个数是依序列长度呈指数级增长的。

标注常用的统计学习方法有：隐马尔可夫模型、条件随机场。

回归问题

回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。

回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之前的关系的类型即模型的类型，分类线性回归和非线性回归。

回归学习最常用的损失函数是平方损失函数，在此情况下，回归问题可以由著名的最小二乘法（least squares）求解。

accuracy、查准率、查全率

• 准确率（accuracy）：= 预测对的/所有 = (TP+TN)/(TP+FN+FP+TN)
• 查准率（precision）：P=TP/(TP+FP)（预测结果和真实结果都为正的样本占总的预测结果为正的样本的比例）（挑出的西瓜种有多少比例是好瓜）
• 查全率（recall）：R=TP/(TP+FN)（预测结果和真实结果都为正的样本占总的正样本的比例）（所有好瓜中有多少比例被挑了出来）

查准率和查全率是一对矛盾的度量，一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。在信息检索中，查准率就是检索出的信息有多少比例是用户感兴趣的；查全率则是用户感兴趣的信息有多少被检索出来。查准率分母中就包含了那些不是用户感兴趣的信息，但仍被预测为是用户感兴趣的而被检索出来；查全率分母中则包含了那些是用户感兴趣的信息，但为被预测为用户感兴趣而被抛弃未检索出来。

对于差准率和查全率的使用是需要按情况来确定那个更重要，例如地震的预测查全率更重要，不希望遗漏哪一次地震，但是对于给用户推荐的广告查准率更重要，要推荐给用户更愿意点击的广告。

P-R曲线

可根据学习器的预测结果对样例进行排序，排在前面的是学习器认为最可能是正例的样本，排在最后的则是学习器认为最不可能是正例的样本。按此顺序逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率，并以查准率为纵轴、查全率为横轴构造查准率-查全率曲线，简称P-R曲线。

P-R曲线是非单调、不平滑的。P-R曲线可用来评估学习器的优劣。若一个学习器的P-R曲线被另一个学习器的P-R曲线完全包住，则后者的性能优于前者。如果两个学习器的曲线发生交叉，则通过二者面积的大小来比较，面积大的表示查全率和查准率双高比较优秀，但不太容易计算曲线（不平滑）的面积，因此通过平衡点（Break-Even Point，简称BEP）来度量。BEP是坐标上查准率等于查全率时的点，平衡点值越大，学习器越优秀。

用了简单的图来说明，红色的点就是三条P-R曲线的BEP点，学习器A的曲线被C包住，C比较优秀，而C和B交叉，用面积计算难以估算，但C的BEP值大于B，所以C比较优秀。

BEP过于简化，定义F1常量来比较学习器P-R曲线的性能：

• F1度量：F1=(2*P*R)/(P+R)=2*TP/(样例总数+TP-TN)

F1是基于查准率与查全率的调和平均（harmonic mean）定义的：1/F1=1/2*(1/P+1/R)

更一般的形式：Fβ=(1+β^2)*P*R/((β^2*P)+R）

其中β>0度量了查全率对查准率的相对重要性；β=1时就是标准的F1；β>1时偏好查全率；β<1时偏好查准率。

Fβ则是加权调和平均：1/Fβ=(1/P+β^2/R)/(1+β^2)

ROC、AUC

ROC和AUC类似，也是通过绘制两个变量的概率图像来解释分类器效果的评判准则,ROC曲线的纵轴是“真正例率”TPR，横轴是“假正例率”FPR。其中：

• 真正例率(True Postive Rate)TPR: TP/(TP+FN),代表分类器预测的正类中实际正实例占所有正实例的比例。Sensitivity
• 假正例率(False Postive Rate)FPR: FP/(FP+TN)，代表分类器预测的正类中实际负实例占所有负实例的比例。1-Specificity
• 真负例率(True Negative Rate)TNR: TN/(FP+TN),代表分类器预测的负类中实际负实例占所有负实例的比例，TNR=1-FPR。Specificity

AUC的几何意义ROC曲线下的面积。

概率学上的意义：随机选取一个正例和一个负例，分类器给正例的打分大于分类器给负例的打分的概率。

转自：https://blog.csdn.net/weixin_41179709/article/details/81879601

装饰器介绍

装饰器就是对被装饰的对象（函数、类）进行重构的，其可以在不改变原来对象的情况下调用对象时执行重构后的行为

1. 解决问题：在函数执行之前和执行之后添加功能，调用函数的方式改变了
2. 不改变原有函数的调用方法:函数里面嵌套函数，并且返回嵌套的函数

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

##引题：当登陆某系统时常常会有欢迎语，但修改时将在登陆函数中修改，可能会出现问题，所以避免直接侵入原函数修改。
def login():
    print("中秋快乐")
    print("login....")
    print("欢迎您下次光临....")
login()

##为了避免在大的函数块中操作，将欢迎语独立出来，另建函数。
def desc(fun):
    def add_info():
        print("中秋快乐")
        fun()
        print("欢迎您下次光临")
    return add_info
def login():
    print("login....")
login = desc(login)
login()

装饰器语法糖

在Python中，可以使用”@”语法糖来精简装饰器的代码，把 decorator 置于函数的定义处，免去给函数重新赋值(即function = decorator(funtion))

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import functools           #functools 标准库
import time                #time 时间函数

def add_log(fun):
    @functools.wraps(fun)           #不用此模块add(x,y)函数的__name__，__doc__都会丢失
    def wrapper(*args,**kwargs):   #*args为元组  **kwargs为字典
        start_time = time.time()
        res = fun(*args,**kwargs)
        end_time = time.time()
        print("[%s] 函数名：%s, 运行时间 ：%.5f ,运行返回值：% d"
              %(time.ctime(),fun.__name__,end_time- start_time,res))
        return res                  #返回值为所要装饰的函数
    return wrapper                 #返回值为所要修饰函数所添加的模块
@add_log                            ##调用语法糖
def add(x,y):
    time.sleep(0.1)
    return x+y
print(add(1,2))

装饰的函数有返回值

解决办法：给返回值赋值

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def timeit(fun):
    def wrapper(*args,**kwargs):    #接收可变参数和关键字参数
        #args:元组 kwargs：字典  args=(5,)
        #原函数执行之前
        start_time = time.time()
        #执行函数
        res = fun(*args,**kwargs)   #args解包
        #执行函数
        end_time = time.time()
        print("运行时间为:%.6f" % (end_time - start_time))
    return res
    return wrapper

@timeit
def list_create(n):
    return(i*2 for i in range(n)])

@timeit
def map_create(n):
    return(list(map(lambda x:x*2,range(n))))

list_create(5)
map_create(5)
print(list_create(100))     ##wrapper(100)

保留被装饰的函数的函数名和帮助文档信息

解决办法：导入functools标准库,使用functools.wraps函数，保留被装饰的函数的函数名和帮助文档信息。

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import  functools
def timeit(fun):
    """这是一个装饰器timeit"""    
    @functools.wraps(fun)       ##内置装饰器
    可以保留被装饰的函数的函数名和帮助文档信息   
    def wrapper(*args,**kwargs):    #接收可变参数和关键字参数
        """这是一个wrapper函数"""
        #args:元组 kwargs：字典  args=(5,)
        #原函数执行之前
        start_time = time.time()
        #执行函数
        res = fun(*args,**kwargs)   #args解包
        #执行函数
        end_time = time.time()
        print("运行时间为:%.6f" % (end_time - start_time))
    return res
    return wrapper
@timeit
def fun():
    print("hello")
print(fun_list.__name__)
print(fun_list.__doc__)

装饰器中不同条件下执行不同的函数

用实例说明：需求: 用户来CSDN登陆验证的装饰器is_login

1. 如果用户登陆成功, 则执行被装饰的函数;
2. 如果用户登陆不成功, 则执行登陆函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import functools
login_users = ['admin', 'root']

def is_login(fun):  # fun: writeBlog
    @functools.wraps(fun)
    def wrapper(*args, **kwargs):   # name="admin"  # kwargs={"name":"admin"}
        # 判断写博客的这个用户是否登陆成功;
        if kwargs.get("name") in login_users:
            res = fun(*args, **kwargs)
            return res
        else:
            res=login()
        return res

    return wrapper

# 必须登陆成功
@is_login    # writeBlog = is_login(writeBlog)
def writeBlog(name):
    return "编写博客"

def login():
    return "登陆。。。。"

# 是否登陆成功都可以执行代码
def news():
    print("新闻......")

print(writeBlog(name="admin"))

多个装饰器

若有两个装饰器，从上到下调用装饰器，wrapper内容也是为由上向下执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def makebold(fun):
    print("bold1")
    def wrapper1(*args, **kwargs):
        print("bold2")
        return  fun(*args, **kwargs)  # wrapper
    return  wrapper1
def makei(fun):   # fun=login
    print("i1")
    def wrapper(*args, **kwargs):
        print("i2")
        return  fun(*args, **kwargs)
    return  wrapper
# 当有多个装饰器时，从上到下调用装饰器
# 真实wrapper内容执行是从上到下执行
@makebold   #login = makebold(login)    #login为wrapper1
@makei      #login = makei(login)       #login为wrapper
def login():
    return "登陆"
print(login())

带有参数的装饰器

创建装饰器， 要求如下：

1. 创建add_log装饰器， 被装饰的函数打印日志信息；
2. 日志格式为: [字符串时间] 函数名: xxx， 运行时间：xxx, 运行返回值结果:xxx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 创建装饰器， 要求如下：
# 1. 创建add_log装饰器， 被装饰的函数打印日志信息；
# 2. 日志格式为: [字符串时间] 函数名: xxx， 运行时间：xxx, 运行返回值结果:xxx


import functools
import time

# format
def log(kind):  # kind="debug"
    def add_log(fun):
        @functools.wraps(fun)
        def wrapper(*args, **kwargs):
            start_time = time.time()
            res = fun(*args, **kwargs)
            end_time = time.time()
            print("<%s> [%s] 函数名: %s， 运行时间：%.5f, 运行返回值结果:%d"
                  %(kind, time.ctime(), fun.__name__, end_time-start_time, res )
                  )
            return res
        return wrapper
    return  add_log
@log("debug")
#  log("debug")==> 返回值是add_log
#  add=add_log(add)
def add(x,y):
    time.sleep(0.1)
    return x+y
print(add(14214124124,1241231231313))
# wrapper(14214124124,1241231231313)

转自：https://www.cnblogs.com/deeper/p/7565571.html

理解了迭代器以后，生成器就会简单很多，因为生成器其实是一种特殊的迭代器。不过这种迭代器更加优雅。它不需要再像上面的类一样写__iter__()和__next__()方法了，只需要一个yiled关键字。 生成器一定是迭代器（反之不成立），因此任何生成器也是以一种懒加载的模式生成值。

语法上说，生成器函数是一个带yield关键字的函数。

调用生成器函数后会得到一个生成器对象，这个生成器对象实际上就是一个特殊的迭代器，拥有__iter__()和__next__()方法

我们先用一个例子说明一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

>>> def generator_winter():
...   i = 1
...   while i <= 3:
...     yield i
...     i += 1
...
>>> generator_winter
<function generator_winter at 0x000000000323B9D8>
>>> generator_iter = generator_winter()
>>> generator_iter
<generator object generator_winter at 0x0000000002D9CAF0>
>>>
>>> generator_iter.__next__()
1
>>> generator_iter.__next__()
2
>>> generator_iter.__next__()
3
>>> generator_iter.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

现在解释一下上面的代码：

1. 首先我们创建了一个含有yield关键字的函数generator_winter，这是一个生成器函数
2. 然后，我们调用了这个生成器函数，并且将返回值赋值给了generator_iter，generator_iter是一个生成器对象；__注意generator_iter = generator_winter()时，函数体中的代码并不会执行，只有显示或隐示地调用next的时候才会真正执行里面的代码__。
3. 生成器对象就是一个迭代器，所以我们可以调用对象的__next__方法来每次返回一个迭代器的值；迭代器的值通过yield返回；并且迭代完最后一个元素后，触发StopIteration异常；

既然生成器对象是一个迭代器，我们就可以使用for循环来迭代这个生成器对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

>>> def generator_winter():
...   i = 1
...   while i <= 3:
...     yield i
...     i += 1
...
>>>
>>> for item in generator_winter():
...   print(item)
...
1
2
3
>>>

我们注意到迭代器不是使用return来返回值，而是采用yield返回值；那么这个yield有什么特别之处呢？

yield

我们知道，一个函数只能返回一次，即return以后，这次函数调用就结束了；

但是生成器函数可以暂停执行，并且通过yield返回一个中间值，当生成器对象的__next__()方法再次被调用的时候，生成器函数可以从上一次暂停的地方继续执行，直到触发一个StopIteration

上例中，当执行到yield i后，函数返回i值，然后print这个值，下一次循环，又调用__next__()方法，回到生成器函数，并从yield i的下一句继续执行；

摘一段<python核心编程>的内容：

生成器的另外一个方面甚至更加强力—-协同程序的概念。协同程序是可以运行的独立函数调用，可以暂停或者挂起，并从程序离开的地方继续或者重新开始。在有调用者和(被调用的)协同程序也有通信。举例来说，当协同程序暂停时，我们仍可以从其中获得一个中间的返回值，当调用回到程序中时，能够传入额外或者改变了的参数，但是仍然能够从我们上次离开的地方继续，并且所有状态完整。挂起返回出中间值并多次继续的协同程序被称为生成器，那就是python的生成真正在做的事情。这些提升让生成器更加接近一个完全的协同程序，因为允许值(和异常)能传回到一个继续的函数中，同样的，当等待一个生成器的时候，生成器现在能返回控制，在调用的生成器能挂起(返回一个结果)之前，调用生成器返回一个结果而不是阻塞的等待那个结果返回。

什么情况会触发StopIteration

两种情况会触发StopIteration

1. 如果没有return，则默认执行到函数完毕时返回StopIteration；
2. 如果在执行过程中 return，则直接抛出 StopIteration 终止迭代；如果在return后返回一个值，那么这个值为StopIteration异常的说明，不是程序的返回值。

   1 2 3 4 5 6 7 8 9 10 11 12 13

   >>> def generator_winter(): ... yield 'hello world' ... return 'again' ... >>> >>> winter = generator_winter() >>> winter.__next__() 'hello world' >>> winter.__next__() Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration: again >>>

生成器的作用

说了这么多，生成器有什么用呢？作为python主要特性之一，这是个极其牛逼的东西，由于它是惰性的，在处理大型数据时，可以节省大量内存空间；

当你需要迭代一个巨大的数据集合，比如创建一个有规律的100万个数字，如果采用列表来存储访问，那么会占用大量的内存空间；而且如果我们只是访问这个列表的前几个元素，那么后边大部分元素占据的内存空间就白白浪费了；这时，如果采用生成器，则不必创建完整的列表，一次循环返回一个希望得到的值，这样就可以大量节省内存空间；

这里在举例之前，我们先介绍一个生成器表达式（类似于列表推导式，只是把[]换成()），这样就创建了一个生成器。

1
2
3
4

>>> gen = (x for x in range(10))
>>> gen
<generator object <genexpr> at 0x0000000002A923B8>
>>>

生成器表达式的语法如下：(expr for iter_var in iterable if cond_expr)
用生成器来实现斐波那契数列

1
2
3
4
5
6
7
8
9

def fib(n):
    a, b = 0, 1
    while b <= n:
        yield b
        a, b = b, a+b

f = fib(10)
for item in f:
    print(item)

生成器方法

直接看生成器源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class __generator(object):
    '''A mock class representing the generator function type.'''
    def __init__(self):
        self.gi_code = None
        self.gi_frame = None
        self.gi_running = 0

    def __iter__(self):
        '''Defined to support iteration over container.'''
        pass

    def __next__(self):
        '''Return the next item from the container.'''
        pass

    def close(self):
        '''Raises new GeneratorExit exception inside the generator to terminate the iteration.'''
        pass

    def send(self, value):
        '''Resumes the generator and "sends" a value that becomes the result of the current yield-expression.'''
        pass

    def throw(self, type, value=None, traceback=None):
        '''Used to raise an exception inside the generator.'''
        pass

首先看到了生成器是自带__iter__和__next__魔术方法的；

send

生成器函数最大的特点是可以接受外部传入的一个变量，并根据变量内容计算结果后返回。这是生成器函数最难理解的地方，也是最重要的地方，协程的实现就全靠它了。

看一个小猫吃鱼的例子：

1
2
3
4
5
6
7
8

def cat():
    print('我是一只hello kitty')
    while True:
        food = yield
        if food == '鱼肉':
            yield '好开心'
        else:
            yield '不开心，人家要吃鱼肉啦'

中间有个赋值语句food = yield，可以通过send方法来传参数给food，试一下：

情况1）

1
2
3

miao = cat()    #只是用于返回一个生成器对象，cat函数不会执行
print(''.center(50,'-'))
print(miao.send('鱼肉'))

结果：

1
2
3
4
5

Traceback (most recent call last):
--------------------------------------------------
  File "C:/Users//Desktop/Python/cnblogs/subModule.py", line 67, in <module>
    print(miao.send('鱼肉'))
TypeError: can't send non-None value to a just-started generator

看到了两个信息：

1. miao = cat() ，只是用于返回一个生成器对象，cat函数不会执行
2. can’t send non-None value to a just-started generator；不能给一个刚创建的生成器对象直接send值

改一下

情况2）

1
2
3

miao = cat()
miao.__next__()
print(miao.send('鱼肉'))

结果：

1
2

我是一只hello kitty
好开心

没毛病，那么到底send()做了什么呢？send()的帮助文档写的很清楚，'''Resumes the generator and "sends" a value that becomes the result of the current yield-expression.'''；可以看到send依次做了两件事：

1. 回到生成器挂起的位置，继续执行
2. 并将send(arg)中的参数赋值给对应的变量，如果没有变量接收值，那么就只是回到生成器挂起的位置

但是，我认为send还做了第三件事：
3. 兼顾__next__()作用，挂起程序并返回值，所以我们在print(miao.send('鱼肉'))时，才会看到’好开心’；其实__next__()等价于send(None)

所以当我们尝试这样做的时候：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def cat():
    print('我是一只hello kitty')
    while True:
        food = yield
        if food == '鱼肉':
            yield '好开心'
        else:
            yield '不开心，人家要吃鱼肉啦'

miao = cat()
print(miao.__next__())
print(miao.send('鱼肉'))
print(miao.send('骨头'))
print(miao.send('鸡肉'))

就会得到这个结果：

1
2
3
4
5

我是一只hello kitty
None
好开心
None
不开心，人家要吃鱼肉啦

我们按步骤分析一下：

1. 执行到print(miao.__next__())，执行cat()函数，print了”我是一只hello kitty”，然后在food = yield挂起，并返回了None，打印None
2. 接着执行print(miao.send('鱼肉'))，回到food = yield，并将’鱼肉’赋值给food，生成器函数恢复执行；直到运行到yield '好开心'，程序挂起，返回’好开心’，并print ‘好开心’
3. 接着执行print(miao.send('骨头'))，回到yield '好开心'，这时没有变量接收参数’骨头’，生成器函数恢复执行；直到food = yield，程序挂起，返回None，并print None
4. 接着执行print(miao.send('鸡肉'))，回到food = yield，并将’鸡肉’赋值给food，生成器函数恢复执行；直到运行到yield '不开心，人家要吃鱼肉啦'，程序挂起，返回’不开心，人家要吃鱼肉啦’，，并print ‘不开心，人家要吃鱼肉啦’

大功告成；那我们优化一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def cat():
    msg = '我是一只hello kitty'
    while True:
        food = yield msg
        if food == '鱼肉':
            msg = '好开心'
        else:
            msg = '不开心，人家要吃鱼啦'

miao = cat()
print(miao.__next__())
print(miao.send('鱼肉'))
print(miao.send('鸡肉'))

我们再看一个更实用的例子，一个计数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def counter(start_at = 0):
    count = start_at
    while True:
        val = (yield count)
        if val is not None:
            count = val
        else:
            count += 1

count = counter(5)
print(count.__next__())
print(count.__next__())
print(count.send(0))
print(count.__next__())
print(count.__next__())

结果：

1
2
3
4
5

5
6
0
1
2

close

帮助文档：'''Raises new GeneratorExit exception inside the generator to terminate the iteration.'''

手动关闭生成器函数，后面的调用会直接返回StopIteration异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

>>> def gene():
...   while True:
...     yield 'ok'
...
>>> g = gene()
>>> g.__next__()
'ok'
>>> g.__next__()
'ok'
>>> g.close()
>>> g.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

在close以后再执行__next__会触发StopIteration异常

throw

用来向生成器函数送入一个异常，throw()后直接抛出异常并结束程序，或者消耗掉一个yield，或者在没有下一个yield的时候直接进行到程序的结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

>>> def gene():
...   while True:
...     try:
...       yield 'normal value'
...     except ValueError:
...       yield 'we got ValueError here'
...     except TypeError:
...       break
...
>>> g = gene()
>>> print(g.__next__())
normal value
>>> print(g.__next__())
normal value
>>> print(g.throw(ValueError))
we got ValueError here
>>> print(g.__next__())
normal value
>>> print(g.throw(TypeError))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

通过yield实现单线程情况下的异步并发效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def consumer(name):
    print('%s准备吃包子了' % name)
    while True:
        baozi_name = yield
        print('[%s]来了，被[%s]吃了'% (baozi_name, name))

def producer(*name):
    c1 = consumer(name[0])
    c2 = consumer(name[1])
    c1.__next__()
    c2.__next__()
    for times in range(5):
        print('做了两个包子')
        c1.send('豆沙包%s'%times)
        c2.send('菜包%s'%times)

producer('winter', 'elly')

效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

winter准备吃包子了
elly准备吃包子了
做了两个包子
[豆沙包0]来了，被[winter]吃了
[菜包0]来了，被[elly]吃了
做了两个包子
[豆沙包1]来了，被[winter]吃了
[菜包1]来了，被[elly]吃了
做了两个包子
[豆沙包2]来了，被[winter]吃了
[菜包2]来了，被[elly]吃了
做了两个包子
[豆沙包3]来了，被[winter]吃了
[菜包3]来了，被[elly]吃了
做了两个包子
[豆沙包4]来了，被[winter]吃了
[菜包4]来了，被[elly]吃了

创建了两个独立的生成器，很有趣，很吊；

补充几个小例子：

使用生成器创建一个range

1
2
3
4
5

def range(n):
    count = 0
    while count < n:
        yield count
        count += 1

使用生成器监听文件输入

1
2
3
4
5
6
7
8

def fileTail(filename):
    with open(filename) as f:
        while True:
            tail = f.readline()
            if line:
                yield tail
            else:
                time.sleep(0.1)

计算移动平均值

1
2
3
4
5
6
7
8
9

def averager(start_with = 0):
    count = 0
    aver = start_with
    total = start_with
    while True:
        val = yield aver
        total += val
        count += 1
        aver = total/count

有个弊端，需要通过__next__或next()初始化一次，通过预激解决

预激计算移动平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def init(f):
    def wrapper(start_with = 0):
        g_aver = f(start_with)
        g_aver.__next__()
        return g_aver
    return wrapper

@init
def averager(start_with = 0):
    count = 0
    aver = start_with
    total = start_with
    while True:
        val = yield aver
        total += val
        count += 1
        aver = total/count

读取文件字符数最多的行的字符数

最传统的写法：

1
2
3
4

def longestLine(filename):
    with open(filename, 'r', encoding='utf-8') as f:
        alllines = [len(x.strip()) for x in f]
        return max(alllines)

使用生成器以后的写法：

1
2

def longestLine(filename):
    return max(len(x.strip()) for x in open(filename))

多生成器迭代

1
2
3
4
5
6
7
8
9
10
11
12
13

>>> g = (i for i in range(5))
>>> for j in g:
...   print(j)
...
0
1
2
3
4
>>> for j in g:
...   print(j)
...
>>>

因为for j in g， 每次循环执行一次g.next()；直到结束，触发StopIteration；

主意下面结果的输出：

1
2
3
4
5
6
7
8
9

>>> g = (i for i in range(4))
>>> g1 = (x for x in g)
>>> g2 = (y for y in g1)
>>>
>>> print(list(g1))
[0, 1, 2, 3]
>>> print(list(g2))
[]
>>>

为什么print(list(g2))为空呢？理一下，不然会乱：

看下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def g():
    print('1.1')
    for i in range(2):
        print('1.2')
        yield i
        print('1.3')

def g1():
    print('2.1')
    for x in s:
        print('2.2')
        yield x
        print('2.3')

def g2():
    print('3.1')
    for y in s1:
        print('3.2')
        yield y
        print('3.3')

s = g()
s1 = g1()
s2 = g2()
print('start first list')
print(list(s1))
print('start second list')
print(list(s2))

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

start first list
2.1
1.1
1.2
2.2
2.3
1.3
1.2
2.2
2.3
1.3
[0, 1]
start second list
3.1
[]

注意第11行之后，g触发了StopIteration，被for x in s捕捉，即不能继续s.__next__()了；同样的g1触发StopIteration，被list捕捉，即不能继续s1.__next__()了；于是打印[0,1]

当进行print(list(s2))时，执行s2.__next__()，停留在代码的第17行for y in s1，但是这是不能继续s1.__next__()了；于是直接触发了StopIteration；结果为[]

再看一个有意思的输出：

1
2
3
4
5
6
7
8
9

def add(n,i):
    return n+i

g = (i for i in range(4))

for n in [1,10]:
    g = (add(n,i) for i in g)

print(list(g))

输出为：[20, 21, 22, 23]

其实上面的代码翻译如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def add(n,i):
    return n+i

def g1():
    for i in g:
        yield add(n,i)

def g2():
    for i in s1:
        yield add(n,i)

n = 1
s1 = g1()
n = 10
s2 = g2()
print(list(s2))

最终n用的是10,

转自：https://www.cnblogs.com/deeper/p/7565571.html

迭代器是访问集合元素的一种方式。迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。迭代器只能往前不会后退，不过这也没什么，因为人们很少在迭代途中往后退。另外，迭代器的一大优点是不要求事先准备好整个迭代过程中所有的元素。迭代器仅仅在迭代到某个元素时才计算该元素，而在这之前或之后，元素可以不存在或者被销毁。这个特点使得它特别适合用于遍历一些巨大的或是无限的集合，比如几个G的文件。

特点：

1. 访问者不需要关心迭代器内部的结构，仅需通过next()方法或不断去取下一个内容
2. 不能随机访问集合中的某个值 ，只能从头到尾依次访问
3. 访问到一半时不能往回退
4. 便于循环比较大的数据集合，节省内存
5. 也不能复制一个迭代器。如果要再次（或者同时）迭代同一个对象，只能去创建另一个迭代器对象。enumerate()的返回值就是一个迭代器，我们以enumerate为例：

   1 2 3 4 5 6

   a = enumerate(['a','b']) for i in range(2): #迭代两次enumerate对象 for x, y in a: print(x,y) print(''.center(50,'-'))

   结果：

   1 2 3 4

   0 a 1 b -------------------------------------------------- --------------------------------------------------

可以看到再次迭代enumerate对象时，没有返回值；

我们可以用linux的文件处理命令vim和cat来理解一下：

1. 读取很大的文件时，vim需要很久，cat是毫秒级；因为vim是一次性把文件全部加载到内存中读取；而cat是加载一行显示一行
2. vim读写文件时可以前进，后退，可以跳转到任意一行；而cat只能向下翻页，不能倒退，不能直接跳转到文件的某一页（因为读取的时候这个“某一页“可能还没有加载到内存中）

正式进入python迭代器之前，我们先要区分两个容易混淆的概念：可迭代对象和迭代器；

• 可以直接作用于for循环的对象统称为 __可迭代对象(Iterable)__。
• 可以被next()函数调用并不断返回下一个值的对象称为 __迭代器(Iterator)__。

所有的Iterable均可以通过内置函数iter()来转变为Iterator。

可迭代对象

首先，可迭代对象是一个对象，不是一个函数；是一个什么样的对象呢？就是只要它定义了可以返回一个迭代器的__iter__方法，或者定义了可以支持下标索引的__getitem__方法，那么它就是一个可迭代对象。

python中大部分对象都是可迭代的，比如list，tuple等。如果给一个准确的定义的话，看一下list，tuple类的源码，都有__iter__(self)方法。

常见的可迭代对象：

1. 集合数据类型，如list、tuple、dict、set、str等；
2. generator，包括生成器和带yield的generator function。

注意：生成器都是Iterator对象，但list、dict、str虽然是Iterable，却不是Iterator

如何判断一个对象是可迭代对象呢？可以通过collections模块的Iterable类型判断：

1
2
3
4
5
6
7
8
9
10
11

>>> from collections import Iterable
>>> isinstance([], Iterable)
True
>>> isinstance({}, Iterable)
True
>>> isinstance('abc', Iterable)
True
>>> isinstance((x for x in range(10)), Iterable)
True
>>> isinstance(100, Iterable)
False

迭代器

一个可迭代对象是不能独立进行迭代的，Python中，迭代是通过for … in来完成的。

for循环在迭代一个可迭代对象的过程中都做了什么呢？

1. 当for循环迭代一个可迭代对象时，首先会调用可迭代对象的__iter__()方法，然我们看看源码中关于list类的__iter__()方法的定义：

   1 2 3

   def __iter__(self, *args, **kwargs): # real signature unknown """ Implement iter(self). """ pass

   __iter__()方法调用了iter(self)函数，我们再来看一下iter()函数的定义：

1
2
3
4
5
6
7
8
9
10

def iter(source, sentinel=None): # known special case of iter
    """
    iter(iterable) -> iterator
    iter(callable, sentinel) -> iterator
    
    Get an iterator from an object.  In the first form, the argument must
    supply its own iterator, or be a sequence.
    In the second form, the callable is called until it returns the sentinel.
    """
    pass

iter()函数的参数是一个可迭代对象，最终返回一个迭代器

2. for循环会不断调用迭代器对象的__next__()方法(python2.x中是next()方法)，每次循环，都返回迭代器对象的下一个值，直到遇到StopIteration异常。

1
2
3
4
5
6
7
8
9
10
11
12

>>> lst_iter = iter([1,2,3])
>>> lst_iter.__next__()
1
>>> lst_iter.__next__()
2
>>> lst_iter.__next__()
3
>>> lst_iter.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

这里注意：这里的__next__()方法和内置函数next(iterator, default=None)不是一个东西；(内置函数next(iterator, default=None)也可以返回迭代器的下一个值）

3. 而for循环可以捕获StopIteration异常并结束循环；

总结一下：

1. for….in iterable，会通过调用iter(iterable)函数（实际上，首先调用的对象的__iter__()方法），返回一个迭代器iterator;
2. 每次循环，调用一次对象的__next__(self)，直到最后一个值，再次调用会触发StopIteration
3. for循环捕捉到StopIteration，从而结束循环

上面说了这么多，到底什么是迭代器Iterator呢？

任何实现了__iter__和__next__()（python2中实现next()）方法的对象都是迭代器，__iter__返回迭代器自身，__next__返回容器中的下一个值；

既然知道了什么迭代器，那我们自定义一个迭代器玩玩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Iterator_test(object):
    def __init__(self, data):
        self.data = data
        self.index = len(data)

    def __iter__(self):
        return self

    def __next__(self):
        if self.index <= 0 :
            raise StopIteration
        self.index -= 1
        return self.data[self.index]

iterator_winter = Iterator_test('abcde')

for item in iterator_winter:
    print(item)

如何判断一个对象是一个迭代器对象呢？两个方法：

1. 通过内置函数next(iterator, default=None)，可以看到next的第一个参数必须是迭代器；所以迭代器也可以认为是可以被next()函数调用的对象
2. 通过collection中的Iterator类型判断

   1 2 3 4 5 6 7 8 9

   >>> from collections import Iterator >>> >>> isinstance([1,2,3], Iterator) False >>> isinstance(iter([1,2,3]), Iterator) True >>> isinstance([1,2,3].__iter__(), Iterator) True >>>

这里大家会不会有个疑问：

对于迭代器而言，看上去作用的不就是__next__方法嘛，__iter__好像没什么卵用，干嘛还需要__iter__方法呢？

我们知道，python中迭代是通过for循环实现的，而for循环的循环对象必须是一个可迭代对象Iterable，而Iterable必须是一个实现了__iter__方法的对象；知道为什么需要__iter__魔术方法了吧；

那么我就是想自定义一个没有实现__iter__方法的迭代器可以吗？可以，像下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Iterable_test(object):
    def __init__(self, data):
        self.data = data

    def __iter__(self):
        return Iterator_test(self.data)

class Iterator_test(object):
    def __init__(self, data):
        self.data = data
        self.index = len(data)

    def __next__(self):
        if self.index <= 0 :
            raise StopIteration
        self.index -= 1
        return self.data[self.index]

iterator_winter = Iterable_test('abcde')

for item in iterator_winter:
    print(item)

先定义一个可迭代对象（包含__iter__方法），然后该对象返回一个迭代器；这样看上去是不是很麻烦？是不是同时带有__iter__和__next__魔术方法的迭代器更好呢！

同时，这里要纠正之前的一个迭代器概念：只要__next__()（python2中实现next()）方法的对象都是迭代器；

既然这样，只需要迭代器Iterator接口就够了，为什么还要设计可迭代对象Iterable呢？

这个和迭代器不能重复使用有关，下面统一讲解：

总结和一些重要知识点

如何复制迭代器

之前在使用enumerate时，我们说过enumerate对象通过for循环迭代一次后就不能再被迭代：

1
2
3
4
5
6
7
8
9
10
11
12

>>> e = enumerate([1,2,3])
>>>
>>> for x,y in e:
...   print(x,y)
...
0 1
1 2
2 3
>>> for x,y in e:
...   print(x,y)
...
>>>

这是因为enumerate是一个迭代器；

迭代器是一次性消耗品，当循环以后就空了。不能再次使用；通过深拷贝可以解决；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

>>> import copy
>>>
>>> e = enumerate([1,2,3])
>>>
>>> e_deepcopy = copy.deepcopy(e)
>>>
>>> for x,y in e:
...   print(x,y)
...
0 1
1 2
2 3
>>> for x,y in e_deepcopy:
...   print(x,y)
...
0 1
1 2
2 3
>>>

为什么不只保留Iterator的接口而还需要设计Iterable呢？

因为迭代器迭代一次以后就空了，那么如果list，dict也是一个迭代器，迭代一次就不能再继续被迭代了，这显然是反人类的；所以通过__iter__每次返回一个独立的迭代器，就可以保证不同的迭代过程不会互相影响。而生成器表达式之类的结果往往是一次性的，不可以重复遍历，所以直接返回一个Iterator就好。让Iterator也实现Iterable的兼容就可以很灵活地选择返回哪一种。

总结说，Iterator实现的__iter__是为了兼容Iterable的接口，从而让Iterator成为Iterable的一种实现。

另外，迭代器是惰性的，只有在需要返回下一个数据时它才会计算。就像一个懒加载的工厂，等到有人需要的时候才给它生成值返回，没调用的时候就处于休眠状态等待下一次调用。所以，Iterator甚至可以表示一个无限大的数据流，例如全体自然数。而使用list是永远不可能存储全体自然数的。

通过__getitem__来实现for循环

前面关于可迭代对象的定义是这样的：定义了可以返回一个迭代器的__iter__方法，或者定义了可以支持下标索引的__getitem__方法，那么它就是一个可迭代对象。

但是如果对象没有__iter__，但是实现了__getitem__，会改用下标迭代的方式。

1
2
3
4
5
6
7
8
9

class NoIterable(object):
    def __init__(self, data):
        self.data = data
    def __getitem__(self, item):
        return self.data[item]

no_iter = NoIterable('abcde')
for item in no_iter:
    print(item)

当for发现没有__iter__但是有__getitem__的时候，会从0开始依次读取相应的下标，直到发生IndexError为止，这是一种旧的迭代方法。iter方法也会处理这种情况，在不存在__iter__的时候，返回一个下标迭代的iterator对象来代替。

一张图总结迭代器

使用迭代器来实现一个斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Fib(object):
    def __init__(self, limit):
        self.a, self.b = 0, 1
        self.limit = limit

    def __iter__(self):
        return self

    def __next__(self):
        self.a, self.b = self.b, self.a+self.b
        while self.a > self.limit:
            raise StopIteration
        return self.a

for n in Fib(1000):
    print(n)

转自：https://www.cnblogs.com/coderzh/articles/1202040.html

yield的英文单词意思是生产，刚接触Python的时候感到非常困惑，一直没弄明白yield的用法。只是粗略的知道yield可以用来为一个函数返回值塞数据，比如下面的例子：

1
2
3

def addlist(alist):
    for i in alist:
        yield i + 1

取出alist的每一项，然后把i + 1塞进去。然后通过调用取出每一项：

1
2
3

alist = [1, 2, 3, 4]
for x in addlist(alist):
    print x,

这的确是yield应用的一个例子。

包含yield的函数

假如你看到某个函数包含了yield，这意味着这个函数已经是一个Generator，它的执行会和其他普通的函数有很多不同。比如下面的简单的函数：

1
2
3
4
5

def h():
    print 'To be brave'
    yield 5

h()

可以看到，调用h()之后，print 语句并没有执行！这就是yield，那么，如何让print 语句执行呢？这就是后面要讨论的问题，通过后面的讨论和学习，就会明白yield的工作原理了。

yield是一个表达式

Python2.5以前，yield是一个语句，但现在2.5中，yield是一个表达式(Expression)，比如：

1

m = yield 5

表达式(yield 5)的返回值将赋值给m，所以，认为 m = 5 是错误的。那么如何获取(yield 5)的返回值呢？需要用到后面要介绍的send(msg)方法。

透过next()语句看原理

现在，我们来揭晓yield的工作原理。我们知道，我们上面的h()被调用后并没有执行，因为它有yield表达式，因此，我们通过next()语句让它执行。next()语句将恢复Generator执行，并直到下一个yield表达式处。比如：

1
2
3
4
5
6
7

def h():
    print 'Wen Chuan'
    yield 5
    print 'Fighting!'

c = h()
c.next()

c.next()调用后，h()开始执行，直到遇到yield 5，因此输出结果：Wen Chuan

当我们再次调用c.next()时，会继续执行，直到找到下一个yield表达式。由于后面没有yield了，因此会拋出异常：

1
2
3
4
5
6

Wen Chuan
Fighting!
Traceback (most recent call last):
  File "/home/evergreen/Codes/yidld.py", line 11, in <module>
    c.next()
StopIteration

send(msg) 与 next()

了解了next()如何让包含yield的函数执行后，我们再来看另外一个非常重要的函数send(msg)。其实next()和send()在一定意义上作用是相似的，区别是send()可以传递yield表达式的值进去，而next()不能传递特定的值，只能传递None进去。因此，我们可以看做

c.next() 和 c.send(None) 作用是一样的。

来看这个例子：

1
2
3
4
5
6
7
8
9
10

def h():
    print 'Wen Chuan',
    m = yield 5  # Fighting!
    print m
    d = yield 12
    print 'We are together!'

c = h()
c.next()  #相当于c.send(None)
c.send('Fighting!')  #(yield 5)表达式被赋予了'Fighting!'

输出的结果为：Wen Chuan Fighting!

需要提醒的是，第一次调用时，请使用next()语句或是send(None)，不能使用send发送一个非None的值，否则会出错的，因为没有yield语句来接收这个值。

send(msg) 与 next()的返回值

send(msg) 和 next()是有返回值的，它们的返回值很特殊，返回的是下一个yield表达式的参数。比如yield 5，则返回 5 。到这里，是不是明白了一些什么东西？本文第一个例子中，通过for i in alist 遍历 Generator，其实是每次都调用了alist.Next()，而每次alist.Next()的返回值正是yield的参数，即我们开始认为被压进去的东东。我们再延续上面的例子：

1
2
3
4
5
6
7
8
9
10
11

def h():
    print 'Wen Chuan',
    m = yield 5  # Fighting!
    print m
    d = yield 12
    print 'We are together!'

c = h()
m = c.next()  #m 获取了yield 5 的参数值 5
d = c.send('Fighting!')  #d 获取了yield 12 的参数值12
print 'We will never forget the date', m, '.', d

输出结果：

1
2

Wen Chuan Fighting!
We will never forget the date 5 . 12

throw() 与 close()中断 Generator

中断Generator是一个非常灵活的技巧，可以通过throw抛出一个GeneratorExit异常来终止Generator。Close()方法作用是一样的，其实内部它是调用了throw(GeneratorExit)的。我们看：

1
2
3
4
5
6
7
8

def close(self):
    try:
        self.throw(GeneratorExit)
    except (GeneratorExit, StopIteration):
        pass
    else:
        raise RuntimeError("generator ignored GeneratorExit")
# Other exceptions are not caught

因此，当我们调用了close()方法后，再调用next()或是send(msg)的话会抛出一个异常：

1
2
3
4

Traceback (most recent call last):
  File "/home/evergreen/Codes/yidld.py", line 14, in <module>
    d = c.send('Fighting!')  #d 获取了yield 12 的参数值12
StopIteration