TY - JOUR
T1 - On comparing bills of materials
T2 - A similarity/distance measure for unordered trees
AU - Romanowski, Carol J.
AU - Nagi, Rakesh
N1 - Funding Information:
Manuscript received May 30, 2003; revised April 16, 2004. This work was supported in part by the Engineering Research Program of the Office of Basic Energy Sciences, Department of Energy and in part by the National Science Foundation under CAREER Grant DMI-9624309. This paper was recommended by Associate Editor L. Gunderson.
PY - 2005/3
Y1 - 2005/3
N2 - Many enterprise areas, such as marketing, variant design, group technology, and cellular manufacturing, require their wide variety of products to be organized into families, which are clusters of similar products. In this paper, we propose a similarity metric for finding the distance between existing products based on bills of materials (BOMs), a class of unordered trees. We show that existing editing operations for unordered trees are not consistent for BOMs, and present a similarity metric based on the symmetric difference. We also provide an polynomial time algorithm for finding the minimum weighted symmetric difference between a pair of unordered trees. The results of the pairwise comparisons are used as a distance metric for a clustering algorithm that groups the BOM trees into product families.
AB - Many enterprise areas, such as marketing, variant design, group technology, and cellular manufacturing, require their wide variety of products to be organized into families, which are clusters of similar products. In this paper, we propose a similarity metric for finding the distance between existing products based on bills of materials (BOMs), a class of unordered trees. We show that existing editing operations for unordered trees are not consistent for BOMs, and present a similarity metric based on the symmetric difference. We also provide an polynomial time algorithm for finding the minimum weighted symmetric difference between a pair of unordered trees. The results of the pairwise comparisons are used as a distance metric for a clustering algorithm that groups the BOM trees into product families.
KW - Bills of material (BOMs)
KW - Similarity measure
KW - Symmetric difference
KW - Unordered trees
UR - http://www.scopus.com/inward/record.url?scp=14644437050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=14644437050&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2005.843395
DO - 10.1109/TSMCA.2005.843395
M3 - Article
AN - SCOPUS:14644437050
SN - 1083-4427
VL - 35
SP - 249
EP - 260
JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
IS - 2
ER -