Русская Википедия:КОРА (алгоритм)
Алгоритм Кора́ (комбинаторного распознавания) — алгоритм классификации (взвешенного голосования правил), предложенный М. Вайнцвайгом и М. Бонгардом в 1973 г.[1] (основы были заложены в одноимённой программе, разработка которой началась в 1961 г.) Применяется для классификации множества <math>M</math>, характеризующегося вектором бинарных признаков <math>M_i=\{0,1\},i=1\ldots n</math>, чаще всего, для задач с двумя непересекающимися классами. Данный алгоритм строит набор конъюнктивных закономерностей и доказал свою эффективность при решении практических задач.
Описание
В таблице <math>||a_{ij}||_{m\times n}</math>, задающей объекты с известной классовой принадлежностью, пусть <math>S_1,\ldots,S_q\in K_1</math>, <math>S_{q+1},\ldots,S_m\in K_2</math>. Просматриваем все тройки признаков <math>\{r, u, v\}</math> (число таких троек, очевидно, равно <math>C_n^3</math> и анализируем часть таблицы информационных векторов <math>T_1</math> из обучающей выборки, составленную из столбцов <math>r,u,v</math>: <math>\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>q</math> строк выделяем и фиксируем все тройки, не совпадающие ни с одной из троек в строках <math>q+1,\ldots,m</math>. Формируем множество таких троек <math>\{(a_{ir},a_{iu},a_{iv})\}</math>. Аналогично выделяем все тройки <math>\{(a_{jr},a_{ju},a_{jv})\}</math>, не совпадающие ни с одной из первых <math>q</math> троек. Множества <math>\{(a_{ir},a_{iu},a_{iv})\}, \{(a_{jr},a_{ju},a_{jv})\}</math> назовем, соответственно, характеристиками классов <math>K_1, K_2</math>. Такие характеристики формируем для всех троек <math>(r, u, v)</math>. Пусть задан для распознавания объект <math>S=(b_1\ldots b_r\ldots b_u\ldots b_v\ldots b_n)</math>. Сравниваем все характеристики всех троек для <math>K_1</math> с соответствующими тройками в распознаваемом объекте <math>S</math>. Число совпадений <math>(a_{ir},a_{iu},a_{iv})=(b_{r},b_{u},b_{v})</math> обозначаем <math>\Gamma(S, K_1)</math> — число голосов, поданных для S за класс <math>K_1</math>. Аналогично формируем величину <math>\Gamma(S, K_2)</math> — число совпадений <math>(a_{jr},a_{ju},a_{jv})=(b_{r},b_{u},b_{v})</math>. Вводим пороговый параметр <math>\nu</math>. Если <math>\Gamma(S, K_1)-\nu>\Gamma(S, K_2)</math>, относим <math>S</math> классу <math>K_1</math>, при <math>\Gamma(S, K_2)-\nu>\Gamma(S, K_1)</math> — в класс <math>K_2</math>. В остальных случаях алгоритм отказывается от классификации. На практике часто полагают <math>\nu=0</math>.
Литература
- Ю. И. Журавлёв. Математические основы теории прогнозирования. Лекции (2008 г.)
- К. В. Воронцов. Лекции по логическим алгоритмам классификации. 2007.
Примечания
- ↑ Вайнцвайг М. Н. Алгоритм обучения распознаванию образов "кора" // Алгоритмы обучения распознаванию образов / Под ред. В. Н. Вапник. М.: Советское радио, 1973. С. 110–116.
