Campus Units

Industrial and Manufacturing Systems Engineering

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

7-15-2019

Journal or Book Title

Expert Systems with Applications

Volume

126

First Page

265

Last Page

276

Research Focus Area(s)

​Operations Research

DOI

10.1016/j.eswa.2019.02.022

Abstract

In most applications of data clustering the input data includes vectors describing the location of each data point, from which distances between data points can be calculated and a proximity matrix constructed. In some applications, however, the only available input is the proximity matrix, that is, the distances between each pair of data point. Several clustering algorithms can still be applied, but if the proximity matrix has missing values no standard method is directly applicable. Imputation can be done to replace missing values, but most imputation methods do not apply when only the proximity matrix is available. As a partial solution to fill this gap, we propose the Proximity Matrix Completion (PMC) algorithm. This algorithm assumes that data is missing due to one of two reasons: complete dissimilarity or incomplete observations; and imputes values accordingly. To determine which case applies the data is modeled as a graph and a set of maximum cliques in the graph is found. Overlap between cliques then determines the case and hence the method of imputation for each missing data point. This approach is motivated by an application in plant breeding, where what is needed is to cluster new experimental seed varieties into sets of varieties that interact similarly to the environment, and this application is presented as a case study in the paper. The applicability, limitations and performance of the new algorithm versus other methods of imputation are further studied by applying it to datasets derived from three well-known test datasets.

Comments

This is a manuscript of an article published as Karimzadeh, Samira, and Sigurdur Olafsson. "Data Clustering using Proximity Matrices with Missing Values." Expert Systems with Applications 126 (2019): 265-276. DOI: 10.1016/j.eswa.2019.02.022. Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Ltd.

Language

en

File Format

application/pdf

Available for download on Sunday, February 21, 2021

Published Version

Share

COinS