An Efficient Similarity Measure for Purchase Histories Considering Hierarchical Classification of Products

Yu-Jeong Yang, Ki Yong Lee

http://doi.org/10.5626/JOK.2020.47.10.999

In an online shopping mall or offline store, the products purchased by each customer over time form a purchase history of the customer. Also, in most cases, products have a hierarchical classification that represents their subcategories. In this paper, we propose a new similarity measure for purchase histories considering not only the purchase order of products but also the hierarchical classification of products. The proposed method extends the dynamic time warping similarity that is an existing representative similarity measure for sequences, to reflect the hierarchical classification of products. Unlike the existing method, where the similarity between the elements in two sequences is only 0 or 1 depending on whether the two elements are the same or not, the proposed method can assign any real number between 0 and 1 as the similarity between the two elements considering the hierarchical classification of elements. We also propose an efficient method for computing the proposed similarity measure. The proposed computation method uses the segment tree to evaluate the similarity between the two products in a hierarchical classification tree in an efficient manner. Through various experiments based on the real data, we show that the proposed method can measure the similarity between purchase histories of products with hierarchical classification in an exceedingly effective and efficient manner.