| dbo:abstract
|
- Graf nejbližšího souseda (nearest neighbor graph – NNG) pro n objektů v množině P v metrickém prostoru (např. pro množiny bodů v rovině euklidovské vzdálenosti) je orientovaný graf, kde uzly jsou spojovány hranami směřujícími od p do q, pokud q je nejbližší soused p (tj. vzdálenost od p do q je větší než od p na jiný objekt z množiny P). V mnoha diskuzích jsou směry hran ignorovány a NNG je definován jako neorientovaný graf. Nicméně nejbližší sousední vztah není symetrický, tzn. p není nutně nejbližším sousedem q. Graf k-nejbližších sousedů (k-nearest neighbor graph - k-NNG) je metoda, ve které jsou dva uzly p a q spojeny hranou, je-li vzdálenost p a q mezi K-tou nejmenší vzdáleností od p k ostatním objektům z množiny P. NNG je zvláštní případ k-NNG, konkrétně se jedná o 1-NNG. Dalším speciálním případem je (n -1)-NNG. Tato metoda se nazývá graf nejzvdálenějšího souseda (farthest neighbor graph - FNG). V teoretické diskuzi ohledně druhu v obecné poloze se často předpokládá, že zejména graf nejbližšího souseda je jedinečný pro každou množinu bodů. V implementaci těchto algoritmů je třeba mít na paměti, že to není vždy správný případ. Graf nejbližšího souseda v rovině i ve vícerozměrných prostorech najde uplatnění např. v kompresi dat, plánování pohybu a lokální analýze. Ve statistické analýze, shlukové analýze a na základě následujících cest v tomto grafu je možné použít pro rychlé hierarchické získávání dat. Graf nejbližšího souseda je také předmětem výpočetní geometrie. (cs)
- El grafo del vecino más cercano (en inglés, nearest neighbor graph o NNG) de un conjunto de objetos en un espacio métrico (generalmente, un conjunto de puntos en el plano euclídeo) es un grafo dirigido donde cada nodo representa a uno de los objetos y donde existe una arista entre cada nodo y su nodo más cercano. En muchas aplicaciones se suele ignorar la dirección de las aristas, convirtiendo el grafo dirigido en un grafo no dirigido. En cualquier caso, la relación de "vecino más cercano" no es una relación simétrica, es decir, que P sea el objeto más cercano a Q, no implica que Q sea el objeto más cercano a P. (es)
- The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from p to q whenever q is a nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself. In many uses of these graphs, the directions of the edges are ignored and the NNG is defined instead as an undirected graph. However, the nearest neighbor relation is not a symmetric one, i.e., p from the definition is not necessarily a nearest neighbor for q. In theoretical discussions of algorithms a kind of general position is often assumed, namely, the nearest (k-nearest) neighbor is unique for each object. In implementations of the algorithms it is necessary to bear in mind that this is not always the case. For situations in which it is necessary to make the nearest neighbor for each object unique, the set P may be indexed and in the case of a tie the object with, e.g., the largest index may be taken as the nearest neighbor. The k-nearest neighbor graph (k-NNG) is a graph in which two vertices p and q are connected by an edge, if the distance between p and q is among the k-th smallest distances from p to other objects from P. The NNG is a special case of the k-NNG, namely it is the 1-NNG. k-NNGs obey a separator theorem: they can be partitioned into two subgraphs of at most n(d + 1)/(d + 2) vertices each by the removal of O(k1/dn1 − 1/d) points. Another variation is the farthest neighbor graph (FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point. NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in data compression, motion planning, and facilities location. In statistical analysis, the nearest-neighbor chain algorithm based on following paths in this graph can be used to find hierarchical clusterings quickly. Nearest neighbor graphs are also a subject of computational geometry. The method can be used to induce a graph on nodes with unknown connectivity. (en)
- De nearest neighbor graph (NNG) van een verzameling punten in de Euclidische ruimte is de gerichte graaf waarin vanuit elk punt een kant vertrekt naar zijn meest nabije buur . De meest nabije buur (nearest neighbor) van een punt is het punt , met , waarvoor de afstand minimaal is. Het is mogelijk dat er meerdere punten op dezelfde minimale afstand van liggen; in dat geval kiest men als de meest nabije buur het punt met de hoogste index. De relatie " is de naaste buur van " is niet symmetrisch, vandaar dat de NNG een gerichte graaf is. (nl)
- Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P). Во многих обсуждениях направление рёбер игнорируется и ГБС определяется как обычный (неориентированный) граф. Однако отношение ближайшего соседства не является симметричным, т.е. если q является ближайшим соседом p, то p не обязательно будет ближайшим соседом q. В некоторых обсуждениях, чтобы сделать выбор ближайшего соседа единственным, множество P индексируется и когда происходит выбор ближайшего объекта, выбирается объект с наибольшим индексом. Граф k-ближайших соседей (k-ГБС) — это граф, в котором две вершины p и q связаны ребром, если расстояние между p и q находится среди k наименьших расстояний от p до других объектов в P. ГБС является частным случаем k-ГБС, а именно, это 1-ГБС. k-ГБС удовлетворяют условиям теоремы о планарном разбиении — их можно разбить на два подграфа с максимум вершинами путём удаления ) точек. Другой частный случай — (n − 1)-ГБС. Этот граф называется графом дальних соседей (ГДС). В теоретических обсуждениях алгоритмов часто предполагается некий вид общего положения, а именно, что для каждого объекта ближайший (k-ближайший) сосед единственен. При имплементации алгоритмов необходимо учитывать, что это условие не всегда выполняется. ГДС как для точек на плоскости, так и для точек в многомерных пространствах, находят приложения, например, в сжатии данных, для и размещения объектов. В статистическом анализе , основанный на путях в этом графе, может быть использовано для быстрого поиска иерархических кластеризаций. Графы ближайших соседей являются также предметом вычислительной геометрии. (ru)
- O grafo do vizinho mais próximo (citado e abreviado na literatura em inglês como NNG, de nearest neighbor graph) para um conjunto de n objetos P num espaço métrico (e.g., para um conjunto de pontos no plano com distâncias euclidianas) é um grafo direto com P sendo seu conjunto de vértices definido e com uma aresta direcionada de p a q sempre que q é um vizinho mais próximo de p (i.e., a distância de p a q não é maior que de p a qualquer outro objeto de P). (pt)
- Граф найбли́жчих сусі́дів (ГНС) для множини P, що складається з n об'єктів у метричному просторі (наприклад, для множини точок на площині з евклідовою метрикою) — орієнтований граф, вершинами якого є елементи множини P, в якому існує орієнтоване оебро з p в q, якщо q є найближчим сусідом p (тобто відстань від p до q не більша, ніж від p до будь-якого іншого об'єкта з P). У багатьох обговореннях напрямок ребер нехтують та ГНС визначають як звичайний (неорієнтований) граф. Проте відношення найближчого сусідства не є симетричним, тобто, якщо q є найближчим сусідом p, то p не обов'язково є найближчим сусідом q. У деяких обговореннях, щоб зробити вибір найближчого сусіда єдиним, множину P індексують і коли відбувається вибір найближчого об'єкта, вибирають об'єкт із найбільшим індексом. Граф k-найближчих сусідів (k-ГНС) — це граф, у якому дві вершини p і q пов'язані ребром, якщо відстань між p і q належить до k найменших відстаней від p до інших об'єктів у P. ГНС є окремим випадком k-ГНС, а саме, це 1-ГНС. k-ГНС задовольняють умовам теореми про планарне розбиття — їх можна розбити на два підграфи з максимум вершинами, видаливши ) точок. Інший окремий випадок — (n − 1)-ГНС. Цей граф називається графом далеких сусідів (ГДС). У теоретичних обговореннях алгоритмів часто передбачається певний вид загального положення, а саме, що для кожного об'єкта найближчий (k-найближчий) сусід єдиний. При імплементації алгоритмів слід ураховувати, що ця умова не завжди виконується. ГНС як для точок на площині, так і для точок у багатовимірних просторах, застосовують, наприклад, у стисканні даних, для планування рухів і розміщення об'єктів. У статистичному аналізі , заснований на шляхах у цьому графі, можна використати для швидкого пошуку ієрархічних кластеризацій. Графи найближчих сусідів є також предметом обчислювальної геометрії. (uk)
|
| rdfs:comment
|
- De nearest neighbor graph (NNG) van een verzameling punten in de Euclidische ruimte is de gerichte graaf waarin vanuit elk punt een kant vertrekt naar zijn meest nabije buur . De meest nabije buur (nearest neighbor) van een punt is het punt , met , waarvoor de afstand minimaal is. Het is mogelijk dat er meerdere punten op dezelfde minimale afstand van liggen; in dat geval kiest men als de meest nabije buur het punt met de hoogste index. De relatie " is de naaste buur van " is niet symmetrisch, vandaar dat de NNG een gerichte graaf is. (nl)
- O grafo do vizinho mais próximo (citado e abreviado na literatura em inglês como NNG, de nearest neighbor graph) para um conjunto de n objetos P num espaço métrico (e.g., para um conjunto de pontos no plano com distâncias euclidianas) é um grafo direto com P sendo seu conjunto de vértices definido e com uma aresta direcionada de p a q sempre que q é um vizinho mais próximo de p (i.e., a distância de p a q não é maior que de p a qualquer outro objeto de P). (pt)
- Graf nejbližšího souseda (nearest neighbor graph – NNG) pro n objektů v množině P v metrickém prostoru (např. pro množiny bodů v rovině euklidovské vzdálenosti) je orientovaný graf, kde uzly jsou spojovány hranami směřujícími od p do q, pokud q je nejbližší soused p (tj. vzdálenost od p do q je větší než od p na jiný objekt z množiny P). V mnoha diskuzích jsou směry hran ignorovány a NNG je definován jako neorientovaný graf. Nicméně nejbližší sousední vztah není symetrický, tzn. p není nutně nejbližším sousedem q. (cs)
- El grafo del vecino más cercano (en inglés, nearest neighbor graph o NNG) de un conjunto de objetos en un espacio métrico (generalmente, un conjunto de puntos en el plano euclídeo) es un grafo dirigido donde cada nodo representa a uno de los objetos y donde existe una arista entre cada nodo y su nodo más cercano. (es)
- The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from p to q whenever q is a nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself. Another variation is the farthest neighbor graph (FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point. The method can be used to induce a graph on nodes with unknown connectivity. (en)
- Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P). В некоторых обсуждениях, чтобы сделать выбор ближайшего соседа единственным, множество P индексируется и когда происходит выбор ближайшего объекта, выбирается объект с наибольшим индексом. (ru)
- Граф найбли́жчих сусі́дів (ГНС) для множини P, що складається з n об'єктів у метричному просторі (наприклад, для множини точок на площині з евклідовою метрикою) — орієнтований граф, вершинами якого є елементи множини P, в якому існує орієнтоване оебро з p в q, якщо q є найближчим сусідом p (тобто відстань від p до q не більша, ніж від p до будь-якого іншого об'єкта з P). У деяких обговореннях, щоб зробити вибір найближчого сусіда єдиним, множину P індексують і коли відбувається вибір найближчого об'єкта, вибирають об'єкт із найбільшим індексом. (uk)
|
