論文の概要、ライセンス

# (参考訳) 最寄りプロトタイプ分類のための非計量空間におけるクラスター代表の選択 [全文訳有]

Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype Classification ( http://arxiv.org/abs/2107.01345v1 )

ライセンス: CC BY 4.0
Jaroslav Hlav\'a\v{c}, Martin Kopp, Jan Kohout(参考訳) 最も近いプロトタイプ分類は、特に大規模なデータセットを考慮に入れた場合、$k$-NN法の計算集約的な置き換えである。 計量空間では、セントロイドはクラスター全体を表すプロトタイプとしてしばしば用いられる。 非計量空間におけるクラスタプロトタイプの選択は、セントロイドの計算が直接適用されないため、より難しい。 本稿では,オブジェクトの小さいが代表的なサブセットをクラスタのプロトタイプとして選択する新しい手法であるCRSを提案する。 nn-descentアルゴリズムによって作成された各クラスタの類似性グラフ表現を利用して、メモリと計算効率のよい代表者選択を可能にする。 CRSはグラフベースのアプローチのため、任意の計量空間や非計量空間で使用することができる。 実験で示すように,本手法は異なる領域の複数のデータセット上で,技術技術の現状よりも優れている。

The nearest prototype classification is a less computationally intensive replacement for the $k$-NN method, especially when large datasets are considered. In metric spaces, centroids are often used as prototypes to represent whole clusters. The selection of cluster prototypes in non-metric spaces is more challenging as the idea of computing centroids is not directly applicable. In this paper, we present CRS, a novel method for selecting a small yet representative subset of objects as a cluster prototype. Memory and computationally efficient selection of representatives is enabled by leveraging the similarity graph representation of each cluster created by the NN-Descent algorithm. CRS can be used in an arbitrary metric or non-metric space because of the graph-based approach, which requires only a pairwise similarity measure. As we demonstrate in the experimental evaluation, our method outperforms the state of the art techniques on multiple datasets from different domains.
公開日: Sat, 3 Jul 2021 04:51:07 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 l u J 1 2 0 2 l u J 0.85
3 ] G L . 3 ] G L。 0.81
s c [ 1 v 5 4 3 1 0 sc [ 1 v 5 4 3 1 0 0.68
. 7 0 1 2 : v i X r a . 7 0 1 2 : v i X r a 0.85
Cluster Representatives Selection in Non-Metric 非メトリックにおけるクラスター代表の選択 0.56
Spaces for Nearest Prototype Classification 最も近いプロトタイプ分類のための空間 0.65
Jaroslav Hlaváč1,2, Martin Kopp1,2, and Jan Kohout1,3 Jaroslav Hlaváč1,2, Martin Kopp1,2, Jan Kohout1,3 0.65
1 Cognitive Intelligence, Cisco Systems, Prague, Czech Republic. チェコのプラハにあるcisco systems.1cognitive intelligence, cisco systems。 0.68
2 Faculty of Information Technology, Czech Technical University in Prague, Czech チェコ・プラハのチェコ工科大学情報技術学部2 0.54
3 Faculty of Electrical Engineering, Czech Technical University in Prague, Czech チェコ・プラハのチェコ工科大学電気工学科 0.41
Republic. Republic. Abstract. 共和国。 共和国。 抽象。 0.75
The nearest prototype classification is a less computationally intensive replacement for the k-NN method, especially when large datasets are considered. 最も近いプロトタイプ分類は、特に大規模なデータセットが考慮されている場合、k-NN法の計算量が少ない置換である。 0.66
In metric spaces, centroids are often used as prototypes to represent whole clusters. 計量空間では、セントロイドはクラスター全体を表すプロトタイプとしてしばしば用いられる。 0.68
The selection of cluster prototypes in non-metric spaces is more challenging as the idea of computing centroids is not directly applicable. 非計量空間におけるクラスタプロトタイプの選択は、セントロイドの計算が直接適用されないため、より難しい。 0.72
In this paper, we present CRS, a novel method for selecting a small yet representative subset of objects as a cluster prototype. 本稿では,オブジェクトの小さいが代表的なサブセットをクラスタのプロトタイプとして選択する新しい手法であるCRSを提案する。 0.86
Memory and computationally efficient selection of representatives is enabled by leveraging the similarity graph representation of each cluster created by the NN-Descent algorithm. nn-descentアルゴリズムによって作成された各クラスタの類似性グラフ表現を利用して、メモリと計算効率のよい代表者選択を可能にする。
訳抜け防止モード: 記憶と計算効率の良い代表者の選定は nn - descentアルゴリズムによって作成された各クラスタの類似グラフ表現を活用する。
0.75
CRS can be used in an arbitrary metric or non-metric space because of the graph-based approach, which requires only a pairwise similarity measure. CRSはグラフベースのアプローチのため、任意の計量空間や非計量空間で使用することができる。
訳抜け防止モード: CRSはグラフベースのアプローチのため、任意の計量空間や非計量空間で使用することができる。 ペアワイズ類似度測定しか必要ありません
0.66
As we demonstrate in the experimental evaluation, our method outperforms the state-of-the-art techniques on multiple datasets from different domains. 実験で示すように,本手法は異なる領域の複数のデータセットにおける最先端技術よりも優れる。 0.71
Keywords: Cluster Representation · Nearest Prototype Classification · Prototype Selection キーワード:クラスタ表現 · 最も近いプロトタイプ分類 · プロトタイプ選択 0.84
1 Introduction The k-NN classifiers are often used in many application domains due to their simplicity and ability to trace the classification decision to a specific set of samples. 1 はじめに k-nn分類器は、その単純さと分類決定を特定のサンプル集合にトレースする能力のため、多くのアプリケーションドメインでしばしば使用される。 0.73
However, their adoption is limited by high computational complexity. しかし、それらの採用は高い計算複雑性によって制限される。 0.55
Because contemporary datasets are often huge, containing hundreds of thousands or even millions of samples, computing similarity between the classified sample and the entire dataset may be computationally intractable. 現代のデータセットはしばしば巨大で、数十万から数百万のサンプルを含んでいるため、分類されたサンプルとデータセット全体の類似性を計算することは、計算に難航する可能性がある。 0.61
In order to decrease computational and memory requirements, the nearest prototype classification (NPC) method is commonly used, c.f. 計算とメモリの要求を減らすために、最も近いプロトタイプ分類 (npc) 法が一般的に用いられる。 0.74
[1,2,3]. In NPC, each class is divided into one or more clusters, and each cluster is represented by its prototype. [1,2,3]. npcでは、各クラスは1つ以上のクラスタに分割され、各クラスタはプロトタイプで表現される。 0.77
The classified sample is then compared just to the prototypes instead of calculating similarity to the entire dataset. 分類されたサンプルは、データセット全体と類似性を計算する代わりに、プロトタイプのみと比較される。 0.74
英語(論文から抽出)日本語訳スコア
Therefore, the goal of prototype selection is to find a memory-efficient representation of clusters such that classification accuracy is preserved while the number of comparisons is significantly reduced. したがって,プロトタイプ選択の目標は,比較回数を大幅に削減しつつ,分類精度が保持されるようなクラスタのメモリ効率の高い表現を見つけることである。 0.79
However, in many application domains, objects might exist in a non-metric space where only a pairwise similarity is defined, e g , bioinformatics [4], biometric identification [5], computer networks [6] or pattern recognition [7]. しかし、多くのアプリケーションドメインにおいて、オブジェクトは、例えばバイオインフォマティクス[4]、バイオメトリック識別[5]、コンピュータネットワーク[6]、パターン認識[7]など、ペアの類似性しか定義されていない非メトリック空間に存在する可能性がある。 0.77
In such application domains, standard representations such as centroids may not be easily determined, or their interpretation does not make much sense. そのようなアプリケーション領域では、センタロイドのような標準表現は簡単には決定できないし、それらの解釈は意味をなさない。
訳抜け防止モード: このようなアプリケーションドメインでは セントロイドのような標準表現は容易には決定できない。 解釈はあまり意味がありません
0.66
For these scenarios, only a few methods have been developed, and to best of our knowledge the only general (not domain-specific) approach is based on the selection of small subsets of objects to represent the remaining cluster members. これらのシナリオでは、少数のメソッドしか開発されておらず、私たちの知識を最大限に活用するために、唯一の一般的な(ドメイン固有ではない)アプローチは、残りのクラスタメンバーを表現するためのオブジェクトの小さなサブセットの選択に基づいている。 0.62
These object, called representatives, are then used as a prototype. これらのオブジェクトはrepresentationと呼ばれ、プロトタイプとして使用される。 0.66
While several methods capable of solving representatives selection on nonmetric spaces exist (i.e. 非計量空間上の代表の選択を解くことのできるいくつかの方法が存在する(すなわち)。 0.52
DS3 [8], δ-medoids [9]), there has not been much research activity in this direction. DS3[8],δ-メドイド[9])は、この方向にはあまり研究が行われていない。 0.75
Our focus on non-metric spaces comes from the problem of behavioural clustering of network hosts [6]. 非計量空間にフォーカスするのは,ネットワークホストの動作クラスタリングの問題 [6] から来ている。 0.72
Nevertheless, the problem of selecting a minimal number of representative samples is of more general interest. それにもかかわらず、最小のサンプル数を選択する問題はより一般的な関心事である。 0.68
Therefore, we present a novel method to solve the problem of Cluster Representatives Selection (CRS). そこで本研究では,クラスタ代表選択(CRS)の問題を解決する新しい手法を提案する。 0.81
CRS is a general method capable of selecting small representative subset of objects from a cluster as its prototype. CRSは、クラスタからオブジェクトの小さな代表サブセットをプロトタイプとして選択できる一般的な方法である。 0.80
Its core idea is fast construction of an approximate reverse k-NN graph and then solving minimal vertex cover problem on that graph. その中心となる考え方は、近似逆k-NNグラフを高速に構築し、そのグラフ上の最小頂点被覆問題を解くことである。 0.67
Only a pairwise similarity is required to build the reverse k-NN graph, therefore application of CRS is not limited to metric spaces. 逆 k-NN グラフを構築するためには、ペアの類似性しか必要としないため、CRS の適用は計量空間に限らない。 0.68
To show that CRS is general and domain-independent, we present an experimental evaluation on datasets from image recognition, document classification and network host classification, with appealing results when compared to the current state-of-the-art. crsが一般的かつドメインに依存しないことを示すために,画像認識,文書分類,ネットワークホスト分類から得られたデータセットについて,現状と比較して魅力的な評価結果を示す。 0.69
The paper is organized as follows. 論文は以下の通り整理される。 0.65
The related work is briefly reviewed in the next section. 関連した作業は、次の節で簡単にレビューします。 0.48
Section 3 formalises the representative selection as an optimization problem. 第3節は最適化問題として代表選択を定式化する。 0.61
The proposed CRS method is described in detail in Section 4. 提案するcrs法は,第4節で詳述する。 0.61
The experimental evaluation is summarized in Section 5 followed by the conclusion. 実験評価は第5節で要約され、結論が導かれる。 0.72
2 Related Work During the past years, significant effort has been made to represent clusters in the most condensed way. 2 関連作業 過去数年間、最も凝縮した方法でクラスターを表現するために多大な努力がなされてきた。 0.67
The approaches could be categorized into two main groups. アプローチは2つの主要なグループに分類できる。 0.84
The first group gathers all prototype generation methods [10], which create artificial samples to represent original clusters, e g [11,12]. 最初のグループはすべてのプロトタイプ生成メソッド[10]を収集し、元のクラスタを表す人工的なサンプルを生成する。 0.77
The second group contains the prototype selection methods. 第2のグループにはプロトタイプの選択方法が含まれている。 0.59
As the name suggests, a subset of samples from the given cluster is selected to represent it. 名前が示すように、与えられたクラスタからのサンプルのサブセットがそれを表すために選択されます。 0.74
Prototype selection is a well-explored field with many approaches, see, e g [13]. プロトタイプの選択は、例えば[13]のように、多くのアプローチを持つよく検討された分野である。 0.64
英語(論文から抽出)日本語訳スコア
However, most of the current algorithms exploit the properties of the metric space, e g , structured sparsity [14], l1-norm induced selection [15] or identification of borderline objects [16]. しかし、現在のアルゴリズムのほとんどは、距離空間の性質、例えば、構造化された空間[14]、l1-ノルム誘導選択[15]、境界線オブジェクト[16]を利用する。
訳抜け防止モード: しかし、現在のアルゴリズムのほとんどは計量空間の性質を利用する。 eg, 構造空間[14], l1-ノルム誘導選択[15] 境界線オブジェクトの識別 [16 ]
0.74
When we leave the luxury of the metric space and focus on situations where only a pairwise similarity exists or where averaging of existing samples may create an object without meaning, there is not much previous work. 計量空間の豪華さを残して、ペア回りの類似性のみが存在する状況や、既存のサンプルの平均値が意味のないオブジェクトを生成できる状況にフォーカスすると、以前の作業はあまりありません。 0.70
The δ-medoids [9] algorithm uses the idea of k-medoids to semi-greedily cover the space with δ-neighbourhoods, in which it then looks for an optimal medoid to represent a given neighbourhood. δ-メドイド [9] アルゴリズムは k-メドイドのアイデアを用いて、δ-近傍で空間を半厳密にカバーし、与えられた近傍を表す最適なメドイドを探す。 0.65
The main issue of this method is the selection of δ: this hyperparameter has to to be fine-tuned based on the domain. この方法の主な問題はδの選択である:このハイパーパラメータはドメインに基づいて微調整されなければならない。 0.88
The DS3 [8] algorithm calculates the full similarity matrix and then selects representatives by a row-sparsity regularized trace minimization program which tries to minimize the rows needed to encode the whole matrix. ds3 [8]アルゴリズムは完全類似度行列を計算し、行列全体を符号化するのに必要な行を最小化しようとする行分離正規化トレース最小化プログラムによって代表者を選択する。 0.70
The overall computational complexity is the most significant disadvantage of this algorithm, despite some proposed approximate estimation of the similarity matrix using only a subset of the data. 全体の計算複雑性は、データのサブセットのみを用いて類似度行列を近似的に推定する提案があるにもかかわらず、このアルゴリズムの最も重要な欠点である。 0.76
The proposed method for Cluster Representatives Selection (CRS) approximates the topological structure of the data by creating a reverse k-NN graph. クラスタ代表選択法(CRS)は,逆k-NNグラフを作成することにより,データの位相構造を近似する。 0.83
CPS then iteratively selects nodes with the biggest reverse neighbourhoods as representatives of the data. 次に、CPSはデータの代表として、最大の逆近傍を持つノードを反復的に選択する。 0.57
This approach systematically minimizes the number of pairwise comparisons to reduce computational complexity while accurately representing the data. このアプローチは、データを正確に表現しながら計算複雑性を低減するために、ペア比較の数を体系的に最小化する。
訳抜け防止モード: このアプローチは、ペアワイズ比較の数を体系的に最小化する データを正確に表現しながら 計算の複雑さを減らします
0.68
3 Problem Formulation In this section, we define the problem of prototype-based representation of clusters and the nearest prototype classification (NPC). 3 問題定式化 本稿では,クラスタのプロトタイプベース表現の問題と,最も近いプロトタイプ分類(NPC)について述べる。 0.81
As we already stated in Introduction, we study the prototypes selection in general cases, including non-metric spaces. はじめに述べたように、非計量空間を含む一般的なケースでプロトタイプの選択を研究する。 0.69
Therefore, we further assume that a cluster prototype is always specified as (possibly small) subset of its members. したがって、クラスタプロトタイプはそのメンバの(おそらく小さい)サブセットとして常に指定されていると仮定する。 0.73
x and(cid:70) Ci = X. x および (cid:70) ci = x。 0.87
Let Ci = {x1, x2, ..., xn} be a cluster of size n. For x ∈ Ci, let us ci = {x1, x2, ..., xn} を大きさ n のクラスターとする。 0.56
Cluster prototypes Let T be an arbitrary space of objects for which a pairwise similarity function s : T × T → R is defined and let X ⊆ T be a set of (training) samples. クラスタのプロトタイプ T を任意の対象の空間とし、T × T → R を対の類似関数 s : T × T → R と定義し、X を(訓練)標本の集合とする。 0.81
Let C = {C1, ..., Cm} be a clustering of X such that Ci ∩ Cj = ∅,∀i (cid:54)= j denote U k the k closest samples to x, i.e., the set of k samples that have the highest similarity to x in the rest of the cluster Ci \ {x}. c = {c1, ..., cm} を x のクラスタリングとし、ci が cj = s, i (cid:54)= j を u k を x に最も近いサンプル、すなわち、クラスタ ci \ {x} の残りの部分において x に最も近い類似性を持つ k 個のサンプルの集合とする。 0.81
Then the goal of the prototype selection is to find a subset of samples Ri ⊆ Ci for each cluster such that: (1) The set Ri is then called the prototype of the cluster Ci. すると、プロトタイプ選択のゴールは、各クラスタに対して、次のようにサンプルのサブセットを見つけることである: 1) 集合 Ri は、クラスタ Ci のプロトタイプと呼ばれる。 0.75
In case of ties, we pick the samples with lowest indices i. 結び目の場合は、最小のインデックスiのサンプルを選択します。 0.58
∀x ∈ Ci ∃ r ∈ Ri . . . x ∈ Ci . r ∈ Ri 0.64
In order to minimize computational requirements of NPC, we search for a minimal set of cluster representatives Ri for each cluster, which satisfies the npcの計算要件を最小限に抑えるため、各クラスタのクラスタ代表数riの最小セットを探索し、それを満たす。
訳抜け防止モード: NPCの計算要求を最小限に抑えるため,各クラスタに対して最小のクラスタ代表数Riを求める。 満足のいくもの
0.76
: x ∈ U k x ∈ u k である。 0.71
r r 0.85
英語(論文から抽出)日本語訳スコア
(cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:91) (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:91) 0.72
(cid:12)(cid:12)(cid :12)(cid:12)(cid:12) ≥ |Ci|, (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) ≥ |ci| である。 0.64
U k r ∩ Ci うーん、うーん、うーん。 0.34
(3) coverage requirement (1): (3) 範囲要件(1) 0.68
|Ri| = min |Ri| = min 0.78
R (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) R (cid:12)(cid:12)(cid :12)(cid:12) 0.87
(cid:40)(cid:91) (cid:40)(cid:91) 0.75
r∈R (cid:41)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12) リョール (cid:41)(cid:12)(cid :12)(cid:12)(cid:12) 0.58
U k r = Ci U K r = Ci 0.81
Note that several sets might satisfy this coverage requirement. いくつかの集合がこのカバレッジ要件を満たすかもしれないことに注意。 0.45
(2) Relaxed prototypes Finding cluster prototypes that fully meet the coverage requirement (1) might pose an unnecessary computational burden. (2) Relaxed prototypes Finding cluster prototypes that fully enough the coverage requirements (1) may may caused a unnecessary compute burden。 0.84
In many cases, a smaller prototype which is much easier to obtain can capture enough of the important characteristics of a cluster despite possibly not covering all of its members (e g , a few outliers). 多くの場合、より簡単に手に入る小さなプロトタイプは、メンバー(例えば、いくつかの外れ値)をすべてカバーしていないにもかかわらず、クラスタの重要な特性を十分に捉えることができる。 0.78
Motivated by this observation, we introduce a relaxed requirement on cluster prototypes. この観察に感銘を受け、我々はクラスタープロトタイプの緩和要求を導入する。 0.65
We say that a set Ri ⊆ Ci is a representative prototype of cluster Ci if the following condition is met: 以下の条件が満たされた場合、集合 ri と ci はクラスタ ci の代表的なプロトタイプであると言う。 0.76
r∈Ri for a preset parameter  ∈ (0, 1]. プリセットパラメータ s ∈ (0, 1] に対する rψri である。 0.75
In further work, we replace the requirement (1) with its relaxed version (3). さらなる作業では、要件 (1) を緩和バージョン (3) に置き換える。 0.62
In case of need, the full coverage requirement can be enforced by simply setting  = 1. 必要であれば、完全なカバレッジ要件は、単に s = 1 を設定するだけで実施できる。 0.72
Similarly, also in the relaxed version, we seek for a prototype with minimal cardinality which satisfies (3). 同様に、リラックスしたバージョンでは、(3)を満たす最小濃度を持つプロトタイプを探します。 0.64
Nearest Prototype Classification Having the representative prototypes for all clusters, we now describe how the classification is performed. 最寄りのプロトタイプ分類 すべてのクラスタの代表的なプロトタイプを持ち、その分類方法を説明する。 0.74
In the nearest prototype classification (NPC), an unseen sample x is classified to the cluster (i.e., the respective target class is assigned to the sample) which is represented by the prototype with the highest similarity to the sample x. 最寄りのプロトタイプ分類(NPC)では、未確認のサンプルxを、サンプルxと最も類似したプロトタイプで表されるクラスタ(すなわち、各ターゲットクラスをサンプルに割り当てる)に分類する。
訳抜け防止モード: 最寄りのプロトタイプ分類(npc)では、未検出のサンプルxがクラスタに分類される (すなわち、各ターゲットクラスがサンプルに割り当てられる。) これは、サンプルxと最もよく似たプロトタイプによって表現される。
0.79
As the cluster prototypes are disjoint sets, the nearest prototype is defined as the prototype containing the sample with the highest similarity to x. クラスタのプロトタイプは非連結集合であるため、最も近いプロトタイプは、x に最も近いサンプルを含むプロトタイプとして定義される。 0.69
Formally, given the prototypes of all clusters R = {R1, ..., Rm}, the nearest prototype, denoted R∗, is the prototype containing r∗, where 正式には、すべてのクラスタ R = {R1, ..., Rm} のプロトタイプを考えると、最も近いプロトタイプ R∗ は r∗ を含むプロトタイプである。 0.74
∗ r = arg max ∗ r =arg max 0.81
r∈(cid:83) Ri rhtml(cid:83) ri 0.55
s(x, r). s(x, r) である。 0.81
Again, we resolve ties by picking the candidate with lowest index in the 再び、最も低い指標を持つ候補を選ぶことで関係を解消する。 0.71
dataset. Finally, the sample x is classified with the same label as that of the cluster データセット。 最後に、サンプルxはクラスタと同じラベルで分類される。 0.67
represented by the prototype R∗. R∗ のプロトタイプで表される。 0.62
4 Cluster Representatives Selection 4つのクラスタ代表者 0.61
In this section, we describe our method CRS for building the cluster prototypes. 本稿では,クラスタプロトタイプ構築のためのCRSについて述べる。 0.70
The entire method is composed of two steps that are discussed in more detail メソッド全体は、より詳細に議論される2つのステップで構成されています 0.71
英語(論文から抽出)日本語訳スコア
in individual subsections. 個々のサブセクションで 0.71
First, given a cluster C and a similarity measure s, a reverse k-NN graph G is constructed from objects C using the pairwise similarity s. Then, the graph G is used to select the representatives that satisfy the coverage requirement while minimizing the size of the cluster prototype. まず、クラスタCと類似度尺度sとが与えられた場合、対の類似度sを用いてオブジェクトCから逆k-NNグラフGを構築し、次いで、クラスタプロトタイプのサイズを最小化しつつ、カバレッジ要件を満たす代表者を選択する。
訳抜け防止モード: まず、クラスター C と類似度測度 s が与えられる。 逆 k - NN グラフ G は、対の類似性 s を用いて C 個のオブジェクトから構成される。 グラフ G が使われる 範囲の要件を満たす代表を選定する クラスタープロトタイプのサイズを最小化しながら
0.83
The simplified scheme of the whole process is depicted in Figure 1. プロセス全体の単純化されたスキームを図1に示します。 0.82
(a) dataset (b) k-neighbourhood (a)データセット (b)k-neighbourhood 0.83
(c) reverse neighbourhood Fig. (c)逆隣地 フィギュア。 0.59
1. Illustration of the steps of CRS algorithm. 1. CRSアルゴリズムのステップの図示。 0.71
(a) Visualization of a toy 2D dataset. (a)おもちゃの2Dデータセットの可視化。 0.78
(b) 2-NN graph created from from the dataset. b)データセットから生成された2-NNグラフ。 0.81
(c) Reverse graph created from the graph depicted in (b). (c) (b)に描かれたグラフから作成された逆グラフ 0.90
Point C is a representative of A, B, D, E and would be a good choice first choice of a representative. 点 C は A, B, D, E の代表であり、代表者の第一選択となる。
訳抜け防止モード: 点 c は a, b, d, e の代表である 代表者の第一選択として よい選択になるでしょう
0.78
Depending on the coverage parameter , the node F could be considered an outlier or also added to the representation. カバレッジパラメーター s によって、ノード f は外れ値と見なすこともできるし、表現に付加することもできる。 0.63
4.1 Building the Prototype For the purpose of building the prototype for a cluster C a weighted reverse −1 C = (V, E, w), where V is the set of k-NN graph G all objects in cluster C, E is a set of edges and w is a weight vector. 4.1 原型を構築する クラスタ C のプロトタイプを構築するために、重み付き逆 −1 C = (V, E, w) ここで V は k-NN グラフ G の集合であり、クラスタ C 内のすべての対象 E は辺の集合であり、w は重みベクトルである。 0.89
An edge between two nodes vi, vj ∈ Vi(cid:54)=j exists if vi ∈ U k , while the edge weight wij is given by the similarity s between the connected nodes, wij = s(vi, vj). 二つのノードvi, vj ∈ Vi(cid:54)=j の間の辺は vi ∈ U k であれば存在し、一方、エッジウェイト wij は連結ノード間の類似性 s, wij = s(vi, vj) によって与えられる。 0.79
is used. It is defined as G 使われています は G と定義される。 0.67
−1 C vj −1 C −1C vj −1C 0.84
The effective construction of such graph is enabled by employing the NNDescent [17] algorithm which produces a k-NN graph GC. このようなグラフを効率的に構築するには、k-NNグラフGCを生成するNNDescent[17]アルゴリズムを用いる。 0.80
The reverse k-NN graph G is then obtained from GC by simply reversing directions of the edges in GC. 逆k-nnグラフgは、gcのエッジの方向を単純に反転することによってgcから得られる。 0.68
NN-Descent is a fast converging approximate method for the k-NN graph construction. NN-Descentはk-NNグラフ構築のための高速収束近似法である。 0.71
It exploits the idea that “a neighbour of a neighbour is also likely to be a neighbour” to locally explore neighbouring nodes for better solutions. これは「隣人の隣人が隣人になる可能性も高い」という考えを生かして、より良い解決策を求めて近隣のノードを探索する。
訳抜け防止モード: それは「隣人の隣人もおそらく」というアイデアを生かしています より優れたソリューションのために、近隣のノードをローカルに探索する。
0.72
, we want to ensure that each object x is それぞれのオブジェクト x が確実に 0.44
Having the reverse k-NN graph G 逆 k-NN グラフ G を持つこと 0.76
at least τ-similar to all its neighbours, i.e., 少なくとも τ はすべての近隣諸国、すなわち 0.66
−1 C Omitting all edges with weight lower than τ not only lowers the memory requirements, but it also unfolds objects with large neighbourhood as good representative candidates. −1C τより重量が低いすべてのエッジをOmizing all edgesは、メモリ要件を下げるだけでなく、優れた代表候補として大きな近傍のオブジェクトを広げる。 0.77
(∀y ∈ Ux : s(x, y) ≥ τ ) . (y ∈ Ux : s(x, y) ≥ τ ) である。 0.75
CABEDFBADECFEDBACF CABEDFADECFEDBACF 0.69
英語(論文から抽出)日本語訳スコア
The selection of representatives is treated as a minimum vertex cover problem −1 on G . 代表者の選択は、G 上の最小頂点被覆問題−1として扱われる。 0.68
We use a greedy algorithm which iteratively selects objects with maximal C |U| as representatives and marks them and their neighbourhood as covered. 極大 c |u| を代表としてオブジェクトを反復的に選択し、それらとその近傍を被覆するグリーディアルゴリズムを用いる。 0.71
The algorithm stops when the coverage requirement (3) is met (see Section 3). このアルゴリズムはカバレッジ要件(3)が満たされると停止する(セクション3参照)。 0.71
The whole algorithm is summarized in Algorithm 1. アルゴリズム全体はアルゴリズム1にまとめられている。 0.80
Algorithm 1: Pseudocode for Cluster Representatives Selection Data: cluster C = {c1, ..., cn}, similarity s, coverage threshold  Result: set of selected representatives R ⊆ C アルゴリズム1:クラスタ代表者の疑似コード選択データ:クラスタc = {c1, ..., cn}, similarity s, coverage threshold , result: set of select representatives r , c
訳抜け防止モード: アルゴリズム1 : クラスタ代表者選択データのための擬似コード : クラスタc = c1 , ... , cn } , similarity s , coverage threshold , result : set of select representatives r , c
0.84
−1 C = ReverseGraph(GC) −1 C = ReverseGraph(GC) 0.96
1 GC = NN-Descent(C, s) 2 G 3 Z = C //set of uncovered objects 4 R = {} 5 while |C|−|Z| 6 1 GC = NN-Descent(C, s) 2 G 3 Z = C //set of uncovered objects 4 R = {} 5 while |C|−|Z| 6 0.87
//set of representatives |C| <  do c∈Z 代表者 |C| < > do c∂Z 0.58
r = arg max((cid:80) r = arg max((cid:80) 0.96
s(c, u), u ∈ Uc) s(c, u), u ∈ Uc) 0.78
Z = Z \ Ur R = R ∪ {r} Z = Z \ Ur R = R > {r} 0.84
7 8 9 end 10 return R 7 8 9 end 10 return R 0.85
An example of a cluster prototype selected by the CRS algorithm is presented CRSアルゴリズムによって選択されたクラスタプロトタイプの例を示す。 0.82
in Figure 2. Fig. 図2に示す。 フィギュア。 0.59
2. Selection of representatives CRS with different Ks for a 2-dimensional dataset with 255 samples. 2. 255サンプルの2次元データセットのための異なるksを持つ代表crsの選択。 0.80
For better comparison δ-medoids and DS3 are also shown. より良い比較のために δ-メディドとds3も示される。 0.59
CRS takes into account the density of different parts of the cluster and selects representatives accordingly. CRSはクラスタの異なる部分の密度を考慮に入れ、それに従って代表を選択する。 0.68
δ-Medoids covers the dataset entirely by evenly distributed representatives. δ-medoidsは、データセットを均等に分散した代表者によって完全にカバーされる。 0.39
DS3 in selects the least representatives but does not capture the overall structure of the cluster very well. DS3は最小代表数を選択するが、クラスタ全体の構造をうまく捉えていない。 0.75
英語(論文から抽出)日本語訳スコア
4.2 Discussion on parameters This subsection summarizes the parameters of the CRS method. 4.2 パラメータに関する考察 CRS法のパラメータを要約する。 0.80
– k: number of neighbors for the k-NN graph creation. k: k-NNグラフ作成の隣人の数。 0.70
When k is high, each object covers more neighbours, but on the other hand it also increases the number of pairwise similarity calculations. kが高い場合、各対象はより多くの近傍をカバーするが、一方、ペアの類似性計算の数も増加する。 0.77
This trade-off is illustrated for different values of k in Figure 3. このトレードオフは図3のkの異なる値に対して示されます。 0.70
Due to the large impact of this parameter on properties of the produced representations and computational requirements, we further study its behaviour in more detail in a dedicated experiment in Section 5. このパラメータが生成した表現と計算要求の特性に与える影響が大きいため、セクション5の専用実験において、その振る舞いをさらに詳細に研究する。 0.79
Fig. 3. Number of representatives being selected and the quality of representation are both controlled by k. As each object explores a bigger neighbourhood for higher k, the number of other objects it represents grows, therefore the number of representatives decreases. フィギュア。 3. 各オブジェクトは、より高いkのより大きな近傍を探索するにつれて、その表現する他のオブジェクトの数は増加するので、代表者の数は減少する。
訳抜け防止モード: フィギュア。 3. 選出される代表者数 表現の質はkによって制御されます それぞれの物体は、より高次のkのより大きな近傍を探索する。 表現する他の物体の数が増えます 代表数は減少する。
0.67
On the other hand, with less representatives, some information about the structure is lost, as in the case of k = 15. 一方、代表数が少ない場合、k = 15 の場合のように、構造に関するいくつかの情報は失われる。 0.73
– : coverage parameter for the relaxed coverage requirement as introduced in Section 3. 第3節で導入された緩和されたカバレッジ要件のカバレッジパラメータ。 0.51
In this work, we set it to 0.95 such that the vast majority of each cluster is still covered but outliers do not influence the prototypes. この研究では、各クラスタの大多数がまだカバーされているが、出力値がプロトタイプに影響を与えないよう、0.95に設定した。 0.65
– τ: threshold on weights, determining which edges will be kept in the graph (see Section 4.1). τ: 重みのしきい値、どの辺がグラフに保持されるかを決定する(セクション4.1)。 0.77
By default it is automatically set to the value of デフォルトでは自動的に値に設定されます 0.94
−1 C G homogeneity h(C) of the cluster C: −1C クラスターcのg相同性h(c): 0.76
(cid:88) h(C) = (cid:88) h(C) = 0.82
1 |C|(|C| − 1) 1 |C|(|C| − 1) 0.80
xi,xj∈C,i(cid:54)=j xi,xjhtmlc,i(cid:54) =j 0.80
s(xi, xj) (4) s(xi, xj) (4) 0.85
Additionally, the NN-Descent algorithm, used within the CRS method, has two more parameters that specify its behaviour during the k-NN graph creation. さらに、CRS法で使用されるNN-Descentアルゴリズムには、k-NNグラフ作成時の振る舞いを規定する2つのパラメータがある。 0.67
First, the δnn parameter which is used for early termination of the NN-Descent algorithm when the number of changes in the constructed graph is minimal. まず、構築されたグラフの変更回数が最小である場合にnn-descentアルゴリズムの早期終了に使用されるδnnパラメータ。 0.77
We set it to 0.001, as suggested by the authors of the original work [17]. 原著[17]の著者が示唆するように、0.001に設定した。
訳抜け防止モード: 私たちは0.001に設定しました。 オリジナルの作品[17 ]の著者によって提案された。
0.64
Second, the sample rate ρ controls the number of reverse neighbours to be explored in each iteration of NN-Descent. 第二に、サンプルレートρはNN-Descentの各イテレーションで探索される逆近傍の数を制御する。 0.70
Again, we set it to 0.7 to speed up the k-NN creation while not diverging too far from the optimal solution in accordance with suggestions published in [17]. 繰り返しますが、[17]で公開された提案に従って最適解から遠ざからず、k-NN生成を高速化するために0.7に設定しました。 0.66
英語(論文から抽出)日本語訳スコア
5 Experiments This section presents experimental evaluation of the CRS algorithm on multiple datasets from very different domains that cover computer networks, text documents processing and image classification. 5 実験 この節では,コンピュータネットワーク,テキスト処理,画像分類を網羅する,非常に異なる領域の複数のデータセットを対象としたCRSアルゴリズムの実験評価を行う。 0.77
In the first experiment, we study the influence of the parameter k (which determines the number of nearest neighbors used for building the underlying k-NN graph). 最初の実験では、パラメータ k の影響(基礎となる k-NN グラフを構築するのに最も近い隣人の数を決定する)について検討する。 0.77
Next, we compare the CRS method to the state-of-the-art techniques DS3[8] and δ-medoids [9] in the nearest prototype classification task on different datasets. 次に, CRS法と最先端技術DS3[8]とδ-メノイド[9]を比較する。
訳抜け防止モード: 次に,CRS法と最先端技術DS3[8]を比較した。 そして δ - medoids [9 ] は、異なるデータセット上で最も近いプロトタイプ分類タスクです。
0.70
We set h as an approximate homogeneity calculated from random 5% of the cluster. h をクラスターのランダムな 5% から計算された近似同質性とする。 0.77
We use h as δ for δ-Medoids algorithm. δ-メドイドアルゴリズムの δ として h を用いる。 0.72
It makes the most sense in comparing with CRS, because CRS is also restricting the similarity by h in reverse graph creation. CRS は逆グラフ生成における h による類似性も制限しているため、CRS との比較で最も理にかなっている。 0.77
The best results for DS3 we obtained with p = inf and α = 3, while creating the full similarity matrix for the entire cluster. ds3の最良の結果は、p = inf と α = 3 で得られ、クラスタ全体の完全な類似性行列を作成した。 0.78
Finally the parameters for CRS are discussed in Section 4.2. 最後に、CRSのパラメータをセクション4.2で議論する。 0.64
The following experiment explores the impact of k in greater detail. 次の実験では、kの影響をより詳細に調べる。 0.72
Impact of k 5.1 When building cluster prototypes by the CRS method, the number of nearest neighbors considered for building the k-NN graph (specified by the parameter k) plays very important role. kの影響 5.1 CRS法でクラスタプロトタイプを構築する場合、k-NNグラフ(パラメータkで指定)を構築するために考慮された近隣住民の数は、非常に重要な役割を果たす。 0.71
With small values of k, each object represents only few of its neighbors that are most similar to it. k の小さな値を持つ各対象は、それと最もよく似た近傍のごくわずかしか表現しない。 0.78
However, this also increases the number of representatives needed to sufficiently cover the cluster. しかし、クラスタを十分にカバーするために必要な代表者数も増加する。 0.71
On the other hand, higher values of k produce smaller prototypes as each representative is able to cover more objects. 一方、kのより高い値は、各代表者がより多くのオブジェクトをカバーできるため、より小さなプロトタイプを生成する。 0.67
Nonetheless, this is at the cost of increased computational burden because the cost of k-NN creation increases rapidly with higher ks. しかしながら、k-NN生成のコストはksの増加とともに急速に増加するため、計算負荷の増加によるコストがかかる。 0.66
These trends can be well observed in Figure 4 which shows classification precision, sizes of created prototypes and numbers of similarity function evaluations depending on k for several clusters that differ in their homogeneity and sizes. これらの傾向は図4でよく観察でき、等質性や大きさが異なるいくつかのクラスタに対して k に依存する分類精度、原型のサイズ、類似度関数の評価数を示す。 0.79
We can see the changing trade-off between computational requirements (blue line) and memory requirements (red line) as the k increases. kが増加するにつれて、計算要求(ブルーライン)とメモリ要求(レッドライン)の間のトレードオフが変化するのがわかります。 0.64
However, this is mostly without significant impact on classification precision. しかし、これは主に分類精度に大きな影響を与えない。 0.79
The parameter k can be therefore set depending on the preferences on computational requirements without significantly decreasing the classification performance. したがって、パラメータkは、分類性能を著しく低下させることなく、計算要求の好みに応じて設定することができる。 0.62
5.2 Datasets In this section we briefly describe the three datasets used in the ongoing subsections for experimental comparison of individual methods. 5.2 データセット この節では、個々のメソッドを実験的に比較するために、進行中のサブセクションで使用される3つのデータセットを簡潔に記述する。 0.56
MNIST Fashion The MNIST Fashion [18] is a well established dataset for image recognition consisting of 60000 black and white images of fashion items belonging to 10 classes. MNIST Fashion MNIST Fashion [18]は10のクラスに属するファッションアイテムの60000の白黒画像からなる画像認識のためのよく確立されたデータセットである。 0.89
It recently replaced the overused handwritten digits datasets in many benchmarks. 最近、多くのベンチマークで多用された手書き桁データセットを置き換える。 0.60
In case of this dataset, the cosine similarity was used as the similarity function s. このデータセットの場合、コサイン類似度を類似度関数sとして用いた。 0.81
英語(論文から抽出)日本語訳スコア
(a) MNIST Fashion - Dress (a)MNISTファッション-ドレス 0.76
(b) Medium Network Cluster (b)Medium Network Cluster 0.79
(c) MNIST Fashion - Sandal (c)MNISTファッション-サンダル 0.75
(d) Big Network Cluster (d)大規模ネットワーククラスタ 0.88
Fig. 4. Illustration of how the selection of k influences the number of representatives and number of similarity computations. フィギュア。 4. k の選択が代表数と類似度計算数にどのように影響するかを示す。 0.68
The number of representatives is in relative numbers to the size of the cluster. 代表者の数はクラスタのサイズに対して相対的な数である。 0.83
For different clusters as k increases the relative number of comparisons also increases. 異なるクラスタに対して、k は相対的な比較数を増加させる。 0.67
However, the size of prototype selected decreases steeply while the precision only decreases slowly. しかし、選択されたプロトタイプのサイズは急激に減少し、精度はゆっくりしか低下しない。 0.60
20 Newsgroup This dataset is a known benchmark dataset for text documents processing. 20 Newsgroup このデータセットは、テキスト文書処理のための既知のベンチマークデータセットである。 0.73
It is composed of nearly 20 thousand newspaper documents from 20 different classes (topics). 20の異なるクラス(トピック)から2万近い新聞文書で構成されている。 0.74
The dataset was preprocessed such that each document is represented by a TF-IDF frequency vector. データセットは事前に処理され、各文書はtf-idf周波数ベクトルで表現される。 0.66
As a similarity function, we again use the cosine similarity which is a common choice in the domain of text documents processing. 類似度関数として、テキスト文書処理の分野において共通の選択であるコサイン類似度を再度使用する。 0.82
Private Network Dataset This dataset was collected on a corporate computer network, originally for the purpose of network host clustering based on their behavior [6]. プライベートネットワークデータセット このデータセットは企業コンピュータネットワーク上で収集され、元々は、その動作に基づいてネットワークホストクラスタリングを目的としていた [6]。 0.79
The work defines a specific similarity measure on top of network hosts which we adopt for this paper. この研究は、我々がこの論文に採用したネットワークホスト上の特定の類似度尺度を定義している。 0.61
Clusters of network hosts were defined according to results achieved in the original work as well. ネットワークホストのクラスタは、元の作業で得られた結果に従っても定義された。 0.69
Additionally, for the purposes of the evaluation, clusters smaller than 10 members were not considered, since such small clusters can be easily represented by any method. また,評価目的では,このような小さなクラスタを任意の方法で容易に表現できるため,10人未満のクラスタは考慮されなかった。 0.83
In contrast 対照的に 0.66
英語(論文から抽出)日本語訳スコア
to the previous datasets, the sizes and values of homogeneity of clusters in the Network dataset differ significantly. 以前のデータセットでは、ネットワークデータセット内のクラスタの均質性のサイズと値は著しく異なる。 0.84
5.3 Evaluation of Results In this section we present the results for each dataset in detail. 5.3 結果の評価 この節では、各データセットの結果を詳細に述べます。 0.80
The main results are summarized in Table 1. 主な結果は表1にまとめられている。 0.85
For a more complete picture we also included results for a random 5% and all 100% of the cluster as a prototype. さらに完全な図では、ランダムな5%の結果と、100%のクラスタがプロトタイプとして含まれています。 0.74
The statistical comparison of the methods can be found in Figure 5. この方法の統計的比較は図5に示すことができる。 0.82
Better rankings for some of CRS methods reflect, that CRS only covers  which removes the outliers that decrease precision and recall of full cluster representation. CRSメソッドのいくつかでは、より優れたランキングが反映されており、CRSは、精度を低下させ、完全なクラスタ表現をリコールする外れ値を取り除いている。 0.56
20Newsgroup 20ニュースグループ 0.53
Method MNIST Fashion δ-medoids 0.763/0.744 (4.73%) 0.542/0.515 (14.51%) 0.865/0.978 (7.38%) 0.657/0.563 (0.07%) 0.133/0.132 (0.64%) 0.87/0.977 (1.88%) DS3 random-5% 0.793/0.784 (5.0%) 0.452/0.435 (5.06%) 0.958/0.97 (5.09%) full-100% 0.823/0.817 (100.0%) 0.56/0.548 (100.0%) 0.987/0.963 (100.0%) 0.855/0.852 (87.71%) 0.635/0.632 (56.58%) 0.988/0.958 (65.31%) CRS-k5 0.836/0.826 (15.37%) 0.538/0.516 (7.14%) 0.985/0.965 (7.74%) CRS-k10 CRS-k15 0.828/0.823 (5.08%) 0.522/0.488 (5.17%) 0.983/0.982 (5.26%) Method MNIST Fashion δ-medoids 0.763/0.744 (4.73%) 0.542/0.515 (14.51%) 0.865/0.978 (7.38%) 0.657/0.563 (0.07%) 0.133/0.132 (0.64%) 0.87/0.977 (1.88%) DS3 random-5% 0.793/0.784 (5.0%) 0.452/0.435 (5.06%) 0.958/0.97 (5.09%) full-100% 0.823/0.817 (100.0%) 0.56/0.548 (100.0%) 0.987/0.963 (100.0%) 0.855/0.852 (87.71%) 0.635/0.632 (56.58%) 0.988/0.958 (65.31%) CRS-k5 0.836/0.826 (15.37%) 0.538/0.516 (7.14%) 0.985/0.965 (7.74%) CRS-k10 CRS-k15 0.828/0.823 (5.08%) 0.522/0.488 (5.17%) 0.983/0.982 (5.26%) 0.46
Network Table 1. ネットワーク 表1。 0.76
Average precision/recall values for each method used on each dataset. 各データセットで使用される各メソッドの平均精度/リコール値。 0.74
The table also shows the percentage of the cluster that was selected as a prototype. テーブルはまた、プロトタイプとして選択されたクラスタの割合も示している。 0.77
Our algorithm is on par with existing methods while selecting noticeably fewer representatives. 我々のアルゴリズムは既存の手法と同等であり、顕著に少ない代表を選択する。 0.65
(a) MNIST precision (a)MNIST精度 0.79
(b) news precision (c) network precision (b)ニュース精度 (c)ネットワークの精度 0.87
(d) MNIST recall (d)MNISTリコール 0.66
(e) news recall (e)ニュースリコール 0.71
(f) network recall (f)ネットワークリコール 0.71
Fig. 5. Critical difference diagram comparison (cf. フィギュア。 5. 臨界差分図の比較 (cf。 0.69
[19]) of algorithms constructed using Friedman’s test with correction for multiple post-hoc hypotheses by Shaffer [20]. Shaffer[20]による複数のポストホック仮説を補正したFriedmanのテストを用いて構築したアルゴリズムの例([19])。 0.77
The diagrams show the average rank of each algorithm over all clusters in each dataset, groups of algorithms that are not significantly different (p=0.05) are connected. ダイアグラムは、各データセットの全てのクラスタにおける各アルゴリズムの平均ランクを示し、大きく異なるアルゴリズム群(p=0.05)が接続されている。 0.84
12345678CRSk5CRSk10C RSk15fullclusterrand omδ−medoidsDS312345678CR Sk5fullclusterCRSK10 δ−medoidsCRSk15randomD S312345678CRSk15CRSk 10CRSk5fullclusterra ndomDS3δ−medoids12345678CRSk5 CRSk15CRSk10fullclus terrandomδ−medoidsDS312345678CR Sk5fullclusterCRSK10 δ−medoidsCRSk15randomD S312345678δ−medoidsCRSk15DS3rand omCRSk10CRSk5fullclu ster 12345678CRSk5CRSk15f ullclusterrandomδ−medoidsDS312345678CR SkK10δ−medoidsCRSk15randomD S312345678CRSk15CRSk 10CRSk5fullclusterra ndomDS3δ−medoids12345678CRSk5 CRSk15CRSk10fullclus terrandomδ−medoidsDS312345678CR Sk5fullclusterCRSK10 δ−medoidsCRSk15randomD S312345678δSk15 0.04
英語(論文から抽出)日本語訳スコア
When evaluating the experiments, we take into account both precision/recall and the percentage of samples selected as prototypes. 実験を評価する際, 精度/リコールと, プロトタイプとして選択した試料の割合を考慮に入れる。 0.73
As we have shown in the experiment in Section 5.1, CRS can be tuned by the parameter k to significantly reduce the number of representatives and maintain a high precision/recall values. 第5.1節で示したように、crsはパラメータkで調整でき、代表数を大幅に削減し、高精度/リコール値を維持することができる。
訳抜け防止モード: 実験の5.1節で示したように crs はパラメータ k で調整できる 代表数を大幅に削減し、高精度/リコール値を維持する。
0.71
When using the full cluster as its prototype, the average values of precision and recall are slightly lower than when using the CRS method. 完全クラスタをプロトタイプとして使用する場合、精度とリコールの平均値はCRS法よりもわずかに低い。 0.65
This shows that CRS with  = 0.95 makes the classification immune to outliers which can otherwise decrease the classification quality. このことは、s = 0.95 の CRS が、分類品質を低下させる可能性のある外れ値に分類を免疫させることを示している。 0.59
The DS3 method selects a significantly lower number of representatives than any other method. DS3法は他の方法よりもはるかに少ない代表数を選択する。 0.76
However, it is at the cost of lower precision and recall values. しかし、精度の低下とリコールのコストがかかる。 0.44
Runtimes of individual algorithms also differ significantly. 個々のアルゴリズムの実行時間も大きく異なる。 0.75
We evaluate the runtime requirements of each algorithm by the relative number of similarity computations S defined as: 各アルゴリズムのランタイム要件を、以下の類似性計算sの相対数で評価する。 0.74
, (5) S = Sactual Sf ull , (5) S = sactual sf ull 0.77
where Sactual stands for the actual number of comparisons made and Sf ull is the hypothetical number needed for computing full similarity matrix. Sactual は実際の比較数を表し、Sf ull は完全類似性行列を計算するのに必要な仮説数である。 0.73
We use DS3 with the full similarity matrix to get most accurate results, therefore SDS3 = 1. 完全類似行列を持つDS3を用いて最も正確な結果を得るので、SDS3 = 1 となる。 0.71
For δ-Medoids the number of computations performed can not be easily preset. δ-メディドの場合、実行された計算の数は容易にはプリセットできない。 0.57
Therefore, we averaged the number of comparisons over different values of Sδ ∈ [0.45, 0.7] (the number might differ significantly for different values of Sδ). したがって、Sδ ∈ [0.45, 0.7] の異なる値に対する比較の回数を平均化した(Sδ の異なる値に対して、その数は著しく異なるかもしれない)。 0.71
For CRS the number of comparisons is influenced by k, homogeneity of each cluster and its size. CRSの場合、比較の数はk、各クラスタの均一性とそのサイズに影響される。 0.73
The impact of k was discussed in detail in Section 5.1. kの影響は、セクション5.1で詳細に議論された。 0.63
The experiment shows that one can make assumptions about S based on the size of the cluster and k (i.e. この実験は、クラスタのサイズと k(すなわち)に基づいてSについて仮定できることを示した。 0.80
for MNIST Fashion dataset SCRS−k10 = 0.063, SCRS−k15 = 0.13). MNIST Fashion dataset SCRS−k10 = 0.063, SCRS−k15 = 0.13)。 0.69
MNIST Fashion The average homogeneity of a cluster in the MNIST Fashion dataset is 0.76. MNIST Fashion MNIST Fashionデータセットにおけるクラスタの平均均一性は0.76である。 0.82
This corresponds with a slower decline of the precision and recall values as the number of representatives decreases. これは、代表者数が減少するにつれて、精度とリコール値の低下に対応する。 0.67
In Figure 6 the steep decline of representatives selected decreases only slightly decreases the precision and recall for the each cluster. 図6では、選択された代表者の急激な減少は、各クラスタの精度とリコールをわずかに低下させる。 0.66
In the case of the the Dress cluster it even slightly increases from k = 10 to k = 15. ドレスクラスタの場合、さらに k = 10 から k = 15 へと増加する。 0.60
In Figure 7 are the confusion matrices for the methods. 図7では、メソッドの混乱行列を示します。 0.71
20Newsgroup The 20Newsgroup dataset has the lowest average homogeneity h = 0.0858 from all the datasets. 20Newsgroup 20Newsgroupデータセットは、すべてのデータセットから平均的同質度h = 0.0858 である。 0.68
The samples are less similar on average, therefore the lower precision and recall values. サンプルは平均的にあまり似ていないため、低い精度とリコール値である。 0.68
It reflects in the percentage of objects selected as representatives by the δ-Medoids algorithm. δ-medoidsアルゴリズムによって代表として選択されたオブジェクトの割合を反映している。 0.60
Confusion matrices for one cluster form each subgroup are in Figure 8. 各部分群からなる1つのクラスタの融合行列は図8にある。 0.67
Network Dataset The results for data collected in real network further prove assumptions made in Section 5.1. ネットワークデータセット 実ネットワークで収集されたデータの結果は、さらに第5.1節の仮定を証明する。 0.68
Figure 9 shows comparison of individual methods by means of precision and recall for selected large clusters as well as the impact of different values of k. 図9は、選択された大きなクラスターに対する精度とリコールによる個々の方法の比較と、kの異なる値の影響を示しています。 0.78
英語(論文から抽出)日本語訳スコア
Fig. 6. Visualization of precision and recall of all methods in relation to percentage of cluster selected on chosen clusters for the MNIST Fashion dataset. フィギュア。 6. MNIST Fashionデータセットの選択クラスタ上で選択されたクラスタの割合に関連して,すべてのメソッドの精度とリコールの可視化を行う。 0.67
Values 0.0 for some clusters for DS3 mean that less than 0.1% objects were selected as representatives. DS3のいくつかのクラスタの値0.0は0.1%未満のオブジェクトが代表として選択されたことを意味する。
訳抜け防止モード: ds3のクラスタの値 0.0 は 代表者は0.1%以下であった。
0.74
(a) CRS-k10 (a)CRS-k10 0.72
(b) δ-Medoids (c) DS3 (b)δメディド (c)DS3 0.78
Fig. 7. Confusion matrices for a cluster from each category in the MNIST Fashion dataset show the performance all 3 methods compared. フィギュア。 7. MNIST Fashionデータセットの各カテゴリからのクラスタの融合行列は、比較した3つのメソッドすべてのパフォーマンスを示している。 0.66
The Sandal class was the hardest to represent for all methods. サンダルクラスは全てのメソッドで最も表現が難しいクラスだった。 0.65
This is also quantified in Figure 6. これはまた、図6で定量化されます。 0.60
英語(論文から抽出)日本語訳スコア
(a) CRS-k10 (a)CRS-k10 0.72
(b) δ-Medoids (c) DS3 (b)δメディド (c)DS3 0.78
Fig. 8. Confusion matrices for a cluster from each category in the 20Newsgroup dataset show the performance all 3 methods compared. フィギュア。 8. 20newsgroupデータセットの各カテゴリのクラスタに対する混乱行列は、3つのメソッドすべてを比較したパフォーマンスを示している。 0.65
The confusion matrix for DS3 visualizes the results from Table 1 DS3の混乱行列は表1から結果を視覚化する 0.79
The depicted clusters were chosen for their sizes and different homogeneity, see Table 2. 表現されたクラスタはそのサイズと異なる均一性のために選択された。 0.59
Increasing k significantly reduces the percentage of dataset selected for kの増加は選択したデータセットの割合を著しく減少させる 0.68
J K L M N Cluster Size 32 108 218 44 Homogeneity 0.58 0.14 0.84 0.64 0.60 0.92 0.34 0.84 0.69 0.35 0.78 0.35 0.79 1.0 Table 2. J K L M N Cluster Size 32 108 218 44 Homogeneity 0.58 0.14 0.84 0.64 0.60 0.92 0.34 0.69 0.35 0.78 0.35 0.79 1.0 Table 2 0.65
Sizes and approximate homogeneity for each cluster from network dataset. ネットワークデータセットから各クラスタのサイズと近似均一性。 0.88
A B C D E F G H I 52 1079 2407 75 A B C D E F G H 52 1079 2407 75 0.76
42 2219 346 59 42 2219 346 59 0.85
248 49 its representation while still retaining high precision and recall values. 248 49 高い精度とリコール値を維持しながら 表現しています 0.73
The results on the network dataset are very important because it is a non-metric dataset, where only a pair-wise similarity is defined. ネットワークデータセットの結果は、ペアの類似性のみを定義する非メトリックデータセットであるため、非常に重要である。 0.83
6 Conclusion This paper proposed a new method called CRS for building representations of clusters — cluster prototypes which are small subsets of the original clusters. 6 結論 本稿では、クラスタの表現を構築するためのCRSと呼ばれる新しい手法を提案し、クラスタのプロトタイプは、元のクラスタの小さなサブセットである。 0.68
CRS leverages nearest neighbor graphs to map structure of each cluster and to identify the most important representatives that will form the cluster prototype. CRSは近隣のグラフを利用して各クラスタの構造をマッピングし、クラスタのプロトタイプを構成する最も重要な代表を識別する。 0.80
Thanks to this approach, CRS can be equally applied in both metric and nonmetric spaces. このアプローチにより、CRSは計量空間と非計量空間の両方に等しく適用できる。 0.74
The proposed method was compared to the prior art in a nearest prototype classification setup on multiple datasets from different domains. 提案手法は,異なる領域の複数のデータセットの最も近いプロトタイプ分類設定において,先行技術と比較した。 0.80
The experimental results show that the CRS method achieves superior classification quality while producing comparably compact representations of clusters. 実験の結果,CRS法はクラスタのコンパクトな表現を生成しながら,優れた分類品質が得られることがわかった。
訳抜け防止モード: 実験結果は CRS法はクラスタのコンパクトな表現を生成しながら、優れた分類品質を実現する。
0.83
英語(論文から抽出)日本語訳スコア
Fig. 9. Visualization of precision and recall of all methods in relation to percentage of cluster selected on chosen clusters from the Network dataset. フィギュア。 9. ネットワークデータセットから選択したクラスタ上で選択したクラスタの割合に関する全メソッドの精度とリコールの可視化。 0.71
References 1. Sambu Seo, Mathias Bode, and Klaus Obermayer. 参考文献 1. Sambu Seo、Mathias Bode、Klaus Obermayer。 0.69
Soft nearest prototype classifica- ソフト最寄りの試作機- 0.39
tion. IEEE Transactions on Neural Networks, 14(2):390–398, 2003. ティメント IEEE Transactions on Neural Networks, 14(2):390–398, 2003 0.57
2. F-M Schleif, Thomas Villmann, and Barbara Hammer. 2. F-Mシュレイフ、トーマス・ヴィルマン、バーバラ・ハマー。 0.72
Local metric adaptation for soft nearest prototype classification to classify proteomic data. プロテオミクスデータの分類のためのソフト最寄りのプロトタイプ分類のための局所距離適応 0.63
In International Workshop on Fuzzy Logic and Applications, pages 290–296. ファジィ論理と応用に関する国際ワークショップ、290-296頁。 0.76
Springer, 2005. 2005年、スプリンガー。 0.62
3. Alejandro Cervantes, Inés Galván, and Pedro Isasi. 3. Alejandro Cervantes、Inés Galván、Pedro Isasi。 0.75
An adaptive michigan approach pso for nearest prototype classification. 最寄りのプロトタイプ分類のための適応的ミシガンアプローチpso 0.69
In International Work-Conference on the Interplay Between Natural and Artificial Computation, pages 287–296. International Work-Conference on the Interplay between Natural and Artificial Computation, page 287–296。 0.93
Springer, 2007. 2007年、スプリンガー。 0.55
4. Alessio Martino, Alessandro Giuliani, and Antonello Rizzi. 4. Alessio Martino、Alessandro Giuliani、Antonello Rizzi。 0.77
Granular computing techniques for bioinformatics pattern recognition problems in non-metric spaces. 非計量空間におけるバイオインフォマティクスパターン認識問題に対するグラニュラー計算技術 0.75
In Computational Intelligence for Pattern Recognition, pages 53–81. Computational Intelligence for Pattern Recognition, page 53–81。 0.85
Springer, 2018. 2018年、スプリンガー。 0.51
5. Glenn C Becker. 5. Glenn C Becker 0.74
Methods and apparatus for clustering templates in non-metric 非メトリックなテンプレートのクラスタリング方法及び装置 0.85
similarity spaces, October 12 2010. 類似性空間 2010年10月12日。 0.67
US Patent 7,813,531. アメリカ特許7,813,531。 0.51
6. Martin Kopp, Martin Grill, and Jan Kohout. 6. Martin Kopp、Martin Grill、Jan Kohout。 0.77
Community-based anomaly detection. コミュニティに基づく異常検出。 0.70
In 2018 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1–6. 2018年、IEEE International Workshop on Information Forensics and Security (WIFS) 1-6ページ。 0.78
IEEE, 2018. 2018年、IEEE。 0.52
7. Walter J Scheirer, Michael J Wilber, Michael Eckmann, and Terrance E Boult. 7. Walter J Scheirer、Michael J Wilber、Michael Eckmann、Terrnce E Boult。 0.79
Good recognition is non-metric. 良い認識は計り知れない。 0.64
Pattern recognition, 47(8):2721–2731, 2014. パターン認識, 47(8):2721–2731, 2014。 0.83
8. Ehsan Elhamifar, Guillermo Sapiro, and S Shankar Sastry. 8. Ehsan Elhamifar、Guillermo Sapiro、S Shankar Sastry。 0.76
Dissimilarity-based sparse subset selection. 相似性に基づくスパースサブセットの選択。 0.44
IEEE transactions on pattern analysis and machine intelligence, 38(11):2182–2197, 2015. IEEEによるパターン解析とマシンインテリジェンスに関するトランザクション 38(11):2182–2197, 2015 0.88
英語(論文から抽出)日本語訳スコア
9. Elad Liebman, Benny Chor, and Peter Stone. 9. Elad Liebman、Benny Chor、Peter Stone。 0.74
Representative selection in nonmetric 非計量における代表的選択 0.53
datasets. Applied Artificial Intelligence, 29(8):807–838, 2015. データセット。 Applied Artificial Intelligence, 29(8):807-838, 2015 0.79
10. Isaac Triguero, Joaquín Derrac, Salvador Garcia, and Francisco Herrera. 10. Isaac Triguero、Joaquín Derrac、Salvador Garcia、Francisco Herrera。 0.77
A taxonomy and experimental study on prototype generation for nearest neighbor classification. 近縁種分類の原型生成に関する分類学的および実験的研究 0.76
IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(1):86–100, 2011. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(1):86-100, 2011 0.81
11. Shlomo Geva and Joaquin Sitte. 11. shlomo gevaとjoaquin sitte。 0.72
Adaptive nearest neighbor pattern classification. 適応最寄りのパターン分類。 0.60
IEEE Trans. IEEE Trans。 0.82
on Neural Networks, 2(0):2, 1991. ニューラルネットワークでは2(0):2, 1991。 0.77
12. Qiaobing Xie, Charles A Laszlo, and Rabab K Ward. 12. Qiaobing Xie、Charles A Laszlo、Rabab K Ward。 0.77
Vector quantization technique for nonparametric classifier design. 非パラメトリック分類器設計のためのベクトル量子化手法 0.70
IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(12):1326–1330, 1993. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(12):1326–1330, 1993 0.92
13. Salvador Garcia, Joaquin Derrac, Jose Cano, and Francisco Herrera. 13. Salvador Garcia、Joaquin Derrac、José Cano、Francisco Herrera。 0.77
Prototype selection for nearest neighbor classification: Taxonomy and empirical study. 近隣の分類のための原型選択:分類学と実証的研究 0.75
IEEE transactions on pattern analysis and machine intelligence, 34(3):417–435, 2012. IEEEによるパターン解析とマシンインテリジェンスに関するトランザクション、34(3):417–435, 2012 0.81
14. Hongxing Wang, Yoshinobu Kawahara, Chaoqun Weng, and Junsong Yuan. 14. 香港王、川原慶喜、チャオカン・ウン、順宗元。 0.68
Representative selection with structured sparsity. 構造空間による代表選択 0.54
Pattern Recognition, 63:268–278, 2017. パターン認識, 63:268-278, 2017 0.73
15. Xingxing Zhang, Zhenfeng Zhu, Yao Zhao, Dongxia Chang, and Ji Liu. 15. Xingxing Zhang, Zhenfeng Zhu, Yao Zhao, Dongxia Chang, Ji Liu 0.77
Seeing all from a few: l1-norm-induced discriminative prototype selection. l1-normによる識別的プロトタイプの選択。 0.59
IEEE transactions on neural networks and learning systems, 30(7):1954–1966, 2018. IEEEによるニューラルネットワークと学習システムのトランザクション 30(7): 1954–1966, 2018。 0.85
16. J Arturo Olvera-López, J Ariel Carrasco-Ochoa, and J Martínez-Trinidad. 16. J Arturo Olvera-López、J Ariel Carrasco-Ochoa、J Martínez-Trinidad。 0.82
Accurate and fast prototype selection based on the notion of relevant and border prototypes. 関連するプロトタイプと境界プロトタイプの概念に基づく正確かつ高速なプロトタイプ選択。 0.69
Journal of Intelligent & Fuzzy Systems, 34(5):2923–2934, 2018. Journal of Intelligent & Fuzzy Systems, 34(5):2923–2934, 2018 0.89
17. Wei Dong, Charikar Moses, and Kai Li. 17. Wei Dong、Charikar Moses、Kai Li。 0.74
Efficient k-nearest neighbor graph construction for generic similarity measures. 一般類似度尺度のための効率的なk-ネアレスト近傍グラフ構築 0.59
In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011. 第20回world wide web国際会議の議事録577-586頁、2011年。 0.74
18. Han Xiao, Kashif Rasul, and Roland Vollgraf. 18. Han Xiao, Kashif Rasul, Roland Vollgraf 0.72
Fashion-mnist: a novel image dataset fashion-mnist: 新しい画像データセット 0.76
for benchmarking machine learning algorithms, 2017. 2017年 機械学習アルゴリズムのベンチマーク 0.62
19. Janez Demšar. 19. Janez Demšar 0.72
Statistical comparisons of classifiers over multiple data sets. 複数のデータセットに対する分類器の統計的比較 0.80
The Journal of Machine Learning Research, 7(Jan):1–30, 2006. Journal of Machine Learning Research, 7 (Jan): 1–30, 2006 0.61
20. Juliet Popper Shaffer. 20. Juliet Popper Shaffer 0.73
Multiple hypothesis testing. Annual review of psychology, 複数の仮説テスト。 心理学の年鑑。 0.69
46(1):561–584, 1995. 46(1):561–584, 1995. 0.88
                               ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。