Instance Based Classifiers

keyword：IBC、rote-learner、nearest neighbor

分类方法

KNN算法（k-Nearest-Neighbor)

• 思想：在数据集中找到k个最近的邻居样本，然后通过这些样本的特点来决定当前样本的属性。
• 算法概述：当我们需要预测一个新样本的输出时，KNN 算法将会遍历整个数据集来寻找 k 个最接近的样本，或者说是 k 个和新样本最相似的样本。然后，如果是一个回归问题，算法将输出这些样本结果的均值；如果是一个分类问题，算法将会输出出现次数最多的类别。k 的值是用户自己选定的。
• 距离计算方法：样本之间的相似度通过计算例如欧几里得距离（Euclidean distance）或者汉明距离（Hamming distance）得到。
  • 使用欧式距离计算距离，可能会导致多特点吻合的两个样本 & 多特点都缺失的两个样本的欧式距离计算结果相同，但实际上两者的关联度是不一样的

• 提出权重的概念：权重因子w与距离d之间的关系（西瓜书中）

  w = 1/d²
  

• k-近邻算法使用所有的数据作为训练数据集，而不是把数据集分为训练集和测试集。

• k的选择：
  • k很小，效果会对样本中的“噪声点”很敏感
  • k很大，邻居样本会包括大量的别类的样本点

• KNN的特点：

  • 懒惰的学习分类器
  • 不需要显式地（explicitly）建模
  • 能够产生任意形状的决策根页面
  • 能够动态调整样本的变化，结果与样本是交互的（因为它是基于当前信息的）
  • 选择一个距离度量的方式是很关键的
  • ?走神了

• 提升KNN效率：

  • 在计算距离的时候，避免计算所有的object
    • k-d trees
    • Fast approximate similarity search
    • LSH(Locality Sensitive Hashing）
  • 构造一个更小的数据集，同时保持当前的性能
  • 移除一些object

聚类方法（clusting)

聚类的定义：

将一些样本聚类成不同的组（簇）

分类方法：

• Hard（Crisp）：一个样本只能属于一个组（簇），不能够同时属于多个组
• Soft（Fuzzy）：一个样本可能同时属于多个组，且属于某个组有对应的概率

聚类的目标：使得簇内的样本很相似（同簇的样本距离尽可能近，不同的簇内的样本的距离尽可能远）

SSE：Error of Sum of Squares

outline：

• 待填

K-means算法:

• 定义:K-means是一个把相似的数据分组的迭代算法。它计算 k 个聚类的重心然后向这个聚类中添加一个数据点，使其与重心的距离最小。

算法步骤：

K-means 算法的步骤

1. k-means 初始化

   a) 选择一个 k 的值。在这里，我们令 k 等于 3。

   b) 随机地把数据点放到 3 个聚类中。

   c) 分别计算每个聚类的质心。图中红色、蓝色和绿色星星表示每个聚类的质心。

2. 把每个观察结果放入一个聚类中

   重新把每个最靠近质心的点放入聚类中。在这里，上面的 5 个点被放入了蓝色的质心对应的聚类中。按照相同的步骤将点分配给包含红色和绿色质心的聚类。

3. 重新计算质心

   计算每一个新聚类的质心。旧的质心以灰色显示，新的质心以红色、绿色和蓝色星星显示。

4. 迭代直到没有新的变化

   重复步骤二和步骤三，直到数据点不在聚类与聚类之间交换。一旦两次连续的步骤之间没有点的交换，就退出 k-means 算法。

EM Algorithm

• 最大期望算法（Expectation-maximization algorithm，又译期望最大化算法），是一种迭代方法。
• 典型：求解高斯混合模型，隐马尔科夫模型
• 算法概述：在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。

• 最大期望算法经过两个步骤交替进行计算（wiki上)：

  • 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
  • 第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

• EM求解过程（PPT）：

  • 初始化参数：先初始化正态分布的参数，包括均值和方差
  • 计算每一个样本更可能属于某个类
  • 通过分为某个类的样本数来重新估计该分布的参数（最大似然估计），对每个类进行同样操作，更新分布
  • 此时不同类的分布的概率更改，重复上述步骤直到2参数不发生变化为止

• 中心极限定理：在适当的条件下，大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布。

• Jensen不等式：
  • 如果f（x）是凸函数，x是随机变量，则下面的不等式成立：
    • E(f(x)) >= f(E(x))
    • E是数学期望
      • 对于离散型随机变量，数学期望是求和
      • 对于连续型随机变量，数学期望是求定积分

Multivariate Gaussian models（多元正态分布）

• 多变量正态分布亦称为多变量高斯分布。

• 先验

• 后验