論文の概要: Hierarchical Clustering: New Bounds and Objective
- arxiv url: http://arxiv.org/abs/2111.06863v1
- Date: Fri, 12 Nov 2021 18:32:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-15 14:56:47.432873
- Title: Hierarchical Clustering: New Bounds and Objective
- Title（参考訳）: 階層的クラスタリング: 新しい境界と目的
- Authors: Mirmahdi Rahgoshay and Mohammad R. Salavatipour
- Abstract要約: 異種性に基づくクラスタリングのための新しい目的関数を提案する。
任意のツリー$T$に対して、$H_i,j$を$i$と$j$の共通の祖先の数とする。
- 参考スコア（独自算出の注目度）: 1.1295032417617457
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hierarchical Clustering has been studied and used extensively as a method for
analysis of data. More recently, Dasgupta [2016] defined a precise objective
function. Given a set of $n$ data points with a weight function $w_{i,j}$ for
each two items $i$ and $j$ denoting their similarity/dis-similarity, the goal
is to build a recursive (tree like) partitioning of the data points (items)
into successively smaller clusters. He defined a cost function for a tree $T$
to be $Cost(T) = \sum_{i,j \in [n]} \big(w_{i,j} \times |T_{i,j}| \big)$ where
$T_{i,j}$ is the subtree rooted at the least common ancestor of $i$ and $j$ and
presented the first approximation algorithm for such clustering. Then Moseley
and Wang [2017] considered the dual of Dasgupta's objective function for
similarity-based weights and showed that both random partitioning and average
linkage have approximation ratio $1/3$ which has been improved in a series of
works to $0.585$ [Alon et al. 2020]. Later Cohen-Addad et al. [2019] considered
the same objective function as Dasgupta's but for dissimilarity-based metrics,
called $Rev(T)$. It is shown that both random partitioning and average linkage
have ratio $2/3$ which has been only slightly improved to $0.667078$ [Charikar
et al. SODA2020]. Our first main result is to consider $Rev(T)$ and present a
more delicate algorithm and careful analysis that achieves approximation
$0.71604$. We also introduce a new objective function for dissimilarity-based
clustering. For any tree $T$, let $H_{i,j}$ be the number of $i$ and $j$'s
common ancestors. Intuitively, items that are similar are expected to remain
within the same cluster as deep as possible. So, for dissimilarity-based
metrics, we suggest the cost of each tree $T$, which we want to minimize, to be
$Cost_H(T) = \sum_{i,j \in [n]} \big(w_{i,j} \times H_{i,j} \big)$. We present
a $1.3977$-approximation for this objective.
- Abstract（参考訳）: 階層クラスタリングは、データ分析の手法として広く研究され、利用されている。
最近では、dasgupta [2016] が正確な目的関数を定義した。
重み関数 $w_{i,j}$ のセットが 2 つの項目に対して$i$ と $j$ の類似性と相似性を示すものであるとすると、そのゴールはデータポイント (items) を連続的に小さなクラスタに分割する再帰的な(ツリーのような)パーティショニングを構築することである。
彼は、$t$ を $cost(t) = \sum_{i,j \in [n]} \big(w_{i,j} \times |t_{i,j}| \big)$ where $t_{i,j}$ は、$i$ と $j$ の最小共通祖先に根ざした部分木であり、そのようなクラスタリングに対する最初の近似アルゴリズムを提示した。
その後、Moseley と Wang [2017] は、類似度に基づく重み付けに対する Dasgupta の目的関数の双対性を考察し、ランダムパーティショニングと平均リンケージの両方が近似比 $1/3$ を持ち、一連の作品において0.585$ [Alon et al. 2020] に改善されていることを示した。
その後、Cohen-Addadら。
[2019] は Dasgupta と同じ目的関数であるが、$Rev(T)$ と呼ばれる相似性に基づくメトリクスに対して考慮した。
ランダムパーティショニングと平均連鎖はいずれも2/3$であり、わずか0.667078$ [charikar et al. soda2020] にわずかに改善されている。
最初の主な結果は$Rev(T)$を考え、より繊細なアルゴリズムと慎重に分析し、近似を0.71604$にすることです。
また,類似性に基づくクラスタリングのための新しい目的関数を提案する。
任意のツリー$t$ に対して、$h_{i,j}$ を $i$ と $j$ の共通の祖先の数とする。
直感的には、類似したアイテムは可能な限り同じクラスタ内に留まると予想される。
したがって、類似性に基づくメトリクスの場合、各ツリーのコストは$t$であり、最小化したい場合は$cost_h(t) = \sum_{i,j \in [n]} \big(w_{i,j} \times h_{i,j} \big)$である。
この目的のために1.3977$-approxationを提示する。
関連論文リスト
- A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。
これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文 参考訳（メタデータ） (2021-11-08T20:18:10Z) - Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。
私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
論文 参考訳（メタデータ） (2021-07-02T02:07:12Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。