КОРА (алгоритм)

Алгоритм Кора́ (комбинаторного распознавания) — алгоритм классификации (взвешенного голосования правил), предложенный М. Вайнцвайгом и М. Бонгардом в 1973 г.^[1] (основы были заложены в одноимённой программе, разработка которой началась в 1961 г.) Применяется для классификации множества $M$, характеризующегося вектором бинарных признаков $M_i=\{0,1\},i=1\ldots n$, чаще всего, для задач с двумя непересекающимися классами. Данный алгоритм строит набор конъюнктивных закономерностей и доказал свою эффективность при решении практических задач.

Описание

В таблице $||a_{ij}||_{m\times n}$, задающей объекты с известной классовой принадлежностью, пусть $S_1,\ldots,S_q\in K_1$, $S_{q+1},\ldots,S_m\in K_2$. Просматриваем все тройки признаков $\{r, u, v\}$ (число таких троек, очевидно, равно $C_n^3$ и анализируем часть таблицы информационных векторов $T_1$ из обучающей выборки, составленную из столбцов $r,u,v$: $\begin{array}{ccc} a_{1r} & a_{1u} & a_{1v} \\ a_{2r} & a_{2u} & a_{2v} \\ \ldots & \ldots & \ldots \\ a_{ir} & a_{iu} & a_{iv} \\ \ldots & \ldots & \ldots \\ a_{qr} & a_{qu} & a_{qv} \\ \hline\\ a_{q+1r} & a_{q+1u} & a_{q+1v} \\ \ldots & \ldots & \ldots \\ a_{jr} & a_{ju} & a_{jv} \\ \ldots & \ldots & \ldots \\ a_{mr} & a_{mu} & a_{mv} \\ \end{array}$

Среди первых $q$ строк выделяем и фиксируем все тройки, не совпадающие ни с одной из троек в строках $q+1,\ldots,m$. Формируем множество таких троек $\{(a_{ir},a_{iu},a_{iv})\}$. Аналогично выделяем все тройки $\{(a_{jr},a_{ju},a_{jv})\}$, не совпадающие ни с одной из первых $q$ троек. Множества $\{(a_{ir},a_{iu},a_{iv})\}, \{(a_{jr},a_{ju},a_{jv})\}$ назовем, соответственно, характеристиками классов $K_1, K_2$. Такие характеристики формируем для всех троек $(r, u, v)$. Пусть задан для распознавания объект $S=(b_1\ldots b_r\ldots b_u\ldots b_v\ldots b_n)$. Сравниваем все характеристики всех троек для $K_1$ с соответствующими тройками в распознаваемом объекте $S$. Число совпадений $(a_{ir},a_{iu},a_{iv})=(b_{r},b_{u},b_{v})$ обозначаем $\Gamma(S, K_1)$ — число голосов, поданных для S за класс $K_1$. Аналогично формируем величину $\Gamma(S, K_2)$ — число совпадений $(a_{jr},a_{ju},a_{jv})=(b_{r},b_{u},b_{v})$. Вводим пороговый параметр $\nu$. Если $\Gamma(S, K_1)-\nu>\Gamma(S, K_2)$, относим $S$ классу $K_1$, при $\Gamma(S, K_2)-\nu>\Gamma(S, K_1)$ — в класс $K_2$. В остальных случаях алгоритм отказывается от классификации. На практике часто полагают $\nu=0$.

Литература

1. Ю. И. Журавлёв. Математические основы теории прогнозирования. Лекции (2008 г.)
2. К. В. Воронцов. Лекции по логическим алгоритмам классификации. 2007.

Примечания

1. ↑ Вайнцвайг М. Н. Алгоритм обучения распознаванию образов "кора" // Алгоритмы обучения распознаванию образов / Под ред. В. Н. Вапник. М.: Советское радио, 1973. С. 110–116.