Development of Algorithms for Ultrametric Tree Optimization and Hierarchical Clustering Optimization

点击翻译按钮获取中文摘要

2022年度は，研究計画調書に記載した3つの研究計画のうち，「（２）階層クラスタリング最適化問題に対する局所探索アルゴリズムの開発」に関連する研究を行った．階層クラスタリングとは, 与えられたデータ集合を，類似するデータから成るクラスターへの分割の階層構造を求める手続きである．階層構造はクラスター木（あるいは，デンドログラム)と呼ばれる2分木によって表現される．Dasgupta (2016) はクラスター木に対する目的関数を導入し，階層クラスタリングの問題を組合せ最適化問題として定式化した．Dasgupta はこの問題がNP困難であることを示すと同時に，この問題に対して再帰的最疎カットアルゴリズムと呼ばれるO(φ)-近似アルゴリズムを与えた．本研究では, Dasgupta (2016) の目的関数を最小化するクラスター木を見出す問題に対して, kSS操作 (k制限部分木交換操作)と呼ばれる2分木の変形操作に基づく局所探索アルゴリズムを提案し,このアルゴリズムの1反復あたりの計算時間がO(n min{2k+1,n}k)であることを示した. ここで, 1≦ k ≦ nである. さらに開発したアルゴリズムの実際的性能を数値実験によって評価した.Cohen-Addad et al. (2019) は，Dasgupta (2016) の目的関数を一般化して，許容的目的関数と呼ばれる階層クラスタリングに対する目的関数のクラスを定義した．許容的目的関数の定義は抽象的なものであり具体的な関数の形は与えられていなかったが，本研究では，3次以下の多項式を用いて定義される許容的目的関数に対する特徴付けを与えた．さらに, 再帰的最疎カットアルゴリズムはこのような許容的目的関数を最小化するクラスター木を求める問題に対するO(φ)-近似アルゴリズムであることを示した．