| dbo:abstract
|
- مسألة بحث النقطة الأقرب هي مسألة رياضية لإيجاد أقرب النقاط من مجموعة نقاط لنقطة معينة في الفضاء المتري. (ar)
- La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. La recherche de voisinage est utilisée dans de nombreux domaines, tels la reconnaissance de formes, le clustering, l'approximation de fonctions, la prédiction de séries temporelles et même les algorithmes de compression (recherche d'un groupe de données le plus proche possible du groupe de données à compresser pour minimiser l'apport d'information). C'est en particulier l'étape principale de la méthode des k plus proches voisins en apprentissage automatique. (fr)
- Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q. Donald Knuth in vol. 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a k-NN search, where we need to find the k closest points. Most commonly M is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, M is taken to be the d-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. One example is asymmetric Bregman divergence, for which the triangle inequality does not hold. (en)
- 最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。 (ja)
- 최근접 이웃 탐색(영어: nearest neighbor search)은 가장 가까운 (또는 가장 근접한) 점을 찾기 위한 최적화 문제이다. 근접 탐색(proximity search), 유사도 탐색(similarity search), 최근접 점쌍 문제(closest point search)라고도 불린다. 근사(近似)라는 개념은 보편적으로 물체와 물체가 덜 유사할수록 그 함수의 값은 커지는 상이(相異) 함수에 의해서 표현된다. 엄밀하게, 최근접 이웃 탐색 문제는 다음과 같이 정의된다: 공간 M에서의 점들로 이루어진 집합 S 가 주어졌을 때, 쿼리점 q ∈ M에 대해 S 안에서 가장 q와 가까운 점을 찾는다. 도널드 커누스는 그의 저서 《컴퓨터 프로그래밍의 예술》(1973) 제 3권에서 사람들의 거주지를 가장 가까운 우체국에 배정하는 프로그램이라는 의미에서 이를 우체국 문제라고 명명했다. 이 문제의 직접적인 일반화 문제로써는, k 개의 가장 가까운 점을 찾는 K-최근접 이웃 알고리즘이 있다. 보편적으로, M은 거리 공간이고 상이(相異)도는 대칭성을 갖고 삼각 부등식을 만족하는 거리 계측에 의해 표현된다. 이보다도 일반적으로 표현하자면, M은 d차원의 벡터 공간이고 상이도는 유클리드 거리, 맨해튼 거리 등을 사용해 계측한다. 그러나 상이함수는 임의성을 갖기 때문에, 예를 들면 대칭성을 띄지 않고 삼각 부등식을 만족하지 않는 브레그만 발산(Bregman Divergence)등을 사용하여 정의할 수 있다. (ko)
- 最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮局。 (zh)
- Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. (ru)
- Задача пошуку найближчого сусіда є задачею оптимізації, яка полягає у відшуканні у множині елементів, розташованих у багатовимірному метричному просторі, елементів, близьких до заданого, відповідно до заданої функції близькості. Формально ця задача ставиться наступним чином: надано множину точок S у просторі M та точку q ∈ M, необхідно знайти найближчу до q точку в S. Дональд Кнут в Мистецтві програмування (том 3, 1973) назвав це проблемою поштового відділення, посилаючись на застосування цієї задачі до пошуку найближчого поштового відділення. Прямим узагальненням задачі пошуку найближчого сусіда є алгоритм пошуку k-NN, який призначений для пошуку k найближчих точок. Найчастіше M є метричним простором і запроваджується функція близькості, що визначається як метрика, яка є симетричною і задовольняє нерівності трикутника. Ще загальніше, M — це d-вимірний векторний простір, в якому близькість береться як Евклідова метрика, вулична метрика або інші метрики. Однак функція близькості може бути довільною. Одним з прикладів може бути , для якої нерівність трикутника не виконується. (uk)
|
| rdfs:comment
|
- مسألة بحث النقطة الأقرب هي مسألة رياضية لإيجاد أقرب النقاط من مجموعة نقاط لنقطة معينة في الفضاء المتري. (ar)
- 最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。 (ja)
- 最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮局。 (zh)
- Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. (ru)
- Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. (en)
- La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. (fr)
- 최근접 이웃 탐색(영어: nearest neighbor search)은 가장 가까운 (또는 가장 근접한) 점을 찾기 위한 최적화 문제이다. 근접 탐색(proximity search), 유사도 탐색(similarity search), 최근접 점쌍 문제(closest point search)라고도 불린다. 근사(近似)라는 개념은 보편적으로 물체와 물체가 덜 유사할수록 그 함수의 값은 커지는 상이(相異) 함수에 의해서 표현된다. 엄밀하게, 최근접 이웃 탐색 문제는 다음과 같이 정의된다: 공간 M에서의 점들로 이루어진 집합 S 가 주어졌을 때, 쿼리점 q ∈ M에 대해 S 안에서 가장 q와 가까운 점을 찾는다. 도널드 커누스는 그의 저서 《컴퓨터 프로그래밍의 예술》(1973) 제 3권에서 사람들의 거주지를 가장 가까운 우체국에 배정하는 프로그램이라는 의미에서 이를 우체국 문제라고 명명했다. 이 문제의 직접적인 일반화 문제로써는, k 개의 가장 가까운 점을 찾는 K-최근접 이웃 알고리즘이 있다. (ko)
- Задача пошуку найближчого сусіда є задачею оптимізації, яка полягає у відшуканні у множині елементів, розташованих у багатовимірному метричному просторі, елементів, близьких до заданого, відповідно до заданої функції близькості. Формально ця задача ставиться наступним чином: надано множину точок S у просторі M та точку q ∈ M, необхідно знайти найближчу до q точку в S. Дональд Кнут в Мистецтві програмування (том 3, 1973) назвав це проблемою поштового відділення, посилаючись на застосування цієї задачі до пошуку найближчого поштового відділення. Прямим узагальненням задачі пошуку найближчого сусіда є алгоритм пошуку k-NN, який призначений для пошуку k найближчих точок. (uk)
|
