メドイド

メドイドは、データセットまたはデータセット内のクラスターの代表的なオブジェクトであり、クラスター内のすべてのオブジェクトとの非類似度の合計が最小です。^{[1]メドイドは}平均や重心に概念が似ていますが、メドイドは常にデータセットのメンバーに制限されます。 メドイドは、グラフなど、平均または重心を定義できない場合にデータで最もよく使用されます。 また、画像、3D軌跡、 遺伝子発現など、重心がデータセットを代表しないコンテキストでも使用されます^{[2] (データがスパースであるがメドイドがスパースである必要がない場合)。 これらは、}ユークリッド距離の2乗以外の距離を使用して代表を見つけたい場合にも重要です(たとえば、映画の評価)。

一部のデータ セットでは、中央値のように、複数のメドイドが存在する場合があります。メドイドの一般的な応用は、k-メドイドクラスタリング アルゴリズムです。これは、 k-meansアルゴリズムに似ていますが、平均または重心が定義できない場合に機能します。このアルゴリズムは、基本的に次のように機能します。まず、メドイドのセットがランダムに選択されます。次に、他のポイントまでの距離が計算されます。3 番目に、データは、最も類似するメドイドに従ってクラスタ化されます。4 番目に、反復プロセスによってメドイド セットが最適化されます。

メドイドは、中央値、幾何中央値、または重心と同じではないことに注意してください。中央値は 1 次元データでのみ定義され、ノルムによって誘導されるメトリック(マンハッタン距離やユークリッド距離など) の他のポイントとの相違を最小限に抑えるだけです。幾何中央値は任意の次元で定義されますが、メドイドとは異なり、必ずしも元のデータセット内のポイントであるとは限りません。

距離関数dを持つ空間内の点の集合をとします。メドイドは次のように定義されます。 ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$${\textstyle n}$

${\displaystyle x_{\text{medoid}}=\arg \min _{y\in {\mathcal {X}}}\sum _{i=1}^{n}d(y,x_{i}).}$

メドイドは、距離関数が (2 乗) ユークリッド距離ではない場合、またはメトリックでさえない場合 (メドイドは三角不等式を必要としないため) に、クラスター平均の一般的な代替手段です。データ セットをクラスターに分割する場合、各クラスターのメドイドを各クラスターの代表として使用できます。

メドイドの考え方に基づくクラスタリング アルゴリズムには次のものがあります。

• Partitioning Around Medoids (PAM)、標準k-medoidsアルゴリズム
• 階層的クラスタリングでメドイドを使用する階層的クラスタリング(HACAM)

上記の定義から、集合のメドイドは、集合内の点間のすべてのペアワイズ距離を計算した後で計算できることは明らかです。これには 距離評価（）が必要です。最悪の場合、より少ない距離評価でメドイドを計算することはできません。^{[3] [4]}ただし、さまざまな統計モデルの下で、サブ2乗時間でメドイドを正確にまたは近似的に計算できるアプローチは多数あります。 ${\displaystyle {\mathcal {X}}}$${\textstyle O(n^{2})}$${\displaystyle n=|{\mathcal {X}}|}$

点が実数直線上にある場合、メドイドの計算は、ホーアのクイック選択アルゴリズム^[5]で実行できる中央値の計算に簡略化されます。ただし、高次元の実空間では、線形時間アルゴリズムは知られていません。RAND ^{[6] は、}他の点のランダムなサブセットをサンプリングすることにより、各点から他のすべての点までの平均距離を推定するアルゴリズムです。 高い確率でメドイドを の係数以内に近似するには、合計距離計算が必要です。ここで、はアンサンブル内の 2 点間の最大距離です。RANDは近似アルゴリズムであり、 事前にわから ない場合があることに注意してください。${\textstyle O(n)}$${\textstyle O\left({\frac {n\log n}{\epsilon ^{2}}}\right)}$${\textstyle (1+\epsilon \Delta )}$${\textstyle \Delta }$${\textstyle \Delta }$

