分段线性判别函数是一种特殊的非线性函数，它确定的决策面是由若干超平面组成的。由于它的基本组成仍然是超平面，因此与一般超平面（例如贝叶斯决策面）相比，仍然是简单的，但又能逼近各种形状的超平面，具有很强的适应能力，见图2.1。

图2.1　线性和非线性分类器示意图

一般来说，如果对于ω_i类取l_i个代表点，或者说，把属于ω_i类的样本区域R_i分成l_i个子区域，即，其中表示第i类的第l个子区域，用表示该子区域中样本的均值向量，并以此作为该子区域的代表点，这样可定义如下判别函数

若有

则这样的分类器称为分段线性距离分类器，这时的决策面是两类期望连线的垂直平分面。

由于将均值向量作为代表点来设计最小距离分类器只有在某些特殊情况下才能得到较好的分类结果，因此在很多情况下并不适用。但如果把每一类分成若干个子类，即令，同时不是选择各子类的均值作为代表点设计最小距离分类器，而是对于每个子类定义一个线性判别函数

其中，分别称为对子类的权向量和阈值权。

再定义ω_i类的线性判别函数为

则对于M类问题，有M个判别函数d_i（X），并得到决策规则

现在的关键问题是如何利用样本集确定子类数目以及如何求得各子类的权向量和阈值权。

（1）已知子类数目，不知子类划分情况

当已知子类数目但不知子类划分情况时，可利用错误修正算法设计分段线性分类器。

①首先给定各子类的初始权向量。假设ω_i类中有l_i个子类，则任意给定

②利用训练集进行迭代，并按下列规则修改权向量：

若在第k次迭代时，ω_i类中的样本y_j与ω_i类的某个权向量的内积为最大，即

而且满足这个内积在所有其他类中也是最大的，即

则说明权向量组

不影响y_j正确分类，因此各权向量保持不变。如果存在某个或几个子类不满足上述条件，即存在，使得

则说明y_j被错误分类，需要对权向量进行修正，修正算法为

③重复上述的迭代过程，直到算法收敛或达到规定的迭代次数为止。

当样本集对于给定的子类数目能用分段线性判别函数完全正确分类时，算法将在有限步内收敛，否则算法不收敛。可以考虑用递减的ρ_k序列令算法收敛。

（2）未知子类数目

当每类应分成的子类数目也未知时，这是最一般的情况。在这种情况下，设计分段线性分类器的方法很多，树状分段线性分类器即是其中的一种。

对于图2.2所示的两类情况，可先用两类线性判别函数算法找一个权向量w₁，它所对应的超平面A把整个样本集分成两部分，称之为样本子集。由于样本集不是线性可分的，因此每一部分仍包含两类样本。

图2.2　树状决策过程

接着再利用算法找出第二个权向量w₂、第三个权向量w₃，超平面B、C分别把相应的样本子集分成两部分。若每一部分仍包含两类样本，则继续上述过程，直到某一权向量把两类样本完全分开为止。

这样得到的分类器也是分段线性的，其决策面如图中虚线表示，箭头表示权向量的方向，它指向超平面的正侧，它的识别过程是一个树状结构，如图2.2所示。