Geodesic
On a scheme for constructing algorithms for correcting a local perturbation in a finite semi-metric
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1315-1326 
I. A. Gromov. On a scheme for constructing algorithms for correcting a local perturbation in a finite semi-metric. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1315-1326. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a12/
@article{ZVMMF_2010_50_7_a12,
     author = {I. A. Gromov},
     title = {On a scheme for constructing algorithms for correcting a local perturbation in a finite semi-metric},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1315--1326},
     year = {2010},
     volume = {50},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a12/}
}
TY  - JOUR
AU  - I. A. Gromov
TI  - On a scheme for constructing algorithms for correcting a local perturbation in a finite semi-metric
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 1315
EP  - 1326
VL  - 50
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a12/
LA  - ru
ID  - ZVMMF_2010_50_7_a12
ER  - 
%0 Journal Article
%A I. A. Gromov
%T On a scheme for constructing algorithms for correcting a local perturbation in a finite semi-metric
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 1315-1326
%V 50
%N 7
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a12/
%G ru
%F ZVMMF_2010_50_7_a12

Voir la notice de l'article provenant de la source Math-Net.Ru

A three-step scheme for constructing algorithms for transforming metric information in data mining is proposed and investigated. The correction problem of a local perturbation of a semimetric on a finite set of objects is considered. In the framework of the proposed scheme, algorithms correcting the changes of the distance between a pair of objects by a given quantity that preserve the metric properties are examined. Sufficient conditions under which the correction of semimetrics using the proposed three-step scheme actually completes in two steps and in some special cases even after the first step are obtained. Semimetric similarity functionals are considered, and the correction algorithms are matched to those functionals.

[1] Aivazyan S. A., Bukhshtaber V. M., Enyukov I. S., Meshalkin L. D., Prikladnaya statistika: klassifikatsiya i snizhenie razmernosti, Finansy i statistika, M., 1989

[2] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968 | MR | Zbl

[3] Vasilev F. P., Chislennye metody resheniya ekstremalnykh zadach, Nauka, M., 1988 | MR

[4] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya (kombinatornaya teoriya mnogogrannikov), Nauka, M., 1981 | MR

[5] Mirkin B. G., Rodin S. N., Grafy i geny, Nauka, M., 1977 | MR

[6] Leontev V. K., “Ustoichivost v lineinykh diskretnykh zadachakh”, Probl. kibernetiki, 1979, no. 35, 169–184 | MR

[7] Yushmanov S. V., “Vosstanovlenie filogeneticheskogo dreva po podderevyam, porozhdennym chetverkami ego visyachikh vershin”, Matem. kibernetika i ee prilozh. k biologii, MGU, M., 1987

[8] Maisuradze A. I., “Ob optimalnykh razlozheniyakh konechnykh metricheskikh konfiguratsii v zadachakh raspoznavaniya obrazov”, Zh. vychisl. matem. i matem. fiz., 44:9 (2004), 1697–1707 | MR

[9] Maisuradze A. I., “Gomogennye i rangovye bazisy v prostranstvakh metricheskikh konfiguratsii”, Zh. vychisl. matem. i matem. fiz., 46:2 (2006), 344–360 | MR

[10] Gromov I. A., “Interaktivnye metody korrektsii polumetrik”, Sb. statei molodykh uchenykh f-ta VMiK MGU, 4, 2007, 27–40

[11] Deza M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001

[12] Zhuravlev Yu. I., “Korrektnye algebry nad mnozhestvami nekorrektnykh (evristicheskikh) algoritmov. I; II; III”, Kibernetika, 1977, no. 4, 5–17; No 6, 21–27; 1978, No 2, 35–43 | Zbl