RANDはTOPRANK ^[7]によって活用され 、 RANDによって得られた推定値を使用して候補点の小さなサブセットに焦点を当て、これらの点の平均距離を正確に評価し、それらの最小値を選択します。TOPRANKは、平均距離の分布仮定の下で、高い確率で正確なメドイドを見つけるために距離計算を必要とします 。 ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$

trimed ^[3]は、点の分布仮定の下で距離評価 を用いてメドイドを見つけるアルゴリズムを提示している 。このアルゴリズムは三角不等式を使用して探索空間を削減する。 ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$

Meddit ^[4]は、メドイド計算と多腕バンディットの結合を活用し、信頼限界上限型のアルゴリズムを使用して、ポイントに関する統計的仮定の下で距離評価を 行うアルゴリズムを取得します。${\textstyle O(n\log n)}$

相関逐次半減法^[8]も多腕バンディット技術を活用し、Medditを改良したものです。問題の相関構造を利用することで、このアルゴリズムは必要な距離計算回数と実時間の両方で劇的な改善（通常1～2桁程度）をもたらすことが証明されています。

RAND、TOPRANK、およびtrimedの実装については、こちらを参照してください。Medditの実装については 、こちらとこちらを参照してください。Correlated Sequential Halvingの実装については 、こちらを参照してください。

Medoidsは、さまざまなテキストおよびNLPタスクに適用して、分析の効率と精度を向上させることができます。^[9]類似性に基づいてテキストデータをクラスタリングすることにより、medoidsはデータセット内の代表的な例を識別するのに役立ち、データの理解と解釈を向上させます。

テキストクラスタリングは、類似したテキストや文書をその内容に基づいてグループ化するプロセスです。メドイドベースのクラスタリングアルゴリズムを使用すると、大量のテキストをクラスターに分割することができ、各クラスターはメドイド文書で表されます。この技術は、検索エンジン、ソーシャルメディア分析、推奨システムなどの大量の文書コレクションから情報を整理、要約、取得するのに役立ちます。^[10]

テキスト要約は、最も重要で関連性の高い情報を抽出することで、長いテキストの簡潔で一貫した要約を作成することを目的としています。メドイドベースのクラスタリングを使用すると、文書または文書グループ内の最も代表的な文を識別し、それらを組み合わせて要約を作成できます。このアプローチは、元のテキストから最も関連性の高い文を選択して要約を生成することを目的とする抽出要約タスクに特に役立ちます。^[11]

感情分析では、肯定的、否定的、中立的など、テキストに表現されている感情や感情を判断します。メドイドベースのクラスタリングは、類似した感情パターンに基づいてテキストデータをグループ化するために適用できます。各クラスターのメドイドを分析することで、研究者はクラスターの主な感情に関する洞察を得ることができ、意見マイニング、顧客フィードバック分析、ソーシャルメディアモニタリングなどのタスクに役立ちます。^[12]

トピックモデリングは、文書の集合に出現する抽象的なトピックを発見するために使用される手法です。メドイドベースのクラスタリングは、同様のテーマやトピックを持つ文書をグループ化するために適用できます。これらのクラスタのメドイドを分析することで、研究者はテキストコーパスの根底にあるトピックを理解し、文書の分類、傾向分析、コンテンツの推奨などのタスクを容易にすることができます。^[13]

メドイドベースのクラスタリングをテキストデータに適用する場合、文書を効果的に比較するために適切な類似度尺度を選択することが重要です。各手法には利点と限界があり、類似度尺度の選択は分析対象のテキストデータの特定の要件と特性に基づいて行う必要があります。^[14]以下は、メドイドベースのクラスタリングでテキストの類似性を測定するための一般的な手法です。

コサイン類似度は、2 つのテキストの類似度を比較するために広く使用されている尺度です。これは、高次元空間内の 2 つのドキュメント ベクトル間の角度のコサインを計算します。^[14]コサイン類似度の範囲は -1 から 1 で、値が 1 に近いほど類似度が高く、-1 に近いほど類似度が低いことを示します。原点からそれぞれの関心点まで伸びる 2 本の線を視覚化し、これらの線の間の角度を測定することで、関連する点間の類似度を判断できます。コサイン類似度はドキュメントの長さの影響を受けにくいため、長さではなくクラスターの内容を表すメドイドを生成するのに適している可能性があります。

