1. 算法流程

? ? ? ? ?OC1 算法大部分情况下使用确定性爬山来确保计算精度，还使用了两种随机化来避免陷入局部最小值，通过限制随机选择超平面的数量减少运行时间。

2. 扰动算法

? ? ? ? OC1 算法对超平面的方向没有限制，然而，为了接近标准的决策树算法，超平面首先被设置为该结点上效果最好的轴平行平面（即单变量决策树做出的平面）。OC1 算法只有在斜平面优于单变量平面的情况下才进行。

? ? ? ? 通过扰动现在的超平面使它偏移来寻找可能的超平面，由于超平面的存在数量是指数级，无法简单的枚举，需要一定的手段来限制（如确定性启发式搜索，模拟退火），OC1结合了这两个想法，使用启发式搜索直到它得到一个局部最小值，然后使用一个非确定性搜索步骤（不是模拟退火）来得到一个局部最小值。

? ? ? ? 假设算法输入样本集 T 的数量为 n ，样本的属性维度是 d ，一共有 k 个类别。 $T_{j}=(x_{j1}, x_{j2}, ... ,x_{jd}, C_{j})$ ?表示T中的第 j 个样本， $C_{j}$ ?是样本类别。则决策树当前结点的超平面方程为：

$\sum_{i=1}^{d}a_{i}x_{i} + a_{d+1}=0$

? ? ? ? 将样本集 Tj 代入到上述公式中可以得到如下公式：

$\sum_{i=1}^{d}a_{i}x_{ji} + a_{d+1}=V_{j}$

? ? ? ? 通过? $V_{j}$ ?的正负可以判断该样本是在超平面的上方还是下方，假定如果? $V_{j}>0$ ?意味着样本点在超平面 H 的上方，如果超平面 H 可以完美的划分训练集 T ，则所有的同一类的样本点代入上述公式后得到的? $V_{j}$ ?符号相同。

????????OC1 算法一次调整超平面 H 的一个系数，在每次调整中确定该系数的局部最优值，如在调整系数? $a_{m}$ ?中，只将? $a_{m}$ ?视作变量，将其他系数视作常量，因此? $V_{j}$ ?可以视作? $a_{m}$ ?的函数，也就是? $V_{j}(a_{m})=a_{m}x_{jm} + \sum_{i=1,i\neq m}^{d}a_{i}x_{ji}+a_{d+1}$

? ? ? ? 如果假定样本点在超平面 H 的上方，可以得到：

$V_{j}>0$

$a_{m}>\frac{a_{m}x_{jm}-V_{j}}{x_{jm}} = U_{j}$

? ? ? ? 如果对输入的样本点提前做好规范化处理，则? $x_{jm}>0$ ?，对样本集 T 中的所有点，有相同类的点在同一方向，所以将所有的样本点插入到上面公式，就可以得到 n 个关于? $a_{m}$ ?的约束方程。（比如假定样本 $T_{1}, T_{2}$ ?属于同一类且都在该超平面 H 的上方，则可得到两个约束 $a_{m}>U_{1}, a_{m}>U_{2}$ ）

? ? ? ? 由此问题就转化为找到一个尽可能多的满足上述方程组的解。解决方案如下：对所有的? $U_{j}$ ?值排序，然后将? $a_{m}$ ?值设为每一对不同值的中间；设? $H_{1}$ ?是改变? $a_{m}$ ?后得到的新超平面，计算新超平面的不纯度，如果不纯度降低，则用它替换原有的超平面。如果两者拥有相同的不纯度，则以概率 P 代替原来的超平面。

? ? ? ? 算法流程如下：

? ? ? ? 现在已经阐述了超平面扰动的算法，接下来需要选定如何选择 d+1 个系数来扰动，有顺序、最佳和随机三种方式。

顺序：For i=1 to d, Perturb(H, i)
最佳：重复直到系数 m 没有修改。m=扰动过程中最大限度改善不纯度时的值，然后调用 Perturb(H, m)
随机：令 m 为随机值，重复一定次数，调用上述函数

? ? ? ? 系数选择方式不会对分类精确度产生较大的影响。

2. 随机化

? ? ? ? 当扰动算法达到局部最小时，算法停止。OC1 算法使用两种随机化方法跳出随即最小化。第一个方法是将超平面 H 移动一个随机向量，另一种是重新调用扰动算法并给出一个不同的初始超平面。

2.1 移动超平面

? ? ? ? 当系统陷入局部最小化时，它选择一个随机的向量并将该向量添加到当前超平面的系数之中，然后计算沿当前扰动方向的最佳超平面。具体的说是，OC1 算法重复以下步骤 J 次（J由用户决定）：

选定一个随机的向量? $R=(r_{1},r_{2},...,r_{d+1})$
令参数? $\alpha$ ?作为我们想让超平面 H 在方向 R 上的移动量，也就是 $H_{1} = \sum_{i=1}^{d}(a_{i}+\alpha r_{i})x_{i}+(a_{d+1}+\alpha r_{d+1})$
找到最佳的参数? $\alpha$
如果? $H_{1}$ ?可以降低划分的不纯度，则用它代替原有的超平面 H 并退出循环。否则重复 1