.png){kind=icon}
Return
An efficient metric combinatorial algorithm for fitting additive trees
.png){kind=icon}
PRE
AI
DOI：10.1207/s15327906mbr3302_3.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A new combinatorial algorithm for fitting additive trees to proximity data is described. This algorithm, termed the generalized triples or GT method, proceeds by examining all triples of objects x, y, u in relation to the remaining set of objects to be clustered. For a given focal object, say x, the algorithm determines whether y or u is x's nearest neighbor using estimates derived from the distances of these objects to each other and the saved sums of distances of these objects to the remaining objects in the set. The result is a basic computational loop that is approximately order(n(3)). This idea is applied in a sequential agglomerative algorithm, with all pairs of objects that are mutual nearest neighbors (based on the above estimates) being joined at each stage. A simple version of the algorithm can be proven to find the correct solution if the dissimilarities matrix D actually satisfies the additive tree metric. The algorithm also works well on errorful data (i.e. data that cannot be modeled perfectly by an additive tree). A simulation study demonstrates that the GT algorithm works as effectively as the Sattath and Tversky algorithm (Corter, 1982; Sattath & Tversky, 1977) in terms of fit of the obtained solutions, and is faster for moderate- to large-sized data sets, especially in the presence of error. A second simulation study shows that the GT algorithm obtains comparable fits to De Soete's(1983) algorithm, with large savings in computation time.
Keywords:
PROXIMITY DATA
REPRESENTATIONS
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
M
IF:
3.5
Papers:
1.8K
Citations:
9.4K
Organization
No organization information available
Cited Papers
No cited papers available