Аннотация. 

Рассматривается логический подход к задаче классификации по прецедентам. Предполагается, что прецеденты описаны в системе числовых признаков, каждый из которых имеет ограниченное число значений и кодируется целыми числами. Этап обучения классификатора заключается в поиске специальных фрагментов в признаковых описаниях прецедентов, позволяющих различать их из разных классов и называемых представительными элементарными классификаторами. Традиционно важным для рассматриваемого подхода является получение оценок количественных характеристик множества искомых элементарных классификаторов. В работе приведена верхняя асимптотическая оценка типичного числа так называемых правильных представительных элементарных классификаторов и оценка типичного «ранга» такого элементарного классификатора для важного в практическом отношении случая, когда число прецедентов существенно больше числа признаков.

Ключевые слова: 

классификация по прецедентам, правильный представительный элементарный классификатор, правильная подматрица целочисленной матрицы, асимптотические оценки типичного числа и порядка правильных подматриц.

DOI: 10.14357/20790279240402

EDN: KADXXE

Литература

1. Бонгард М.М. Проблема узнавания. М.Ж. Физматгиз. 1967. 321 c.

2. Crama, Y., Hammer P.L., Ibaraki T. Causeeffect relationships and partially defined Boolean functions // Ann. Oper. Res. 1988. Vol. 16. Iss. 1. P. 299–325.

3. Дюкова Е.В., Журавлёв Ю.И. Задача монотонной дуализации и её обобщения: асимптотические оценки числа решений // Ж. вычисл. матем. и матем. физ. 2018. Т. 58. № 12. С. 2153–2168.

4. Хачиян Л. Г. Избранные труды. М.: МЦНМО. 2009. 519 с.

5. Dragunov N., Djukova E., Djukova А. Supervised classification and finding frequent elements in data // 8th Conference (International) on Information Technology and Nanotechnology Proceedings. NJ: IEEE. 2022. Р. 5.

6. Драгунов Н.А., Дюкова Е.В., Дюкова А.П. Логическая классификация на основе поиска правильных представительных элементарных классификаторов // Известия РАН. Теория и системы управления. 2024. № 3 (в печати).

7. Charu C. Aggarwal, Jiawei Han. Frequent Pattern Mining. Springer International Publishing. 2014. 471 p.

8. Дюкова Е.В., Дюкова А.П. О методах машинного обучения в задаче предсказания промотеров // Доклады Международной конференции «Математическая биология и биоинформатика». 2024. Т 10. № е42. С. 1–4.

9. Дюкова Е.В., Дюкова А.П. О числе решений некоторых специальных задач логического анализа целочисленных данных // Известия РАН. Теория и системы управления. 2023. № 5. С. 57–66.

10. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 5. С. 741–753.

11. Носков В.Н., Слепян В.А. О числе тупиковых тестов для одного класса таблиц // Кибернетика. 1972. № 1. С. 60–65.