{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,10]],"date-time":"2026-08-10T20:20:43Z","timestamp":1786393243069,"version":"build-2736575974"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005366","name":"Universitetet i Oslo","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005366","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005366","name":"University of Oslo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005366","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Partial orders and directed acyclic graphs are commonly recurring data structures that arise naturally in numerous domains and applications and are used to represent ordered relations between entities in the domains. Examples are task dependencies in a project plan, transaction order in distributed ledgers and execution sequences of tasks in computer programs, just to mention a few. We study the problem of<jats:italic>order preserving hierarchical clustering<\/jats:italic>of this kind of ordered data. That is, if we have<jats:inline-formula><jats:alternatives><jats:tex-math>$$a&lt;b$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>a<\/mml:mi><mml:mo>&lt;<\/mml:mo><mml:mi>b<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>in the original data and denote their respective clusters by [<jats:italic>a<\/jats:italic>] and [<jats:italic>b<\/jats:italic>], then we shall have<jats:inline-formula><jats:alternatives><jats:tex-math>$$[a]&lt;[b]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>[<\/mml:mo><mml:mi>a<\/mml:mi><mml:mo>]<\/mml:mo><mml:mo>&lt;<\/mml:mo><mml:mo>[<\/mml:mo><mml:mi>b<\/mml:mi><mml:mo>]<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>in the produced clustering. The clustering is similarity based and uses standard linkage functions, such as single- and complete linkage, and is an extension of classical hierarchical clustering. To achieve this, we develop a novel theory that extends classical hierarchical clustering to strictly partially ordered sets. We define the output from running classical hierarchical clustering on strictly ordered data to be<jats:italic>partial dendrograms<\/jats:italic>; sub-trees of classical dendrograms with several connected components. We then construct an embedding of partial dendrograms over a set into the family of ultrametrics over the same set. An optimal hierarchical clustering is defined as the partial dendrogram corresponding to the ultrametric closest to the original dissimilarity measure, measured in the<jats:italic>p<\/jats:italic>-norm. Thus, the method is a combination of classical hierarchical clustering and ultrametric fitting. A reference implementation is employed for experiments on both synthetic random data and real world data from a database of machine parts. When compared to existing methods, the experiments show that our method excels both in cluster quality and order preservation.<\/jats:p>","DOI":"10.1007\/s10994-021-06125-0","type":"journal-article","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T19:03:32Z","timestamp":1639681412000},"page":"1851-1901","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Order preserving hierarchical agglomerative clustering"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1636-1428","authenticated-orcid":false,"given":"Daniel","family":"Bakkelund","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,12,16]]},"reference":[{"issue":"231","key":"6125_CR1","first-page":"1","volume":"17","author":"M Ackerman","year":"2016","unstructured":"Ackerman, M., & Ben-David, S. (2016). A characterization of linkage-based hierarchical clustering. Journal of Machine Learning Research, 17(231), 1\u201317.","journal-title":"Journal of Machine Learning Research"},{"key":"6125_CR2","doi-asserted-by":"publisher","DOI":"10.1201\/9781584889977","volume-title":"Constrained clustering: Advances in algorithms, theory, and applications","author":"S Basu","year":"2008","unstructured":"Basu, S., Davidson, I., & Wagstaff, K. (2008). Constrained clustering: Advances in algorithms, theory, and applications (1st ed.). Chapman & Hall\/CRC.","edition":"1"},{"key":"6125_CR3","volume-title":"Lattices and ordered algebraic structures","author":"T Blyth","year":"2005","unstructured":"Blyth, T. (2005). Lattices and ordered algebraic structures. Universitext, Springer."},{"key":"6125_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs, Cambridge Studies in Advanced Mathematics","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge Studies in Advanced Mathematics (2nd ed.). Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511814068.","edition":"2"},{"key":"6125_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","volume-title":"Recent advances in graph partitioning","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016). Recent advances in graph partitioning (pp. 117\u2013158). Cham: Springer International Publishing. https:\/\/doi.org\/10.1007\/978-3-319-49487-6_4."},{"key":"6125_CR6","first-page":"1425","volume":"11","author":"G Carlsson","year":"2010","unstructured":"Carlsson, G., & M\u00e9moli, F. (2010). Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, 11, 1425\u20131470.","journal-title":"Journal of Machine Learning Research"},{"key":"6125_CR7","unstructured":"Carlsson, G., M\u00e9moli, F., Ribeiro, A., & Segarra, S. (2014). Hierarchical quasi-clustering methods for asymmetric networks. In E. P. Xing, & T. Jebara (Eds.), Proceedings of the 31st international conference on machine learning (Vol.\u00a032, pp. 352\u2013360). PMLR, Bejing, China, Proceedings of Machine Learning Research."},{"key":"6125_CR8","unstructured":"Chierchia, G., & Perret, B. (2019). Ultrametric fitting by gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019Alch\u00e9-Buc, E. Fox, & R. Garnett (Eds.), Advances in neural information processing systems (Vol.\u00a032, pp. 3181\u20133192). Curran Associates, Inc."},{"key":"6125_CR9","doi-asserted-by":"publisher","unstructured":"Dasgupta, S. (2016). A cost function for similarity-based hierarchical clustering. In Proceedings of the forty-eighth annual ACM symposium on theory of computing (pp. 118\u2013127). Association for Computing Machinery, New York, NY, USA, STOC \u201916, https:\/\/doi.org\/10.1145\/2897518.2897527.","DOI":"10.1145\/2897518.2897527"},{"key":"6125_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/11564126_11","volume-title":"Knowledge discovery in databases: PKDD 2005","author":"I Davidson","year":"2005","unstructured":"Davidson, I., & Ravi, S. S. (2005). Agglomerative hierarchical clustering with constraints: Theoretical and empirical results. In A. M. Jorge, L. Torgo, P. Brazdil, R. Camacho, & J. Gama (Eds.), Knowledge discovery in databases: PKDD 2005 (pp. 59\u201370). Springer."},{"issue":"2","key":"6125_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01896984","volume":"4","author":"G De Soete","year":"1987","unstructured":"De Soete, G., Carroll, J. D., & DeSarbo, W. S. (1987). Least squares algorithms for constructing constrained ultrametric and additive tree representations of symmetric proximity data. Journal of Classification, 4(2), 155\u2013173. https:\/\/doi.org\/10.1007\/BF01896984.","journal-title":"Journal of Classification"},{"issue":"458","key":"6125_CR12","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1198\/016214502760047131","volume":"97","author":"C Fraley","year":"2002","unstructured":"Fraley, C., & Raftery, A. E. (2002). Model-based clustering, discriminant analysis, and density estimation. Journal of the American Statistical Association, 97(458), 611\u2013631. https:\/\/doi.org\/10.1198\/016214502760047131","journal-title":"Journal of the American Statistical Association"},{"issue":"87","key":"6125_CR13","first-page":"1","volume":"18","author":"AJ Gates","year":"2017","unstructured":"Gates, A. J., & Ahn, Y. Y. (2017). The impact of random models on clustering similarity. Journal of Machine Learning Research, 18(87), 1\u201328.","journal-title":"Journal of Machine Learning Research"},{"key":"6125_CR14","unstructured":"Ghoshdastidar, D., Perrot, M., & von Luxburg, U. (2019). Foundations of comparison-based hierarchical clustering. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019Alch\u00e9-Buc, E. Fox, R. Garnett (Eds.), Advances in neural information processing systems 32 (pp. 7456\u20137466). Curran Associates, Inc."},{"key":"6125_CR15","doi-asserted-by":"crossref","unstructured":"Gilpin, S., Nijssen, S., & Davidson, I. (2013). Formalizing hierarchical clustering as integer linear programming. In Proceedings of the twenty-seventh AAAI conference on artificial intelligence (pp. 372\u2013378). AAAI Press, AAAI\u201913.","DOI":"10.1609\/aaai.v27i1.8671"},{"key":"6125_CR16","doi-asserted-by":"publisher","unstructured":"Herrmann, J., Kho, J., U\u00e7ar, B., Kaya, K., & \u00c7ataly\u00fcrek, \u00dc. V. (2017). Acyclic partitioning of large directed acyclic graphs. In 2017 17th IEEE\/ACM international symposium on cluster, cloud and grid computing (CCGRID) (pp. 371\u2013380). https:\/\/doi.org\/10.1109\/CCGRID.2017.101.","DOI":"10.1109\/CCGRID.2017.101"},{"key":"6125_CR17","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.socnet.2015.03.002","volume":"42","author":"M Hoffman","year":"2015","unstructured":"Hoffman, M., Steinley, D., & Brusco, M. J. (2015). A note on using the adjusted rand index for link prediction in networks. Social Networks, 42, 72\u201379. https:\/\/doi.org\/10.1016\/j.socnet.2015.03.002.","journal-title":"Social Networks"},{"issue":"8","key":"6125_CR18","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1080\/00029890.2001.11919803","volume":"108","author":"JE Holly","year":"2001","unstructured":"Holly, J. E. (2001). Pictures of ultrametric spaces, the p-adic numbers, and valued fields. The American Mathematical Monthly, 108(8), 721\u2013728.","journal-title":"The American Mathematical Monthly"},{"issue":"1","key":"6125_CR19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193\u2013218.","journal-title":"Journal of Classification"},{"issue":"1","key":"6125_CR20","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.aim.2003.11.008","volume":"189","author":"B Hughes","year":"2004","unstructured":"Hughes, B. (2004). Trees and ultrametric spaces: A categorical equivalence. Advances in Mathematics, 189(1), 148\u2013191. https:\/\/doi.org\/10.1016\/j.aim.2003.11.008.","journal-title":"Advances in Mathematics"},{"key":"6125_CR21","volume-title":"Algorithms for clustering data","author":"AK Jain","year":"1988","unstructured":"Jain, A. K., & Dubes, R. C. (1988). Algorithms for clustering data. Prentice-Hall, Inc."},{"key":"6125_CR22","doi-asserted-by":"publisher","DOI":"10.1142\/7449","volume-title":"Ordinal and relational clustering","author":"MF Janowitz","year":"2010","unstructured":"Janowitz, M. F. (2010). Ordinal and relational clustering. World Scientific. https:\/\/doi.org\/10.1142\/7449."},{"key":"6125_CR23","unstructured":"Jardine, N., & Sibson, R. (1971). Mathematical Taxonomy. Wiley series in probability and mathematical statistics, Wiley."},{"key":"6125_CR24","doi-asserted-by":"crossref","unstructured":"Jeantet, I., Miklos, Z., & Gross-Amblard, D. (2020). Overlapping hierarchical clustering (OHC). In Inteligent data analysis (IDA 2020).","DOI":"10.1007\/978-3-030-44584-3_21"},{"issue":"3","key":"6125_CR25","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02289588","volume":"32","author":"SC Johnson","year":"1967","unstructured":"Johnson, S. C. (1967). Hierarchical clustering schemes. Psychometrika, 32(3), 241\u2013254. https:\/\/doi.org\/10.1007\/BF02289588.","journal-title":"Psychometrika"},{"key":"6125_CR26","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-39644-4_17","volume-title":"Discovery science","author":"T Kamishima","year":"2003","unstructured":"Kamishima, T., & Fujiki, J. (2003). Clustering orders. In G. Grieser, Y. Tanaka, & A. Yamamoto (Eds.), Discovery science (pp. 194\u2013207). Springer. https:\/\/doi.org\/10.1007\/978-3-540-39644-4_17."},{"key":"6125_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85\u2013103). Springer US. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9."},{"issue":"3","key":"6125_CR28","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/widm.30","volume":"1","author":"HP Kriegel","year":"2011","unstructured":"Kriegel, H. P., Kr\u00f6ger, P., Sander, J., & Zimek, A. (2011). Density-based clustering. WIREs Data Mining and Knowledge Discovery, 1(3), 231\u2013240. https:\/\/doi.org\/10.1002\/widm.30.","journal-title":"WIREs Data Mining and Knowledge Discovery"},{"key":"6125_CR29","unstructured":"Lassila, O., & Swick, R. R. (1999). Resource description framework (RDF) model and syntax specification. W3c recommendation, W3C."},{"key":"6125_CR30","doi-asserted-by":"publisher","unstructured":"Li, X., Wu, Y., Ester, M., Kao, B., Wang, X., & Zheng, Y. (2017). Semi-supervised clustering in attributed heterogeneous information networks. In Proceedings of the 26th international conference on world wide web, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, WWW \u201917 (pp. 1621-1629), https:\/\/doi.org\/10.1145\/3038912.3052576.","DOI":"10.1145\/3038912.3052576"},{"key":"6125_CR31","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.eswa.2016.06.012","volume":"62","author":"M \u0141uczak","year":"2016","unstructured":"\u0141uczak, M. (2016). Hierarchical clustering of time series data with parametric derivative dynamic time warping. Expert Systems with Applications, 62, 116\u2013130. https:\/\/doi.org\/10.1016\/j.eswa.2016.06.012.","journal-title":"Expert Systems with Applications"},{"key":"6125_CR32","unstructured":"Macqueen, J. (1967). Some methods for classification and analysis of multivariate observations. In In 5-th Berkeley symposium on mathematical statistics and probability (pp. 281\u2013297)."},{"issue":"11","key":"6125_CR33","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1109\/JPROC.2015.2478963","volume":"103","author":"IL Markov","year":"2015","unstructured":"Markov, I. L., Hu, J., & Kim, M. (2015). Progress and challenges in VLSI placement research. Proceedings of the IEEE, 103(11), 1985\u20132003.","journal-title":"Proceedings of the IEEE"},{"key":"6125_CR34","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ins.2017.10.021","volume":"425","author":"G Pio","year":"2018","unstructured":"Pio, G., Serafino, F., Malerba, D., & Ceci, M. (2018). Multi-type clustering and classification from heterogeneous networks. Information Sciences, 425, 107\u2013126. https:\/\/doi.org\/10.1016\/j.ins.2017.10.021.","journal-title":"Information Sciences"},{"key":"6125_CR35","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1103\/RevModPhys.58.765","volume":"58","author":"R Rammal","year":"1986","unstructured":"Rammal, R., Toulouse, G., & Virasoro, M. A. (1986). Ultrametricity for physicists. Reviews of Modern Physics, 58, 765\u2013788. https:\/\/doi.org\/10.1103\/RevModPhys.58.765.","journal-title":"Reviews of Modern Physics"},{"issue":"336","key":"6125_CR36","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1080\/01621459.1971.10482356","volume":"66","author":"WM Rand","year":"1971","unstructured":"Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336), 846\u2013850.","journal-title":"Journal of the American Statistical Association"},{"key":"6125_CR37","unstructured":"Sneath, P., & Sokal, R. (1973). Numerical taxonomy: The principles and practice of numerical classification. A Series of books in biology. W. H. Freeman."},{"issue":"95","key":"6125_CR38","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh, N. X., Epps, J., & Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11(95), 2837\u20132854.","journal-title":"Journal of Machine Learning Research"},{"issue":"301","key":"6125_CR39","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1080\/01621459.1963.10500845","volume":"58","author":"JH Ward","year":"1963","unstructured":"Ward, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301), 236\u2013244.","journal-title":"Journal of the American Statistical Association"},{"key":"6125_CR40","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00357-008-9023-7","volume":"25","author":"MJ Warrens","year":"2008","unstructured":"Warrens, M. J. (2008). On the equivalence of Cohen\u2019s Kappa and the Hubert-Arabie adjusted Rand index. Journal of Classification, 25, 177\u2013183.","journal-title":"Journal of Classification"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06125-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06125-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06125-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T22:27:13Z","timestamp":1674080833000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06125-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,16]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["6125"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06125-0","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,16]]},"assertion":[{"value":"17 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}