Цель Дасгуптаса - Википедия - Dasguptas objective

При изучении иерархическая кластеризация, Цель Дасгупты является мерой качества кластеризации, определяемой из мера сходства на элементы, которые нужно объединить. Он назван в честь Санджоя Дасгупты, который сформулировал его в 2016 году.^[1] Его ключевое свойство состоит в том, что когда сходство исходит от ультраметрическое пространство, оптимальная кластеризация для этой меры качества следует основной структуре ультраметрического пространства. В этом смысле можно ожидать, что методы кластеризации, которые обеспечивают хорошую кластеризацию для этой цели, будут приближать наземная правда лежащая в основе данной меры подобия.^[2]

В формулировке Дасгупты сходство между элементами задается неориентированный граф ${ Displaystyle G = (V, E)}$, с неотрицательными действительными весами по краям. Большие веса указывают на элементы, которые следует считать более похожими друг на друга, в то время как малые веса или отсутствующие ребра указывают на пары элементов, которые не похожи. Иерархическая кластеризация может быть описана деревом (не обязательно двоичным деревом), листья которого являются элементами быть сгруппированным; тогда кластеры являются субъектами элементов, происходящих от каждого узла дерева, а размер ${ displaystyle | C |}$ любого кластера ${ displaystyle C}$ это его количество элементов. Для каждого края ${ displaystyle uv}$ входного графа, пусть ${ Displaystyle ш (уф)}$ обозначим вес ребра ${ displaystyle uv}$ и разреши ${ Displaystyle C (УФ)}$ обозначают наименьший кластер данной кластеризации, который содержит оба ${ displaystyle u}$ и ${ displaystyle v}$. Затем Дасгупта определяет стоимость кластеризации как^[1]

${ Displaystyle сумма _ {УФ в E} вес (уф) cdot | С (уф) |.}$

Оптимальная кластеризация для этой цели: NP-жесткий найти. Однако можно найти кластеризацию, которая приближается к минимальному значению цели в полиномиальное время с помощью делительного (нисходящего) алгоритма кластеризации, который многократно подразделяет элементы с помощью алгоритм аппроксимации для самая редкая проблема среза, задача поиска разбиения, которое минимизирует отношение общего веса обрезанных ребер к общему количеству пар вырезок.^[1]Эквивалентно, в целях приближения, можно минимизировать отношение общего веса обрезных кромок к количеству элементов на меньшей стороне разреза. Используя наиболее известное приближение для задачи с разреженными разрезами, коэффициент аппроксимации этого подхода ${ Displaystyle О ({ sqrt { log n}})}$.^[3]

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