ジャカード類似度はジャカード係数とも呼ばれ、2 つのセットの共通部分と結合部分の比率を比較することで、2 つのセットの類似度を測定します。テキスト データのコンテキストでは、各ドキュメントは単語のセットとして表され、ジャカード類似度は 2 つのセット間の共通単語に基づいて計算されます。ジャカード類似度は 0 から 1 の範囲で、値が高いほどドキュメント間の類似度が高いことを示します。^{[引用が必要]}

ユークリッド距離は、多次元空間内の2点間の相違点を測定するために使用される標準的な距離測定基準です。テキストデータのコンテキストでは、文書はTFベクトルなどの高次元ベクトルとして表されることが多く、ユークリッド距離を使用してそれらの間の相違点を測定できます。ユークリッド距離が低いほど、文書間の類似度が高いことを示します。^[14]ユークリッド距離を使用すると、文書の長さをよりよく表すメドイドが得られる場合があります。

編集距離はレーベンシュタイン距離とも呼ばれ、ある文字列を別の文字列に変換するために必要な操作（挿入、削除、または置換）の最小数を計算することで、2つの文字列の類似性を測定します。テキストデータのコンテキストでは、編集距離は短いテキスト文書または個々の単語間の類似性を比較するために使用できます。編集距離が低いほど、文字列間の類似度が高いことを示します。^[15]

Medoidsは、BERT、GPT、RoBERTaなどの大規模言語モデル（LLM）によって生成されたベクトル空間表現を分析および理解するために使用できます。これらのモデルによって生成された単語、フレーズ、または文の埋め込みにmedoidベースのクラスタリングを適用することで、研究者はLLMによってキャプチャされた意味関係を調査できます。このアプローチは、意味的に類似したエンティティのクラスターを識別するのに役立ち、これらのモデルによって生成された高次元の埋め込み空間の構造と構成に関する洞察を提供します。^[16]

能動学習では、モデルのパフォーマンスを最大化するデータポイントをトレーニングプールから選択します。メドイドは、LLM によるデータ選択と能動学習において重要な役割を果たします。メドイドベースのクラスタリングは、大規模なテキストデータセットから代表的で多様なサンプルを識別するために使用でき、その後、LLM をより効率的に微調整したり、より優れたトレーニングセットを作成したりするために使用できます。メドイドをトレーニング例として選択することで、研究者はよりバランスのとれた有益なトレーニングセットを得ることができ、微調整されたモデルの一般化と堅牢性が向上する可能性があります。^[17]

LLMのコンテキストでメドイドを適用すると、モデルの解釈可能性の向上に貢献できます。LLMによって生成された埋め込みをクラスタリングし、各クラスタの代表としてメドイドを選択することで、研究者はモデルの動作のより解釈しやすい要約を提供できます。^[18]このアプローチは、モデルの意思決定プロセスを理解し、潜在的なバイアスを特定し、LLMによって生成された埋め込みの根本的な構造を明らかにするのに役立ちます。LLMの解釈可能性と安全性に関する議論が活発化しているため、メドイドの使用はこの目標を達成するための貴重なツールとなる可能性があります。

汎用性の高いクラスタリング手法であるメドイドは、生物学や医学から広告やマーケティング、ソーシャル ネットワークまで、さまざまな分野のさまざまな現実の問題に適用できます。複雑なデータセットを非常に複雑に処理できるため、現代のデータ分析において強力なツールとなっています。

遺伝子発現解析では、^[19]研究者はマイクロアレイやRNAシーケンシングなどの先進技術を利用して、生物学的サンプル中の多数の遺伝子の発現レベルを測定します。その結果、複雑で解析が困難な多次元データが得られます。メドイドは、主に発現プロファイルに基づいて遺伝子をクラスタリングする潜在的なソリューションであり、研究者は共発現する遺伝子グループを発見することができ、生物学的プロセスや疾患の分子メカニズムに関する貴重な洞察を得ることができます。

