WikiSort.ru - Не сортированное

Алгоритм Кора́ (комбинаторного распознавания) — алгоритм классификации (взвешенного голосования правил), предложенный М. Вайнцвайгом и М. Бонгардом в 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.

Примечания