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

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

В таблице ${\displaystyle ||a_{ij}||_{m\times n}}$, задающей объекты с известной классовой принадлежностью, пусть ${\displaystyle S_{1},\ldots ,S_{q}\in K_{1}}$, ${\displaystyle S_{q+1},\ldots ,S_{m}\in K_{2}}$. Просматриваем все тройки признаков ${\displaystyle \{r,u,v\}}$ (число таких троек, очевидно, равно ${\displaystyle C_{n}^{3}}$ и анализируем часть таблицы информационных векторов ${\displaystyle T_{1}}$ из обучающей выборки, составленную из столбцов ${\displaystyle r,u,v}$: ${\displaystyle {\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}}}$

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

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