ソーシャルネットワークの評価では、^[20]メドイドはソーシャルネットワークの中心的または影響力のあるノードを認識するための優れたツールになり得ます。研究者は接続スタイルに基づいてノードをクラスタ化し、ネットワークの機能と構造に大きな影響を与える可能性が最も高いノードを特定できます。ソーシャルネットワーク分析でメドイドを利用するための一般的なアプローチの1つは、ノードのペア間の距離または類似性メトリックをそのプロパティに基づいて計算することです。

メドイドは市場セグメンテーションにも利用することができます。^[21]メドイドは、主に購買行動、人口統計学的特性、およびその他のさまざまな属性に基づいて顧客をグループ化する分析手順です。メドイドを使用して顧客をセグメントにクラスタリングすると、企業は各顧客グループのニーズに合わせてマーケティング戦略を調整できます。メドイドは各クラスター内の代表要因として機能し、そのグループの顧客の主な特性をカプセル化します。

グループ内二乗誤差合計 (WGSS) は、市場セグメンテーションで使用される式で、クラスター内の二乗誤差の集中度を定量化することを目的としています。グループ内の誤差を二乗して結果を集計することで、グループ内の誤差の分布を把握しようとします。WGSS メトリックは、クラスター内のサンプルの凝集性を定量化し、WGSS 値が低いほどクラスターが密集していることを示し、それに応じて優れたクラスタリング効果を示します。WGSS の式は次のとおりです。

$${\displaystyle {\text{WGSS}}={\frac {1}{2}}\left[(m_{1}-1){\overline {d_{1}^{2}}}+\cdots +(m_{k}-1){\overline {d_{k}^{2}}}\right]}$$

ここで、はk番目のクラスター内のサンプルの平均距離であり、はk番目のクラスター内のサンプル数です。 ${\displaystyle {\overline {d_{1}^{2}}}}$${\displaystyle m_{k}}$

メドイドは異常の特定にも役立ち、効率的な方法の 1 つはクラスターベースの異常検出です。メドイドは、残りのデータから大きく逸脱するデータ ポイントのクラスターを発見するために使用できます。メドイドを使用してデータをグループにクラスタ化し、各クラスターの特性をデータと比較することで、研究者は異常なクラスターを明確に検出できます。^{[引用が必要]}

メドイドベースクラスタリングの視覚化は、メドイドベースクラスタリングの仕組みを理解するのに役立ちます。研究では、視覚情報があると学習効果が高いことが示されています。^[22]メドイドベースクラスタリングでは、メドイドはクラスターの中心です。これは、中心が実際のデータポイントではなく、データポイント間にある可能性があるk-meansクラスタリングとは異なります。メドイドを使用して、クラスター内の他のすべてのオブジェクトとの平均非類似度が最小の要素を見つけることで得られるデータの「クラスター」をグループ化します。^[23]　使用されている視覚化の例ではk-メドイドクラスタリングを使用していますが、平均非類似度を使用しているデータセットの平均と入れ替えることで、k-meansクラスタリングにも視覚化を適用できます。

メドイドベースのクラスタリングには距離行列が必要です。これは、Jaccard 非類似度 (1 - Jaccard 指数) を使用して生成されます。この距離行列は、1 次元グラフ上の 2 点間の距離を計算するために使用されます。^{[引用が必要]}上記の画像は、Jaccard 非類似度グラフの例を示しています。

ステップ1

Medoid ベースのクラスタリングは、データセット内のクラスターを見つけるために使用されます。medoid ベースのクラスタリングのプロセスには、検出する必要のあるクラスターを含む初期の 1 次元データセットが使用されます。下の画像では、データセット内にさまざまな x 位置にある 12 個の異なるオブジェクトがあります。

ステップ2

K 個のランダム ポイントが初期の中心として選択されます。K に選択された値は K 値と呼ばれます。下の画像では、K 値として 3 が選択されています。最適な K 値を見つけるプロセスについては、手順 7 で説明します。

ステップ3

