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

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

Описание

В таблице $||a_{ij}|{|}_{m\times n}$, задающей объекты с известной классовой принадлежностью, пусть $S_1,\dots ,S_q\in K_1$, $S_{q+1},\dots ,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}\\ \dots & \dots & \dots \\ a_{ir}& a_{iu}& a_{iv}\\ \dots & \dots & \dots \\ a_{qr}& a_{qu}& a_{qv}\\ \\ a_{q+1r}& a_{q+1u}& a_{q+1v}\\ \dots & \dots & \dots \\ a_{jr}& a_{ju}& a_{jv}\\ \dots & \dots & \dots \\ a_{mr}& a_{mu}& a_{mv}\end{array}$

Среди первых $q$ строк выделяем и фиксируем все тройки, не совпадающие ни с одной из троек в строках $q+1,\dots ,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\dots b_r\dots b_u\dots b_v\dots b_n)$. Сравниваем все характеристики всех троек для $K_1$ с соответствующими тройками в распознаваемом объекте $S$. Число совпадений $(a_{ir},a_{iu},a_{iv})=(b_r,b_u,b_v)$ обозначаем $\mathrm{\Gamma }(S,K_1)$ — число голосов, поданных для S за класс $K_1$. Аналогично формируем величину $\mathrm{\Gamma }(S,K_2)$ — число совпадений $(a_{jr},a_{ju},a_{jv})=(b_r,b_u,b_v)$. Вводим пороговый параметр $\nu$. Если $\mathrm{\Gamma }(S,K_1)-\nu >\mathrm{\Gamma }(S,K_2)$, относим $S$ классу $K_1$, при $\mathrm{\Gamma }(S,K_2)-\nu >\mathrm{\Gamma }(S,K_1)$ — в класс $K_2$. В остальных случаях алгоритм отказывается от классификации. На практике часто полагают $\nu =0$.

Литература

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