Цель Дасгуптаса - Dasguptas objective - Wikipedia

При изучении иерархическая кластеризация, Цель Дасгупты является мерой качества кластеризации, определяемой из мера сходства на элементы, которые нужно объединить. Он назван в честь Санджоя Дасгупты, который сформулировал его в 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]

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

^ ^а ^б ^c Дасгупта, Санджой (2016), «Функция стоимости для иерархической кластеризации на основе сходства», Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений (STOC 2016), Нью-Йорк, Нью-Йорк: ACM, стр. 118–127, arXiv:1510.05043, Дои:10.1145/2897518.2897527, МИСТЕР 3536559
^ Коэн-Аддад, Винсент; Канаде, Варун; Малльманн-Тренн, Фредерик; Матье, Клэр (2018), «Иерархическая кластеризация: целевые функции и алгоритмы», Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2018), Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 378–397, arXiv:1704.02147, Дои:10.1137/1.9781611975031.26, МИСТЕР 3775814
^ Арора, Санджив; Рао, Сатиш; Вазирани, Умеш (2009), «Расширительные потоки, геометрические вложения и разбиение графов», Журнал ACM, 56 (2): A5: 1 – A5: 37, Дои:10.1145/1502793.1502794, МИСТЕР 2535878

[dasgupta-1] а ^б ^c Дасгупта, Санджой (2016), «Функция стоимости для иерархической кластеризации на основе сходства», Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений (STOC 2016), Нью-Йорк, Нью-Йорк: ACM, стр. 118–127, arXiv:1510.05043, Дои:10.1145/2897518.2897527, МИСТЕР 3536559

[ckmm-2] Коэн-Аддад, Винсент; Канаде, Варун; Малльманн-Тренн, Фредерик; Матье, Клэр (2018), «Иерархическая кластеризация: целевые функции и алгоритмы», Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2018), Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 378–397, arXiv:1704.02147, Дои:10.1137/1.9781611975031.26, МИСТЕР 3775814

[arv-3] Арора, Санджив; Рао, Сатиш; Вазирани, Умеш (2009), «Расширительные потоки, геометрические вложения и разбиение графов», Журнал ACM, 56 (2): A5: 1 – A5: 37, Дои:10.1145/1502793.1502794, МИСТЕР 2535878

[1]

[2]

[3]