Индекс Фаулкса – Маллоуса - Fowlkes–Mallows index

В Индекс Фаулкса – Маллоуса является внешняя оценка метод, который используется для определения сходства между двумя кластерами (кластеры, полученные после алгоритм кластеризации ), а также метрику для измерения матрицы путаницы.^[1] Этот мера сходства может быть между двумя иерархические кластеры или кластеризация и эталонная классификация. Более высокое значение индекса Фаулкса – Маллоуса указывает на большее сходство между кластерами и эталонными классификациями.

Предварительные мероприятия

В Индекс Фаулкса – Маллоуса, когда для оценки результатов используются результаты двух алгоритмов кластеризации, определяется как^[2]

${ displaystyle FM = { sqrt {PPV cdot TPR}} = { sqrt {{ frac {TP} {TP + FP}} cdot { frac {TP} {TP + FN}}}}}$

куда ${ displaystyle TP}$ это количество истинные положительные моменты, ${ displaystyle FP}$ это количество ложные срабатывания, и ${ displaystyle FN}$ это количество ложные отрицания. ${ displaystyle TPR}$ это истинно положительная ставка, также называемый чувствительность или же отзывать, и ${ displaystyle PPV}$ это положительный прогноз, также известный как точность.

Определение

Рассмотрим две иерархические кластеры ${ displaystyle n}$ помеченные объекты ${ displaystyle A_ {1}}$ и ${ displaystyle A_ {2}}$. Деревья ${ displaystyle A_ {1}}$ и ${ displaystyle A_ {2}}$ можно разрезать для производства ${ Displaystyle к = 2, ldots, п-1}$ кластеры для каждого дерева (либо выбирая кластеры на определенной высоте дерева, либо устанавливая различную степень иерархической кластеризации). Для каждого значения ${ displaystyle k}$, затем можно создать следующую таблицу

${ displaystyle M = [m_ {i, j}] qquad (i = 1, ldots, k { text {и}} j = 1, ldots, k)}$

куда ${ displaystyle m_ {i, j}}$ есть объекты, общие между ${ displaystyle i}$й кластер ${ displaystyle A_ {1}}$ и ${ displaystyle j}$й кластер ${ displaystyle A_ {2}}$. В Индекс Фаулкса – Маллоуса для конкретной стоимости ${ displaystyle k}$ тогда определяется как

${ displaystyle B_ {k} = { frac {T_ {k}} { sqrt {P_ {k} Q_ {k}}}}}$

куда

${ displaystyle T_ {k} = sum _ {i = 1} ^ {k} sum _ {j = 1} ^ {k} m_ {i, j} ^ {2} -n}$

${ displaystyle P_ {k} = sum _ {я = 1} ^ {k} ( sum _ {j = 1} ^ {k} m_ {i, j}) ^ {2} -n}$

${ displaystyle Q_ {k} = sum _ {j = 1} ^ {k} ( sum _ {i = 1} ^ {k} m_ {i, j}) ^ {2} -n}$

${ displaystyle B_ {k}}$ затем можно рассчитать для каждого значения ${ displaystyle k}$ и сходство между двумя кластерами можно показать, построив график ${ displaystyle B_ {k}}$ против ${ displaystyle k}$. Для каждого ${ displaystyle k}$ у нас есть ${ displaystyle 0 leq B_ {k} leq 1}$.

Индекс Фаулкса – Маллоуса также может быть определено на основе количества точек, общих или необычных в двух иерархических кластерах. Если мы определим

${ displaystyle TP}$ как количество пар точек, которые присутствуют в одном кластере в обоих ${ displaystyle A_ {1}}$ и ${ displaystyle A_ {2}}$.

${ displaystyle FP}$ как количество пар точек, которые присутствуют в одном кластере в ${ displaystyle A_ {1}}$ но не в ${ displaystyle A_ {2}}$.

${ displaystyle FN}$ как количество пар точек, которые присутствуют в одном кластере в ${ displaystyle A_ {2}}$ но не в ${ displaystyle A_ {1}}$.

${ displaystyle TN}$ как количество пар точек, которые находятся в разных кластерах в обоих ${ displaystyle A_ {1}}$ и ${ displaystyle A_ {2}}$.

Можно показать, что четыре отсчета обладают следующим свойством

${ Displaystyle TP + FP + FN + TN = n (n-1) / 2}$

и что Индекс Фаулкса – Маллоуса для двух кластеров можно определить как^[3]

${ displaystyle FM = { sqrt {PPV cdot TPR}} = { sqrt {{ frac {TP} {TP + FP}} cdot { frac {TP} {TP + FN}}}}}$

куда ${ displaystyle TP}$ это количество истинные положительные моменты, ${ displaystyle FP}$ это количество ложные срабатывания, и ${ displaystyle FN}$ это количество ложные отрицания.

${ displaystyle TPR}$ это истинно положительная ставка, также называемый чувствительность или же отзывать, и ${ displaystyle PPV}$ это положительный прогноз, также известный как точность.

Индекс Фаулкса – Маллоуса - это среднее геометрическое из точность и отзыв.^[4]

Обсуждение

Поскольку индекс прямо пропорционален количеству истинно положительных результатов, более высокий индекс означает большее сходство между двумя кластерами, используемыми для определения индекса. Один из основных способов проверить правильность этого индекса - сравнить две кластеризации, которые не связаны друг с другом. Фаулкс и Мэллоуз показали, что при использовании двух несвязанных кластеров значение этого индекса приближается к нулю по мере увеличения общего количества точек данных, выбранных для кластеризации; тогда как значение для Индекс Rand для одних и тех же данных быстро подходит ${ displaystyle 1}$^[1] что делает индекс Фаулкса – Маллоуса гораздо более точным представлением несвязанных данных. Этот индекс также хорошо работает, если к существующему набору данных добавляется шум и сравнивается их сходство. Фаулкс и Мэллоуз показали, что значение индекса уменьшается с увеличением составляющей шума. Индекс также показал сходство, даже когда зашумленный набор данных имел другое количество кластеров, чем кластеры исходного набора данных. Это делает его надежным инструментом для измерения сходства между двумя кластерами.

Рекомендации

Библиография

• Ramirez, E.H .; Brena, R .; Magatti, D .; Стелла, Ф. (2010). «Вероятностные метрики для мягкой кластеризации и валидации тематической модели». 2010 Международная конференция IEEE / WIC / ACM по веб-аналитике и технологиям интеллектуальных агентов. п. 406. Дои:10.1109 / WI-IAT.2010.148. ISBN  978-1-4244-8482-9.

Смотрите также

• Оценка F1
• Коэффициент корреляции Мэтьюза
• Матрица путаницы

внешняя ссылка

• Реализация индекса Фаулкса – Маллоуса в р.