中心以外の各オブジェクトは、最も近い中心に割り当てられます。これは、距離マトリックスを使用して行われます。相違度が低いほど、ポイントは近くなります。下の画像では、クラスター 1 に 5 つのオブジェクト、クラスター 2 に 3 つのオブジェクト、クラスター 3 に 4 つのオブジェクトがあります。

ステップ4

各クラスターの新しい中心は、クラスター内の他のすべてのオブジェクトとの平均相違が最小であるオブジェクトを見つけることによって見つけられます。このステップで選択された中心は、メドイドと呼ばれます。下の画像は、メドイドの選択結果を示しています。

ステップ5

以下の画像のように、中心が動かなくなるまで手順 3 ～ 4 を繰り返します。

• 手順3～4を繰り返す（左から右へ）
• 
  2番目のクラスター。
• 
  メドイドの選択。
• 
  3番目のクラスター。
• 
  最終的なメドイドの選択。

ステップ6

最終的なクラスターは、中心がステップ間で移動しなくなったときに得られます。下の画像は、最終的なクラスターがどのように見えるかを示しています。

ステップ7

各クラスター内の変動を合計して、中心の精度を確認します。異なる K 値でこのテストを実行すると、変動グラフの「エルボ」を取得できます。この部分でグラフの変動は平準化されます。グラフの「エルボ」がデータセットの最適な K 値です。

k-メドイドクラスタリングやその他のメドイドベースのクラスタリングアルゴリズムに共通する問題は、「次元の呪い」です。これは、データポイントに含まれる次元や特徴が多すぎるというものです。データに次元が追加されると、それらの間の距離は疎になり、^[24]ユークリッド距離だけでクラスタリングを特徴付けることが難しくなります。その結果、距離ベースの類似性尺度は定数に収束し^[25]、ポイント間の距離の特徴付けが、意味のある方法でデータセットを反映しない可能性があります。

次元の呪いの影響を軽減する方法の1つは、スペクトルクラスタリングを使用することです。スペクトルクラスタリングは、主成分分析を使用してデータの次元を削減し、データポイントをより低次元のサブスペースに投影してから、選択したクラスタリングアルゴリズムを前と同じように実行することで、より適切な分析を実現します。ただし、注意すべき点の1つは、次元削減を行うと情報が失われるため、^[26]どの程度の削減を行うとデータが失われるかを事前にクラスタリングと比較検討する必要があります。

ただし、高次元性は距離メトリックにのみ影響するわけではなく、時間計算量も特徴の数に応じて増加します。k-medoids は、medoids の初期選択に敏感です。medoids は通常ランダムに選択されるためです。このような medoids の初期化方法によっては、k-medoids は異なる局所最適値に収束し、異なるクラスターと品質尺度が生じる可能性があります。^[27]つまり、k-medoids は異なる初期化で複数回実行する必要がある可能性があり、実行時間が大幅に長くなります。これを相殺する 1 つの方法は、k-medoids++ を使用することです。^{[28]これは、k-means の代替であり、k} -means++に似ています。k -means++は、確率分布に基づいて、いわば「情報に基づいたランダム性」または知識に基づいた推測として、最初に初期 medoids を選択します。このような理由でこのような medoids を選択すると、実行時間が改善され、クラスタリングのパフォーマンスが向上します。k-medoids++ アルゴリズムは次のように説明されます。^[29]

1. 初期メドイドは、すべての空間点の中からランダムに選択されます。
2. 各空間点 𝑝 について、 𝑝 と最も近いメドイド間の距離（D(𝑝) と呼ばれる）を計算し、 𝑆 までの距離をすべて合計します。
3. 次のメドイドは、加重確率分布を使用して決定されます。具体的には、ゼロと合計距離 𝑆 の間の乱数 𝑅 が選択され、対応する空間点が次のメドイドになります。
4. ステップ（2）とステップ（3）は、𝑘個のmedoidが選択されるまで繰り返されます。

メドイドの適切な最初の選択ができたので、k-メドイドの通常のバリエーションを実行できます。

• #Visualization_of_the_medoid-based_clustering_process セクションで視覚的な参照として使用される StatQuest k-means ビデオ