Development of Algorithms for Ultrametric Tree Optimization and Hierarchical Clustering Optimization

超度量树优化和层次聚类优化算法的开发

• 批准号: 22K11921
• 负责人: 安藤 和敏
• 金额: $ 1.58万
• 依托单位: Shizuoka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11921/
• 关键词: 組合せ最適化; クラスタリング; 系統樹; デンドログラム; 超距離; アルゴリズム; クラスター解析; バイオインフォマティクス; 系統学; 組合せ最適化; クラスタリング; 系統樹; デンドログラム; 超距離; アルゴリズム; クラスター解析; バイオインフォマティクス; 系統学

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(φ)-近似アルゴリズムであることを示した．

在2022年，我们进行了与“（2）开发局部搜索算法有关层次聚类优化问题的研究”中列出的三个研究计划中列出的研究计划中的研究。层次聚类是找到将给定数据设置分成相似数据群的层次结构的过程。分层结构由称为群集树（或树状图）的二进制树表示。 Dasgupta（2016）引入了集群树的目标函数，并提出了分层聚类问题作为组合优化问题。达斯古普塔（Dasgupta）表明，这个问题很难NP，与此同时，他将此问题作为o（φ） - 附属算法称为递归稀疏切割算法。在这项研究中，对于找到最小化Dasgupta（2016）目标功能的簇树的问题，我们根据二进制树（K-Limimimimited子树交换操作）的转换操作提出了一种本地搜索算法，并显示了该算法的计算时间（n Min Min Min Min Min nim Min everation）。在这里，1≦K≦n。此外，我们通过数值实验评估了开发算法的实际性能。 Cohen-Addad等。 （2019）概括了Dasgupta（2016）的目标函数，并定义了层次聚类的目标函数类别，称为允许目标函数。可接受的目标函数的定义是抽象的，没有给出特定的函数形式，但是在这项研究中，我们提供了可接受的目标函数的表征，该目标函数使用以下的多项式定义了可接受的目标函数。此外，我们表明递归稀疏切割算法是找到一个最小化这种可接受的目标函数的群集树的问题（φ） - approximation算法。