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

Алгоритм Кора́ (комбинаторного распознавания) — алгоритм классификации (взвешенного голосования правил), предложенный М. Вайнцвайгом и М. Бонгардом в 1973 г. (основы были заложены в одноимённой программе, разработка которой началась в 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$.

Литература

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