Кіріспе

Жинақтар арасындағы ұқсастық және әртүрліліктің өлшемі

Жакард индексі, сондай-ақ Жакардтың ұқсастық коэффициенті деп аталады, бұл үлгі жиынтықтарының ұқсастығы мен әртүрлілігін бағалауға қолданылатын статистикалық шама. Ол 1884 жылы Гроув Карл Гилберт тарапынан тексеру коэффициенті (v) ретінде әзірленген, ал қазір метеорологияда Критикалық табыстылық индексі деп жиі аталады. Кейін Пол Жаккард оны тәуелсіз түрде әзірледі, бастапқыда француз тілінде "coefficient de communauté" деп атады, және Т. Танимото да оны тәуелсіз түрде қайта жасады. Жакард ұқсастығы қаптарға, яғни көп жиынтықтарға да қолданылады. Бұл ұқсас формулаға ие, бірақ қолданылатын белгілер қаптың қиылысын және қаптың қосындысын (біріктірілісі емес) көрсетеді. Ең жоғары мәні 1/2-ге тең. Үлгі жиынтықтарының ұқсамастығын өлшейтін Жакард қашықтығы Жакард коэффициентіне толықтырады және Жакард коэффициентін 1-ден азайту арқылы немесе, баламалы түрде, екі жиынтықтың біріктірілісі мен қиылысының өлшемдерінің айырмасын біріктірілістің өлшеміне бөлу арқылы есептеледі:

Жакард қашықтығының тағы бір түсіндірілуі – симметриялық айырмашылықтың өлшемінің біріктіріліске қатынасы. Жакард қашықтығы жиі n үлгі жиынтығын кластерлеу және көп өлшемді масштабтау үшін n × n матрицасын есептеу үшін қолданылады. Бұл қашықтық барлық шекті жиынтықтар жиынындағы метрика болып табылады. Жакард қашықтығының өлшемдер үшін, соның ішінде ықтималдық өлшемдері үшін де нұсқасы бар. Егер өлшенетін кеңістіктегі өлшем болса, онда Жакард коэффициенті мен Жакард қашықтығы былай анықталады:

және

Егер немесе болса, сақтану керек, өйткені бұл формулалар осы жағдайларда дұрыс анықталмайды. MinHash – минималды дана тәуелсіз пермутациялардың жергілікті сезімтал хэштеу схемасы, жиынтықтар жұбының Жакард ұқсастық коэффициентінің дәл бағасын тиімді есептеу үшін қолданылуы мүмкін, мұнда әрбір жиынтық хэш функциясының ең төменгі мәндерінен алынған тұрақты өлшемді қолтаңбамен бейнеленеді.

Мүмкіндіктер индексінің оптималдық жакардтық

Кездейсоқ айнымалыларды бір-бірімен мүмкіндігінше көп соқтығысуы үшін құру мәселесін қарастырайық. Егер және екі таралымды жеке қарасақ, ең жоғарғы мәнге қол жеткіземіз, ол – Толық Ауытқу қашықтығы арқылы беріледі. Дегенмен, егер біз тек осы жұптың соқтығысу ықтималдығын максималдауды ғана емес, кез келген кездейсоқ жұптың соқтығысу ықтималдығын максималдауды қаласақ не болады? Әр таралым үшін бір-бірден шексіз көп кездейсоқ айнымалыларды құрастыруға болады және барлық жұптар үшін максималдық мәнге қол жеткізуге тырысу керек. Төменде сипатталғандай, Ықтималдық Жеккард Индексі осы кездейсоқ айнымалыларды сәйкестендірудің оңтайлы жолы болып табылады. Кез келген іріктеу әдісі және дискретті таралымдар үшін, егер онда кейбір жерде және , немесе IBM техникалық есебін бастапқы сілтеме ретінде келтіріңіз. Есепті бірнеше кітапханадан алуға болады. 1960 жылдың қазанында жарияланған «Өсімдіктерді жіктеуге арналған компьютерлік бағдарламада» ұқсастық коэффициенті және одан туындаған қашықтық функциясы негізінде жіктеу әдісі берілген. Бұл «Танимото ұқсастығы» және «Танимото қашықтығы» терминдерінің мағынасын анықтайтын ең авторитетті дереккөз болып көрінеді. Ұқсастық коэффициенті Жеккард ұқсастығына тең, бірақ қашықтық функциясы Жеккард қашықтығынан өзгеше.