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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n10http://dbpedia.org/resource/File:
n19https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n21http://dbpedia.org/resource/En:
freebasehttp://rdf.freebase.com/ns/
n12http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Nearest_neighbor_graph
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Batch_effect
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Stack_(abstract_data_type)
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Jean-Paul_Benzécri
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Hierarchical_clustering
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Nearest-neighbor_chain_algorithm
rdf:type
yago:Information105816287 dbo:Software yago:Datum105816622 yago:Abstraction100002137 yago:WikicatDataClusteringAlgorithms yago:PsychologicalFeature100023100 yago:Cognition100023271
rdfs:label
Nearest-neighbor chain algorithm
rdfs:comment
In the theory of cluster analysis, the nearest-neighbor chain algorithm is an algorithm that can speed up several methods for agglomerative hierarchical clustering. These are methods that take a collection of points as input, and create a hierarchy of clusters of points by repeatedly merging pairs of smaller clusters to form larger clusters. The clustering methods that the nearest-neighbor chain algorithm can be used for include Ward's method, complete-linkage clustering, and single-linkage clustering; these all work by repeatedly merging the closest two clusters but use different definitions of the distance between clusters. The cluster distances for which the nearest-neighbor chain algorithm works are called reducible and are characterized by a simple inequality among certain cluster dis
foaf:depiction
n12:Hierarchical_clustering_diagram.png n12:Nearest-neighbor_chain_algorithm_animated.gif
dcterms:subject
dbc:Cluster_analysis_algorithms
dbo:wikiPageID
33068704
dbo:wikiPageRevisionID
1088104637
dbo:wikiPageWikiLink
dbr:Taxonomy_(biology) dbr:Complete-linkage_clustering dbr:Prim's_algorithm dbr:Cluster_analysis dbr:Metric_space dbr:Phylogenetic_tree n10:Hierarchical_clustering_diagram.png n10:Nearest-neighbor_chain_algorithm_animated.gif dbr:Single-linkage_clustering dbr:Disjoint_set dbr:Maximal_element dbr:Agglomerative_hierarchical_clustering dbr:Data_analysis dbr:Distance_matrix dbr:Algorithm dbr:Centroid dbr:Cardinality dbr:Jean-Paul_Benzécri dbr:Sequential_search dbr:Euclidean_space dbr:Nearest_neighbor_graph dbr:Triangle_inequality dbr:Stack_(abstract_data_type) dbr:Binary_tree dbc:Cluster_analysis_algorithms dbr:Hierarchical_clustering dbr:Quadtree dbr:Taxonomic_rank dbr:Path_(graph_theory) dbr:Closest_pair dbr:Outlier dbr:Ward's_method dbr:Data_structure dbr:Minimum_spanning_tree dbr:Priority_queue dbr:Stack_(data_structure) dbr:Greedy_algorithm n21:k-means_clustering
owl:sameAs
yago-res:Nearest-neighbor_chain_algorithm wikidata:Q17162702 n19:gao3 freebase:m.0h55x4_
dbp:wikiPageUsesTemplate
dbt:Mvar dbt:Reflist dbt:Harvtxt dbt:Short_description dbt:Good_article dbt:Math
dbo:thumbnail
n12:Hierarchical_clustering_diagram.png?width=300
dbo:abstract
In the theory of cluster analysis, the nearest-neighbor chain algorithm is an algorithm that can speed up several methods for agglomerative hierarchical clustering. These are methods that take a collection of points as input, and create a hierarchy of clusters of points by repeatedly merging pairs of smaller clusters to form larger clusters. The clustering methods that the nearest-neighbor chain algorithm can be used for include Ward's method, complete-linkage clustering, and single-linkage clustering; these all work by repeatedly merging the closest two clusters but use different definitions of the distance between clusters. The cluster distances for which the nearest-neighbor chain algorithm works are called reducible and are characterized by a simple inequality among certain cluster distances. The main idea of the algorithm is to find pairs of clusters to merge by following paths in the nearest neighbor graph of the clusters. Every such path will eventually terminate at a pair of clusters that are nearest neighbors of each other, and the algorithm chooses that pair of clusters as the pair to merge. In order to save work by re-using as much as possible of each path, the algorithm uses a stack data structure to keep track of each path that it follows. By following paths in this way, the nearest-neighbor chain algorithm merges its clusters in a different order than methods that always find and merge the closest pair of clusters. However, despite that difference, it always generates the same hierarchy of clusters. The nearest-neighbor chain algorithm constructs a clustering in time proportional to the square of the number of points to be clustered. This is also proportional to the size of its input, when the input is provided in the form of an explicit distance matrix. The algorithm uses an amount of memory proportional to the number of points, when it is used for clustering methods such as Ward's method that allow constant-time calculation of the distance between clusters. However, for some other clustering methods it uses a larger amount of memory in an auxiliary data structure with which it keeps track of the distances between pairs of clusters.
gold:hypernym
dbr:Method
prov:wasDerivedFrom
wikipedia-en:Nearest-neighbor_chain_algorithm?oldid=1088104637&ns=0
dbo:wikiPageLength
27316
foaf:isPrimaryTopicOf
wikipedia-en:Nearest-neighbor_chain_algorithm
Subject Item
dbr:List_of_statistics_articles
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Ward's_method
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
dbr:Outline_of_machine_learning
dbo:wikiPageWikiLink
dbr:Nearest-neighbor_chain_algorithm
Subject Item
wikipedia-en:Nearest-neighbor_chain_algorithm
foaf:primaryTopic
dbr:Nearest-neighbor_chain_algorithm