DeepECT:Deep Embedded Cluster Tree
mnist、USPS、Fashion-MNIST、Reutersの4つの一般的に使用されるディープラーニングデータセットについて、提案した手法DeepECTを評価します。 表1は、実験で使用されたすべてのデータセットの統計を示しています。 MNISTとUSPSは、手書きの数字を含む両方の画像データセットです。 Fashion-MNISTデータセットには、衣類、靴、バッグの画像など、ファッション製品の画像が含まれています。 Reutersデータセットには、4つの上位カテゴリのニュース記事が含まれており、ここで説明したのと同じ表現を使用します。
実験セットアップ
私たちは、新しいクラスタリング層の評価に実験を焦点を当てています。 したがって、より精巧なオートエンコーダアーキテクチャを使用しないでください。 代わりに、すべての実験で使用されているのと同じ一般的なfully connected autoencoderレイアウトを使用します。 前に述べたように、すべてのメソッドは、より洗練されたドメイン固有のアーキテクチャから均等に得ら しかし、標準的なオートエンコーダーアーキテクチャは、ベースラインの競合他社と比較してDeepECTの実行可能性を示すのに十分です。 したがって，埋め込まれた空間をクラスタリングする目的でも使用されるのと同じ汎用オートエンコーダアーキテクチャを使用する。 このアーキテクチャのフィードフォワードエンコーダーの次元はdです-500–500–2000–10、デコーダネットワークはミラー化されたレイアウトを持っています。 Ｒｅｌｕ活性化と式からの平均二乗誤差再構成損失を使用した。 (1).
各データセットに対して十個の自動エンコーダーを事前訓練し、すべての実験と比較方法に対してこれらの同じ事前訓練されたネットワークを使用します。 これらの事前に学習された自動エンコーダーを使用することで、各メソッドが埋め込まれた空間に対して同じ開始条件を持ち、クラスタリング品質の変 事前トレーニングの設定は、で説明されているものと同様です。 私たちは、20％の破損率でautoencodersをノイズ除去するようにautoencodersを事前に訓練します。 まず、各レイヤーの後にドロップアウト（20％の割合）とレイヤーごとに20,000ステップを使用して、レイヤーごとの事前トレーニングを実行します。 次に、ドロップアウトせずに50,000ステップのネットワーク全体を微調整します。 入力破損は事前学習のためにのみ使用し、DeepECTとそのベースライン法の実際の最適化には使用しません。 すべての実験に対して、Adam(learning\({\hbox{rate}})を使用します}}=0.0001\), \(\beta_1=0.9,\beta_2=0.999\))最適化アルゴリズムと256サンプルのミニバッチサイズとして。 結合された最適化のために、収束を確実にするために追加の50,000回の反復を訓練します。
DeepECTでは、合成データを用いた最初の実験で、500個の最適化ステップごとにツリーを分割すると有望な結果が得られ、ステップサイズが拡張されてもパフォーマ このため、実世界のデータセットの実験に合わせて調整することなく、このスケジュールを維持します。 同じことが、宗派に記載されている剪定閾値にも当てはまります。 2.7. MNIST、Fashion-MNIST、およびUSPSの場合、20個の葉ノードが含まれるまで木を成長させます。 Reutersデータセットでは、地上真理クラスターが少ないため、リーフノードの最大数を十二に設定しました。 このようにして、実際のクラスター数の2倍と3倍があります。 これらの値は，選択したデータセットの本質的な構造を捉えるのに十分であると考えた。 階層ベースラインメソッドには同じ数のリーフノードを使用します。
プロットには、元のMNIST桁のサンプルとランダムに拡張されたバージョンが表示されます
画像データセットについては，拡張拡張Ｄｅｅｐｅｃｔ＋Ａｕｇをさらに実験した。 我々は、他の実験と同じ事前に訓練されたautoencodersから始めます。 さらに、DeepECTの非拡張バージョンを使用した実験では、上記と同じ最適化スケジュールに固執します。 各反復では、元のミニバッチとその拡張された対応物を使用して、Eqの損失関数を最適化します。 図9に示すように、式中の非増強損失の代わりに、式中の非増強損失を示す。 6. ランダムなアフィン変換をオンザフライで適用することにより，ミニバッチの各画像の拡張バージョンを作成した。 アフィン変換はランダムに回転し、\(\)度の範囲で画像をせん断します。 また、任意の方向に二つのピクセルまでランダムに数字を移動します。 図5は、MNISTのこの増強の例を示しています。
評価方法
系統樹純度(DP)と葉純度(LP)測定でDeepECTのクラスタ階層を評価します。 以下、その両方について説明する。 さらに，フラットベースライン法に対してクラスタツリーを評価した。 このために，よく知られた正規化相互情報（ＮＭＩ）とクラスタリング精度（ＡＣＣ）を用いた。 完全性のためにこれらを含め、フラットなクラスタ構造を期待し、データセット内の実際のクラスタ数を知っているシナリオでもDeepECTが競争力があるこ クラスタツリーからk個のクラスタパーティションを決定するには、最初の\(k-1\)分割の後に葉ノードであったk個のノードへの割り当てを使用します。
デンドログラム純度
デンドログラム純度測定は、平坦なグランド真理分配に対してクラスタツリーを評価するために使用することができます。 これは、同じクラスの2つのランダムにサンプリングされたデータポイントについて、最小共通祖先ノードによって与えられるサブツリーの期待される純度です。 それは1です。0は、基底真理値の1つのクラスに属するすべてのデータ点がある純粋な部分木に割り当てられ、ランダムに生成された木に対して0に近づく場合にのみ、0に近づく場合にのみ、0に近づく場合にのみ、0に近づく場合にのみ、0に近づくことができます。
明示的な式は次のように定義されています:
ここで、\(C_1,\dots,C_K\)は基底真理値クラスに対応するデータ点集合であり、\({\text{lca}}(x,y)\)はクラスタツリーのxとyの最小共通祖先ノードであり、\({\text{dan}}(z)\)はクラスタツリーのノードzに割り当てられたデータ点の集合であり、\({\text{pur}}(S,T)=|S\cap T|||S|\)は純度尺度であり、\({\text{pur}}(S,T)=|S\cap T|||S|\)は純度尺度であり、\({\text{pur}}(S,T)=|S\cap T|||S|\)は純度尺度である。 {\mathcal{P}}=\{（x、y）\mid\は\{C_1、\dots、C_K\}に存在します：X、y\In C\wedge x\ne y\}\）は、同じクラスに属するすべてのデータポイントペアのセットです。 系統樹純度は，クラスタツリー上のボトムアップ再帰で効率的かつ正確に計算できる。
葉の純度
系統樹の純度を使用するだけでなく、葉の純度（LP）と呼ばれる別の尺度を導入します。 これは、リーフノードに割り当てられたオブジェクトのマジョリティクラスに対するリーフノードw.r.t.の加重平均純度で、次の式で与えられます:
ここで、\({{\mathcal{L}}}_{{\mathcal{D}}}\)は、リーフノードに割り当てられたデータポイントを含むセットのセットです。
木の高さ純度測定の依存性
二つのクラスター木の樹形と葉の純度を比較することは、両方の木が同じ数の葉ノードを持っている場合にのみ直接可能で ただし、この要件を満たすために、サブツリーを常にリーフノードに折りたたむことができます。 したがって、DeepECTおよびBisecting—K—meansのトップダウンツリーで分割ノードと同じ数のマージステップが残るまで、サブツリーをリーフノードに圧縮することにより、ベースライ このプロセスにより、両方の方法が階層的評価尺度と同等であることが保証されます。
階層クラスタリングベースライン
階層特性を評価するためのベースラインとして、古典的な階層クラスタリングアルゴリズムbisecting-k-means(AE+Bisecting)、single-linkage(AE+Single)、complete-linkage(AE+Complete)を使用して埋め込みデータをクラスター化します。 これらの古典的アルゴリズムのどれも埋め込み空間を最適化することができないので，フラット埋め込みクラスタリングアルゴリズムＩＤＥＣを単一リンケージおよび完全リンケージと組み合わせるという簡単なアイデアも検討した。 IDECは、DECのクラスタリング層とオートエンコーダの再構成損失を組み合わせた方法です。 まず、クラスターの数を予想されるクラスター数よりも高い値に設定してIDECを実行します—この場合、DeepECTに使用するリーフノードの最大数に等しく設定します。 次に，これらのＩＤＥＣクラスタセンターを割り当てられたデータポイントの代表とみなし，クラスタセンター（ＩＤＥＣ＋ＳｉｎｇｌｅおよびＩＤＥＣ＋Ｃｏｍｐｌｅｔｅ）に対して単一リンケージと完全リンケージを行うことにより階層クラスタリング構造を回復しようとした。 同様の手法は，ＩＤＥＣの代わりにｋ-平均を持つ古典的な非埋め込み設定に対して提案されている。
フラットクラスタベースライン
フラットクラスタリング設定におけるDeepECTの性能を評価するためのベースラインとして、事前に訓練されたオートエンコーダ（AE+k-means）とIDECの埋め込みデータにk-meansを使用します。 より多くのドメイン固有で洗練されたオートエンコーダアーキテクチャの利点を無視すると、IDECは現在、最良の組み込みクラスタリング方法の一つです。 DeepECTとは対照的に、IDECとk-meansの最適化時にグランド真理値の実際のクラスタ数を設定する必要があります。 さらに、再構成損失に対するIDECのハイパーパラメータを0.1に設定します。
一般的な結果
DeepECTおよび階層ベースラインアルゴリズムの系統樹純度および葉純度測定を使用した階層評価の一般的な結果を表2に示します。 DeepECTは一貫して高品質のクラスターツリーを生成し、広いマージンでトップパフォーマンスのアルゴリズムです。 また、増強拡張により、MNISTとUSPSの結果が大幅に改善されることもわかります。 データセットの作成者は、各ファッションアイテムが正規化された表現を持つようにすべての画像を前処理することを選択したため、Fashion-MNISTデータセットの 古典的な方法の結果は、埋め込みを強化することができないことによって説明することができる。 DeepECTの葉の純度値は、この方法が均質な亜集団を作成できることを示しています。 DeepECTと階層IDEC+Center-linkageバリアントのリーフ純度値を他のベースラインのリーフ純度値と比較すると、クラスタリングとオートエンコーダの組み合わせ最適化が実際にローカル構造の均質性を向上させることがわかります。 しかし、IDEC+センターリンケージは、一貫した階層構造を抽出することもできません。
表3は、同じ事前学習されたオートエンコーダーに基づくフラットクラスタリング比較法の実験結果を示しています。 同じ事前に学習された自動エンコーダーを使用するので、それぞれのクラスタリング目的の影響を直接見ることができます。 IDECとDeepECTの両方が、埋め込みを最適化できないk-meansと比較して、複合最適化の恩恵を受けます。 表4は、それぞれの出版物から取られたより多くの重心ベースのクラスタリング方法の結果を示しています。 これらの方法についての詳細は、宗派で見つけることができます。 4. DeepECTもこれらの方法と比較してうまく機能していることがわかります。 しかし、オートエンコーダアーキテクチャがクラスタリング結果に大きく影響することもわかります。 たとえば、dbcはたたみ込みオートエンコーダの使用によってのみDECとは異なりますが、優れた結果が得られます。 ただし、選択したオートエンコーダアーキテクチャは、選択したクラスタリング層とは独立しています。
もちろん、フラットクラスタリングの目的とDeepECTのこの比較は、競合する方法が最適化時に真のクラスタ数を与えられるのに対し、DeepECTの場合は評価時にのみこの情報を使用するため、後者に対して不公平である。 それにもかかわらず、我々はDeepECTの通常のバージョンは、生のNMIとACC対策の面でこれらの方法に追いつくことができ、増強拡張DeepECT+Augは、データ内の既知の不変性を無視 これらの結果は，平坦なクラスタ構造を期待しているが，クラスタの数を知らず，クラスタツリーを再帰的に検査するシナリオにおいてもＤｅｅｐｔが競争力があることを示している。
詳細な評価
このセクションでは、上記のデータセットの結果DeepECT-treesを詳しく見ていきます。 USPSデータセットの調査結果はmnistの調査結果と同等であるため、両方とも手書きの数字を表しているため、簡潔にするためにこれらの結果を省略します。
MNIST Results
mnistデータセットの結果DeepECT-treesを詳しく見ると、手書きの数字内の異なる部分母集団のいくつかのエキサイティングな特性が示されています。 二つの例示的な例を図に示す。 6とDeepECTの通常および拡張拡張で見つけることができます。 数字7’の描写されたサブツリーのノード純度は98％であり、このクラスのほぼすべてのインスタンスを含みます。 これには2つのリーフノードが含まれています。 一方の葉ノードは、ヨーロッパで一般的に書かれているように小さなクロスバーでセブンを示し、もう一方の葉ノードは、より一般的に米国で書かれているように、この数字を示しています。 第二のサブツリーには、純度97％の数字”2″のほぼすべてのインスタンスが含まれています。 このサブツリーには、それぞれ固有の特性を持つ2つのリーフノードも含まれています。 最初のリーフノードには、よりカーリーで、下部に独特のループを持つインスタンスが含まれています。 表示されているサブツリーは、それぞれの桁の自然な階層を構築し、これらの知見が研究者にとって興味深いものであることを容易に想像することができます。 数字の他の形状に応じたグループは、ツリーの下部にも見つけることができ、例えば、数字の書かれたバージョン”4″と”9″は、多くの特性を共有しています。 したがって、これらはしばしば、これらの2つの桁のタイプのみを含むサブツリーとしてグループ化されています。
プロットは、DeepECTによって発見されたMNISTデータセットの興味深い部分集団から抽出された二つの部分木を示しています。 これらは、数字7（中央のクロスバーの有無にかかわらず）と2（カーリーと’合理化された’バージョン、文字’Z’のように見える）です。 表示されている数字はランダムにサンプリングされます
Reuters Results
Reutersデータセットには、協力/産業が44%、政府/社会が24%、市場が24%、経済が8%の四つの不均衡なトップカテゴリ（第一レベルのラベル）が含まれています。 このデータセットは、でより詳細に説明されています。 各ニュース記事のカテゴリは手作業で選択されているため、ある程度主観的です。 さらに、各トップカテゴリには、いくつかの追加の重複するサブカテゴリ（第二レベルのラベル）とサブサブカテゴリ（第三レベルのラベル）があり、96％以上の記事が二つ以上のサブカテゴリに属しています。 表5に、このデータセットのDeepECT結果を示します。 最初の2つの分割は、ノード3から始まる政府/社会サブツリーとノード5から始まる市場サブツリーのほとんどを他の2つのカテゴリから分離することが その後、政府/社会のサブツリーは、スポーツ、戦争と犯罪、国内および国際政治などのサブカテゴリのトピックにさらに差別化されます。 市場カテゴリは、それぞれのサブカテゴリのさまざまな側面にさらに差別化されます。 たとえば、最後の2行のリーフノードは、サブカテゴリ商品市場の異なるサブサブカテゴリに関係しています。 中央のリーフノードは、主に企業/産業と経済に関連しています。 それらは他の2つのサブツリーほど分離されていません。 しかし、そこでさえ、興味深い葉のノードを見つけることができます。 例えば、トップからの第七葉ノード（行）は、サブカテゴリのパフォーマンス（企業/産業の）と経済パフォーマンス（経済学の）でラベル付けされたニュース記事を共有
ファッション-MNISTの検索結果
この図は、Fashion-MNISTデータセットのクラスタツリーを示しています。 各リーフノードには、ランダムにサンプリングされたオブジェクトが割り当てられています。 ラベルは著者による解釈です。 色付きの領域は、データセットで見つかった3つのタイプのオブジェクトを表す3つの支配的なサブツリーを強調表示します：バッグ、服、靴
ファッション-MNISTは、服、靴、バッグ、すなわちTシャツ/トップ、ズボン、プルオーバー、ドレス、コート、サンダル、シャツ、スニーカー、バッグ、アンクルブーツの十種類のクラスが含まれています。 この方法の結果として得られるクラスタツリーを図に示す。 7. リーフノードは、ランダムにサンプリングされたオブジェクトに割り当てられています。 各ノードのラベルは、それぞれのノードに割り当てられたオブジェクトに基づいて解釈されます。 DeepECTがこのデータセット内に完全に自然に見える階層を見つけたことがわかります。 服、靴、バッグ：まず、画像は三つのカテゴリに分割されています。 私たちは、色付きの領域でこれらのサブツリーを強調しました。 各サブツリー内では、自然階層を見つけることができます。 袋の部門は目に見える革紐/ハンドルのない袋、小さいハンドルが付いている袋、および肩ひもが付いている袋を区別する。 地上の真実は、これらのタイプのバッグを区別せず、それらをすべて同じクラスに割り当てます。 服のカテゴリは、最初に上半身のズボンと服に分かれています。 その後、これらは再び短い袖と長い袖に分割されます。 ここでは、各アイテムが画像内で同じサイズで表示されるように正規化されているため、スリーブの長さは、それぞれの衣服の全長に対して見られなけ、ドレスやシャツは同じサイズのように見えます。 靴のカテゴリはまた、いくつかの興味深い特性を示しています。 まず、より小さくて大きな靴が区別されます。 小さい靴は、さらにサンダルとスニーカーに分かれています。 大きな靴は、フラットソール、小さなかかと、またはハイヒールのいずれかを持っています。 これらの機能に基づいて階層を構築することは、スニーカー、サンダル、アンクルブーツのground truthクラスに対して実行されます。 それにもかかわらず、それは—外観の観点から-靴のための有効で有益な階層です。
MNISTの予測タスクへの適用性
また、予測タスクでDeepECTを評価します。 これにより、オートエンコーダとクラスタリング最適化手順は上記のように保持されます。 上記の実験的評価とは対照的に、クラスタツリーの最適化時には、データセットMNISTの最初の50.000サンプル(トレーニングセット)のみを使用します。 最適化の後、以前には見えなかった残りの20.000データポイント（テストセット）のクラスターツリーのクラスタリング性能を評価します。
この実験では、テストセットに対して\(0.73\pm0.08\)と葉の純度\(0.85\pm0.06\)であり、これは表2の値と比較してわずかに低下しています。 それにもかかわらず、結果はクラスターツリーによって直接以前に目に見えないデータポイントの限定されたラベル予測を可能にするのに十分 しかし、ほとんどの場合、見つかったクラスター構造に基づいて分類器を訓練します。 埋め込み自体にも同じことが当てはまりますが、たとえば、教師付きオートエンコーダーの損失を利用して、見つかった埋め込みを強化することができます。
実験の概要
要約すると、4つの実世界のデータセットで示された実験は、DeepECTクラスターツリーの有用性と有効性を明確に示していると考えられます。 これらの種類の構造を見つけ、分析する詳細レベルを選択することは、DeepECTをデータ科学者にとって貴重な方法としています。
