論文の概要: Finding Relevant Points for Nearest-Neighbor Classification
- arxiv url: http://arxiv.org/abs/2110.06163v1
- Date: Tue, 12 Oct 2021 16:58:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-13 16:08:59.279634
- Title: Finding Relevant Points for Nearest-Neighbor Classification
- Title（参考訳）: 最寄り-neighbor分類の関連点の探索
- Authors: David Eppstein
- Abstract要約: 最寄りの分類問題では、それぞれ既知の分類を持つ$d$次元の訓練点の集合が与えられ、他の点の未知の分類を推測するために使用される。
トレーニングセットからの離脱がこれらの推論の結果を変える場合、トレーニングポイントが関係する。
- 参考スコア（独自算出の注目度）: 0.456877715768796
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In nearest-neighbor classification problems, a set of $d$-dimensional
training points are given, each with a known classification, and are used to
infer unknown classifications of other points by using the same classification
as the nearest training point. A training point is relevant if its omission
from the training set would change the outcome of some of these inferences. We
provide a simple algorithm for thinning a training set down to its subset of
relevant points, using as subroutines algorithms for finding the minimum
spanning tree of a set of points and for finding the extreme points (convex
hull vertices) of a set of points. The time bounds for our algorithm, in any
constant dimension $d\ge 3$, improve on a previous algorithm for the same
problem by Clarkson (FOCS 1994).
- Abstract（参考訳）: 至近距離分類問題において、既知の分類を持つ1組の1組のd$-d訓練点が与えられ、最近の訓練点と同じ分類を用いて、他の点の未知の分類を推測するために使用される。
トレーニングセットからの欠落がこれらの推論の結果を変える場合、トレーニングポイントは重要となる。
関連する点のサブセットに設定されたトレーニングを細分化する簡単なアルゴリズムを提供し、各点の集合の最小スパンディングツリーを探索し、点の集合の極端点(凸包頂点)を求めるサブルーチンアルゴリズムとして使用する。
我々のアルゴリズムの時間境界は、任意の定数次元$d\ge 3$で、クラークソン (FOCS 1994) による同じ問題に対する以前のアルゴリズムを改善する。
関連論文リスト
- 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) - Reducing Nearest Neighbor Training Sets Optimally and Exactly [0.0]
最寄りの分類では、与えられた分類を持つ$mathbbRd$の点のP$のトレーニングセットが$mathbbRd$のすべての点を$mathbbRd$の点の分類に使用される
関連する点の集合が、もし$P$ が一般的な位置にあるならば、そのような最小濃度削減訓練集合であることが示される。
論文 参考訳（メタデータ） (2023-02-04T08:48:59Z) - Improved Search of Relevant Points for Nearest-Neighbor Classification [91.3755431537592]
トレーニングセットから除外された場合、トレーニングポイントが$mathbbRd$のクエリポイントの誤分類を引き起こす可能性がある場合、トレーニングポイントは関連していると言います。
出力に敏感なアルゴリズムが提案され、境界点の集合が$P$ in $O(n2 + nk2 )$ time, ここで$k$はそのような集合のサイズである。
本稿では,このアルゴリズムを,O(nk2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(n2)であることを示す。
論文 参考訳（メタデータ） (2022-03-07T18:10:27Z) - DeepBBS: Deep Best Buddies for Point Cloud Registration [55.12101890792121]
DeepBBSは、トレーニング中のポイント間の最良の相反する距離を考慮に入れた表現を学ぶための新しい方法である。
実験の結果,従来の手法と比較して性能が向上した。
論文 参考訳（メタデータ） (2021-10-06T19:00:07Z) - Quantum K-nearest neighbor classification algorithm based on Hamming
distance [3.4501155479285326]
本研究では,ハミング距離を持つ量子K-アレスト近傍分類アルゴリズムを提案する。
提案アルゴリズムは,時間的複雑さを短時間で解析することにより,2次高速化を実現することができる。
論文 参考訳（メタデータ） (2021-03-07T04:08:21Z) - Social Distancing is Good for Points too! [91.3755431537592]
点が近すぎるとFCNNの動作が悪くなることを示す。
そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。
この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
論文 参考訳（メタデータ） (2020-06-28T16:49:59Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Coresets for the Nearest-Neighbor Rule [78.15296214629433]
最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。
本稿では,最寄りの分類のためのコアセットの概念を紹介する。
そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-16T19:00:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。