СРАВНЕНИЕ ЧИСЛЕННЫХ РЕАЛИЗАЦИЙ АЛГОРИТМА РАСЧЁТА ВЗАИМНОЙ ИНФОРМАЦИИ НА ОСНОВЕ УЧЁТА БЛИЖАЙШИХ СОСЕДЕЙ
Образец для цитирования:
Цель. Сравнить эффективность реализации различных подходов к оцениванию функции взаимной информации на основе учёта ближайших соседей.
Метод. Численно реализованы два подхода к вычислению функции взаимной информации: лобовой, основанный на поиске ближайших соседей перебором, и сортировочный, основанный на сортировке одного из наблюдаемых рядов.
Результаты. Показано, что алгоритмическая сложность сортировочного метода ниже, чем лобового, но выше, чем алгоритмическая сложность самой сортировки, реализованной любым из методов быстрой сортировки.
Обсуждение. Реализация сортировочного алгоритма оправдана в случае, если приходится иметь дело с выборками большой длины, в то время как для сравнительно небольших выборок (порядка сотен отсчётов) можно ограничиться лобовым подходом.
1. Fraser A.M., Swinney H.L. Independent coordinates for strange attractors from mutual information // Phys. Rev. A. 1986. Vol. 33. 1134.
2. Wells W.M., Viola P., Atsumi H., Nakajima Sh., Kikinis R. Multi-modal volume registration by maximization of mutual information // Medical Image Analysis. 1996. Vol. 1. Iss. 1. Pp. 35–51.
3. Pluim J.P.W., Maintz J.B.A., Viergever M.A. Mutual-information-based registration of medical images: a survey // IEEE Transac. on Medical Imaging, 2003. Vol. 22, Iss. 8. Pp. 986–1004.
4. Paninski L. Estimation of Entropy and Mutual Information // Neural Computation. 2003. Vol. 15. Pp. 1191–1253.
5. Church K.W., Hanks P. Word association norms, mutual information, and lexicography // Computational Linguistics. 1990. Vol. 16, Iss. 1. Pp. 22–29.
6. Moddemeijer R. On estimation of entropy and mutual information of continuous distributions // Signal Processing. 1989. Vol. 16, Iss. 3. Pp. 233–248.
7. Ai-Hua Jiang, Xiu-Chang Huang, Zhen-Hua Zhang, Jun Li, Zhi-Yi Zhang, Hong-Xin Hua. Mutual information algorithms // Mechanical Systems and Signal Processing. 2010. Vol. 24. Pp. 2947–2960.
8. Il-Moon Yo., Rajagopalan B., Lall U. // Estimation of mutual information using kernel density estimators // Phys. Rev. E. 1995. Vol. 52(3). Pp. 2318–2321.
9. Kraskov A., St ̈ogbauer H., Grassberger P. Estimating mutual information // Phys. Rev. E. 2004. Vol. 69. 066138.
10. Abramowitz M., Stegun I.A., eds. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (10th ed.). New York: Dover. 1972. Pp. 258–259.
11. Schreiber Th. Measuring Information Transfer // Phys. Rev. Lett. 2000. Vol. 85. Pp. 461–464.
12. McGill W.J. Multivariate information transmission // Psychometrika. 1954. Vol. 19. Pp. 97–116.
BibTeX
author = {Илья Вячеславович Сысоев},
title = {СРАВНЕНИЕ ЧИСЛЕННЫХ РЕАЛИЗАЦИЙ АЛГОРИТМА РАСЧЁТА ВЗАИМНОЙ ИНФОРМАЦИИ НА ОСНОВЕ УЧЁТА БЛИЖАЙШИХ СОСЕДЕЙ},
year = {2016},
journal = {Известия высших учебных заведений. Прикладная нелинейная динамика},
volume = {24},number = {4},
url = {https://old-andjournal.sgu.ru/ru/articles/sravnenie-chislennyh-realizaciy-algoritma-raschyota-vzaimnoy-informacii-na-osnove-uchyota},
address = {Саратов},
language = {russian},
doi = {10.18500/0869-6632-2016-24-4-86-95},pages = {86--95},issn = {0869-6632},
keywords = {Взаимная информация,метод ближайших соседей,быстрая сортировка.},
abstract = {Цель. Сравнить эффективность реализации различных подходов к оцениванию функции взаимной информации на основе учёта ближайших соседей. Метод. Численно реализованы два подхода к вычислению функции взаимной информации: лобовой, основанный на поиске ближайших соседей перебором, и сортировочный, основанный на сортировке одного из наблюдаемых рядов. Результаты. Показано, что алгоритмическая сложность сортировочного метода ниже, чем лобового, но выше, чем алгоритмическая сложность самой сортировки, реализованной любым из методов быстрой сортировки. Обсуждение. Реализация сортировочного алгоритма оправдана в случае, если приходится иметь дело с выборками большой длины, в то время как для сравнительно небольших выборок (порядка сотен отсчётов) можно ограничиться лобовым подходом. Скачать полную версию }}