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

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

ОписаниеПравить

В таблице $||a_{ij}|{|}_{m\times <!--\; \times \; -->n}$$||a_{ij}||_{m\times n}$ , задающей объекты с известной классовой принадлежностью, пусть $S_1,\dots <!--\; \dots \; -->,S_q\in <!--\; \in \; -->K_1$$S_{1},\ldots ,S_{q}\in K_{1}$ , $S_{q+1},\dots <!--\; \dots \; -->,S_m\in <!--\; \in \; -->K_2$$S_{q+1},\ldots ,S_{m}\in K_{2}$ . Просматриваем все тройки признаков $\{r,u,v\}$$\{r,u,v\}$  (число таких троек, очевидно, равно $C_n^3$$C_{n}^{3}$  и анализируем часть таблицы информационных векторов $T_1$$T_{1}$  из обучающей выборки, составленную из столбцов $r,u,v$$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$  строк выделяем и фиксируем все тройки, не совпадающие ни с одной из троек в строках $q+1,\dots <!--\; \dots \; -->,m$$q+1,\ldots ,m$ . Формируем множество таких троек $\{(a_{ir},a_{iu},a_{iv})\}$$\{(a_{ir},a_{iu},a_{iv})\}$ . Аналогично выделяем все тройки $\{(a_{jr},a_{ju},a_{jv})\}$$\{(a_{jr},a_{ju},a_{jv})\}$ , не совпадающие ни с одной из первых $q$$q$  троек. Множества $\{(a_{ir},a_{iu},a_{iv})\},\{(a_{jr},a_{ju},a_{jv})\}$$\{(a_{ir},a_{iu},a_{iv})\},\{(a_{jr},a_{ju},a_{jv})\}$  назовем, соответственно, характеристиками классов $K_1,K_2$$K_{1},K_{2}$ . Такие характеристики формируем для всех троек $(r,u,v)$$(r,u,v)$ . Пусть задан для распознавания объект $S=(b_1\dots <!--\; \dots \; -->b_r\dots <!--\; \dots \; -->b_u\dots <!--\; \dots \; -->b_v\dots <!--\; \dots \; -->b_n)$$S=(b_{1}\ldots b_{r}\ldots b_{u}\ldots b_{v}\ldots b_{n})$ . Сравниваем все характеристики всех троек для $K_1$$K_1$  с соответствующими тройками в распознаваемом объекте $S$$S$ . Число совпадений $(a_{ir},a_{iu},a_{iv})=(b_r,b_u,b_v)$$(a_{ir},a_{iu},a_{iv})=(b_{r},b_{u},b_{v})$  обозначаем $\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_1)$$\Gamma (S,K_{1})$  — число голосов, поданных для S за класс $K_1$$K_1$ . Аналогично формируем величину $\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_2)$$\Gamma (S,K_{2})$  — число совпадений $(a_{jr},a_{ju},a_{jv})=(b_r,b_u,b_v)$$(a_{jr},a_{ju},a_{jv})=(b_{r},b_{u},b_{v})$ . Вводим пороговый параметр $\mathrm{\nu <!--\; \nu \; -->}$$\nu$ . Если $\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_1)-<!--\; -\; -->\mathrm{\nu <!--\; \nu \; -->}>\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_2)$$\Gamma (S,K_{1})-\nu >\Gamma (S,K_{2})$ , относим $S$$S$  классу $K_1$$K_1$ , при $\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_2)-<!--\; -\; -->\mathrm{\nu <!--\; \nu \; -->}>\mathrm{\Gamma <!--\; \Gamma \; -->}(S,K_1)$$\Gamma (S,K_{2})-\nu >\Gamma (S,K_{1})$  — в класс $K_2$$K_{2}$ . В остальных случаях алгоритм отказывается от классификации. На практике часто полагают $\mathrm{\nu <!--\; \nu \; -->}=0$$\nu =0$ .

ЛитератураПравить

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