This HTML5 document contains 175 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbpedia-sh	http://sh.dbpedia.org/resource/
dcterms	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
n33	http://www.ddj.com/architect/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n22	https://archive.today/20130222061350/http:/sswiki.tierra-aoi.net/
dbpedia-ko	http://ko.dbpedia.org/resource/
dbpedia-hu	http://hu.dbpedia.org/resource/
n23	https://global.dbpedia.org/id/
dbpedia-he	http://he.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
dbt	http://dbpedia.org/resource/Template:
dbpedia-ru	http://ru.dbpedia.org/resource/
n14	http://simsearch.yury.name/
dbpedia-uk	http://uk.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbpedia-fa	http://fa.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-ar	http://ar.dbpedia.org/resource/
owl	http://www.w3.org/2002/07/owl#
dbpedia-zh	http://zh.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
dbpedia-th	http://th.dbpedia.org/resource/
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
gold	http://purl.org/linguistics/gold/
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/

Statements

Subject Item

dbr:Nearest_neighbor_search

rdf:type

yago:YagoPermanentlyLocatedEntity yago:Activity100407535 yago:Rule105846932 yago:Abstraction100002137 yago:WikicatGeometricAlgorithms yago:WikicatApproximationAlgorithms yago:Algorithm105847438 yago:Act100030358 yago:PsychologicalFeature100023100 yago:WikicatClassificationAlgorithms dbo:Disease yago:Procedure101023820 yago:Event100029378 yago:WikicatSearchAlgorithms

rdfs:label

بحث النقطة الأقرب Recherche des plus proches voisins 最邻近搜索 Задача поиска ближайшего соседа 최근접 이웃 탐색 Пошук найближчого сусіда Nearest neighbor search 最近傍探索

rdfs:comment

Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. 最近傍探索（英: 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年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。 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. 最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮局。 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. 최근접 이웃 탐색(영어: nearest neighbor search)은 가장 가까운 (또는 가장 근접한) 점을 찾기 위한 최적화 문제이다. 근접 탐색(proximity search), 유사도 탐색(similarity search), 최근접 점쌍 문제(closest point search)라고도 불린다. 근사(近似)라는 개념은 보편적으로 물체와 물체가 덜 유사할수록 그 함수의 값은 커지는 상이(相異) 함수에 의해서 표현된다. 엄밀하게, 최근접 이웃 탐색 문제는 다음과 같이 정의된다: 공간 M에서의 점들로 이루어진 집합 S 가 주어졌을 때, 쿼리점 q ∈ M에 대해 S 안에서 가장 q와 가까운 점을 찾는다. 도널드 커누스는 그의 저서 《컴퓨터 프로그래밍의 예술》(1973) 제 3권에서 사람들의 거주지를 가장 가까운 우체국에 배정하는 프로그램이라는 의미에서 이를 우체국 문제라고 명명했다. 이 문제의 직접적인 일반화 문제로써는, k 개의 가장 가까운 점을 찾는 K-최근접 이웃 알고리즘이 있다. مسألة بحث النقطة الأقرب هي مسألة رياضية لإيجاد أقرب النقاط من مجموعة نقاط لنقطة معينة في الفضاء المتري. Задача пошуку найближчого сусіда є задачею оптимізації, яка полягає у відшуканні у множині елементів, розташованих у багатовимірному метричному просторі, елементів, близьких до заданого, відповідно до заданої функції близькості. Формально ця задача ставиться наступним чином: надано множину точок S у просторі M та точку q ∈ M, необхідно знайти найближчу до q точку в S. Дональд Кнут в Мистецтві програмування (том 3, 1973) назвав це проблемою поштового відділення, посилаючись на застосування цієї задачі до пошуку найближчого поштового відділення. Прямим узагальненням задачі пошуку найближчого сусіда є алгоритм пошуку k-NN, який призначений для пошуку k найближчих точок.

dcterms:subject

dbc:Search_algorithms dbc:Discrete_geometry dbc:Classification_algorithms dbc:Geometric_algorithms dbc:Machine_learning dbc:Data_mining dbc:Approximation_algorithms dbc:Mathematical_optimization

dbo:wikiPageID

7309022

dbo:wikiPageRevisionID

1123903963

dbo:wikiPageWikiLink

