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

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

Описание

В таблице [math]\displaystyle{ ||a_{ij}||_{m\times n} }[/math], задающей объекты с известной классовой принадлежностью, пусть [math]\displaystyle{ S_1,\ldots,S_q\in K_1 }[/math], [math]\displaystyle{ S_{q+1},\ldots,S_m\in K_2 }[/math]. Просматриваем все тройки признаков [math]\displaystyle{ \{r, u, v\} }[/math] (число таких троек, очевидно, равно [math]\displaystyle{ C_n^3 }[/math] и анализируем часть таблицы информационных векторов [math]\displaystyle{ T_1 }[/math] из обучающей выборки, составленную из столбцов [math]\displaystyle{ r,u,v }[/math]: [math]\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} }[/math]

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

Литература

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