多类有重叠问题的扩张矩阵算法

An Extension Matrix Algorithm for Multi class Problem with Overlay Area

示例学习是从某一概念的已给的正例集合和反例集合中归纳产生出描述所有正例并排除所有反例的该概念的一般规则，而扩张矩阵理论将寻找正例在反例背景下所满足的公式等价为在反例矩阵上找出一条生路．该文针对多类有重叠问题，改进了原有的扩张矩阵算法，引入了基于平均熵的最短公式近似解的启发式搜索，并利用势函数估计正、反例间重叠区域的概率密度函数，从而获得类间非线性判别界面．文章将此算法应用于手写汉字识别，通过分析比较。

Learning from examples is to obtain a general rule through induction from a given set of positive and negative examples of a concept, which may describe all the positive examples, and reject all the negative examples of that concept. According to the extension matrix theory, to discover the equations which satisfy all positive examples on the background of negative examples may be considered as to find a path within the matrix of negative examples. In order to deal with the multi class problems with overlay, an improved extension matrix algorithm has been proposed in this paper. The heuristic search based on average entropy has been used to get the approximate solutions of the shortest equation. The potential function is used to estimate the probability density function of the overlay area between positive and negative examples, so that the non linear interfaces of the interclass areas may be obtained. The improved algorithms have been applied to handwritten Chinese character recognition and its effectiveness has been proved through comparison study and analysis.