dbr:Taxicab_geometry dbr:Fixed-radius_near_neighbors dbr:R*_tree dbr:Optimization_problem dbr:Computational_geometry dbr:Pattern_matching dbr:Chemical_similarity dbr:Cluster_analysis dbr:MinHash dbr:Pattern_recognition dbc:Search_algorithms dbr:Internet_marketing dbr:Digital_signal_processing dbr:MPEG-2 dbr:Plagiarism_detection dbr:R-tree dbr:Statistical_classification dbr:Nearest-neighbor_interpolation dbr:Doubling_constant dbr:Ε-approximate_nearest_neighbor_search dbc:Discrete_geometry dbr:Statistical_distance dbc:Classification_algorithms dbr:Locality_sensitive_hashing dbr:Ball_tree dbr:Vector_Quantization dbr:Similarity_score dbr:Spatial_index dbr:Recommender_system dbr:K-nearest_neighbor_algorithm dbr:Vector_space dbr:Range_search dbc:Geometric_algorithms dbr:Closest_pair_of_points_problem dbr:DNA_sequencing dbr:Entropy_estimation dbr:Lp_space dbr:Wavelet dbr:Distance_metric dbr:Multidimensional_analysis dbr:Linear_least_squares_(mathematics) dbr:Donald_Knuth dbr:Maximum_inner-product_search dbr:Cardinality dbr:Contextual_advertising dbr:Principal_component_analysis dbr:Dimension_reduction dbr:Fourier_analysis dbr:Balanced_box-decomposition_tree dbr:The_Art_of_Computer_Programming dbr:Instance-based_learning dbr:Metric_space dbr:Collaborative_filtering dbr:Sparse_distributed_memory dbr:Triangle_inequality dbr:Predictive_analytics dbr:Semantic_Search dbr:Branch_and_bound dbr:Robotic dbr:Cover_tree dbr:Vp-tree dbc:Machine_learning dbr:Voronoi_diagram dbr:Running_time dbr:Bregman_divergence dbr:Computer_vision dbr:Behavioral_targeting dbr:Time_series dbc:Data_mining dbc:Mathematical_optimization dbr:Database dbr:Coding_theory dbr:Singular_value_decomposition dbr:Spell_checking dbr:Optical_character_recognition dbc:Approximation_algorithms dbr:Euclidean_space dbr:Data_compression dbr:Curse_of_dimensionality dbr:Similarity_learning dbr:Space_partitioning dbr:Binary_space_partitioning dbr:Content-based_image_retrieval dbr:Point_cloud_registration dbr:Metric_tree dbr:BK-tree dbr:Locality-sensitive_hashing dbr:Best_bin_first dbr:Motion_planning dbr:Nearest_neighbor_distance_ratio dbr:Euclidean_distance dbr:Expansivity_constant dbr:Neighbor_joining dbr:Decoding_methods dbr:K-d_tree

dbo:wikiPageExternalLink

n14:tutorial.html n22: n33:184401449

owl:sameAs

dbpedia-ja:最近傍探索 dbpedia-fr:Recherche_des_plus_proches_voisins dbpedia-ru:Задача_поиска_ближайшего_соседа dbpedia-he:חיפוש_שכן_קרוב dbpedia-hu:Legközelebbi_szomszéd_analízis dbpedia-zh:最邻近搜索 dbpedia-sr:Pretraživanje_najbližeg_suseda dbpedia-ar:بحث_النقطة_الأقرب dbpedia-uk:Пошук_найближчого_сусіда n23:4o5ym dbpedia-ko:최근접_이웃_탐색 freebase:m.025ytbk yago-res:Nearest_neighbor_search dbpedia-sh:Pretraživanje_najbližeg_suseda dbpedia-fa:جستجوی_نزدیکترین_همسایه dbpedia-th:การค้นหาเพื่อนบ้านใกล้สุด wikidata:Q608751

dbp:wikiPageUsesTemplate

dbt:Short_description dbt:Cite_book dbt:Cite_journal dbt:Div_col dbt:Div_col_end dbt:Commons_category dbt:Reflist dbt:Confusing

dbo:abstract

Задача пошуку найближчого сусіда є задачею оптимізації, яка полягає у відшуканні у множині елементів, розташованих у багатовимірному метричному просторі, елементів, близьких до заданого, відповідно до заданої функції близькості. Формально ця задача ставиться наступним чином: надано множину точок S у просторі M та точку q ∈ M, необхідно знайти найближчу до q точку в S. Дональд Кнут в Мистецтві програмування (том 3, 1973) назвав це проблемою поштового відділення, посилаючись на застосування цієї задачі до пошуку найближчого поштового відділення. Прямим узагальненням задачі пошуку найближчого сусіда є алгоритм пошуку k-NN, який призначений для пошуку k найближчих точок. Найчастіше M є метричним простором і запроваджується функція близькості, що визначається як метрика, яка є симетричною і задовольняє нерівності трикутника. Ще загальніше, M — це d-вимірний векторний простір, в якому близькість береться як Евклідова метрика, вулична метрика або інші метрики. Однак функція близькості може бути довільною. Одним з прикладів може бути , для якої нерівність трикутника не виконується. Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. 最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮局。 مسألة بحث النقطة الأقرب هي مسألة رياضية لإيجاد أقرب النقاط من مجموعة نقاط لنقطة معينة في الفضاء المتري. 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. 최근접 이웃 탐색(영어: 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)등을 사용하여 정의할 수 있다. 最近傍探索（英: 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年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。 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.

gold:hypernym

dbr:Problem

prov:wasDerivedFrom

wikipedia-en:Nearest_neighbor_search?oldid=1123903963&ns=0

dbo:wikiPageLength

25982

foaf:isPrimaryTopicOf

wikipedia-en:Nearest_neighbor_search