Learnable Weighting of Intra-Attribute Distances for Categorical Data Clustering with Nominal and Ordinal Attributes

# Learnable Weighting of Intra-Attribute Distances for Categorical Data Clustering with Nominal and Ordinal Attributes
Source: [https://arxiv.org/html/2607.05464](https://arxiv.org/html/2607.05464)
###### Abstract

The success of categorical data clustering generally much relies on the distance metric that measures the dissimilarity degree between two objects\. However, most of the existing clustering methods treat the two categorical subtypes, i\.e\. nominal and ordinal attributes, in the same way when calculating the dissimilarity without considering the relative order information of the ordinal values\. Moreover, there would exist interdependence among the nominal and ordinal attributes, which is worth exploring for indicating the dissimilarity\. This paper will therefore study the intrinsic difference and connection of nominal and ordinal attribute values from a perspective akin to the graph\. Accordingly, we propose a novel distance metric to measure the intra\-attribute distances of nominal and ordinal attributes in a unified way, meanwhile preserving the order relationship among ordinal values\. Subsequently, we propose a new clustering algorithm to make the learning of intra\-attribute distance weights and partitions of data objects into a single learning paradigm rather than two separate steps, whereby circumventing a suboptimal solution\. Experiments show the efficacy of the proposed algorithm in comparison with the existing counterparts\.

###### Index Terms:

Categorical data clustering, nominal\-and\-ordinal attribute, intra\-attribute distance, learnable weighting\.

## 1Introduction

Widespread categorical data can be easily collected from questionnaires, medical scales, scoring systems, and so on\[[1](https://arxiv.org/html/2607.05464#bib.bib1)\]\. As one of the most widely used machine learning and pattern recognition techniques, clustering that partitions data objects into homogeneous groups in unsupervised environment\[[7](https://arxiv.org/html/2607.05464#bib.bib26),[26](https://arxiv.org/html/2607.05464#bib.bib21)\]has been commonly adopted for the analysis of categorical data\[[25](https://arxiv.org/html/2607.05464#bib.bib5),[56](https://arxiv.org/html/2607.05464#bib.bib11)\]\. In order to better discover homogeneous clusters, weighting attributes according to their importance to the clustering task\[[57](https://arxiv.org/html/2607.05464#bib.bib12)\]is adopted by many existing clustering algorithms\[[20](https://arxiv.org/html/2607.05464#bib.bib31),[9](https://arxiv.org/html/2607.05464#bib.bib30),[32](https://arxiv.org/html/2607.05464#bib.bib32),[6](https://arxiv.org/html/2607.05464#bib.bib33),[28](https://arxiv.org/html/2607.05464#bib.bib36)\]\. Since weighting an attribute is equivalent to uniformly weighting all the intra\-attribute distances measured on this attribute, these algorithms are actually based on the hypothesis that all the intra\-attribute distances are well defined, which is reasonable for numerical data with well\-defined distance measure\[[48](https://arxiv.org/html/2607.05464#bib.bib20)\]\. However, for categorical data whose distance measure is generally not well\-defined, uniformly weighting the intra\-attribute distances is surely unreasonable\[[12](https://arxiv.org/html/2607.05464#bib.bib10)\]\. To solve this problem, most existing methods focus on exploring appropriate distance measures\[[8](https://arxiv.org/html/2607.05464#bib.bib6),[4](https://arxiv.org/html/2607.05464#bib.bib7)\]and attribute weighting mechanisms\[[28](https://arxiv.org/html/2607.05464#bib.bib36)\]\.

Successful attempts in exploring appropriate distance measures include Lin’s\[[41](https://arxiv.org/html/2607.05464#bib.bib40)\]similarity measure, coupled\[[29](https://arxiv.org/html/2607.05464#bib.bib76)\]similarity metric, association\-based\[[35](https://arxiv.org/html/2607.05464#bib.bib41)\], Ahmad’s\[[3](https://arxiv.org/html/2607.05464#bib.bib42)\], context\-based\[[23](https://arxiv.org/html/2607.05464#bib.bib43),[24](https://arxiv.org/html/2607.05464#bib.bib44)\], and Jia’s\[[27](https://arxiv.org/html/2607.05464#bib.bib45)\]distance metrics\. The above\-mentioned measures define intra\-attribute distances according to the possible value statistics, e\.g\., the occurrence frequencies and conditional occurrence probabilities\. Lin’s measure computes the cumulative entropy of a range of ordered possible values \(i\.e\., the adjacent possible values \{good, neutral, bad\} of an ordinal attribute with possible values \{very\-good, good, neutral, bad, very\-bad\}\) to indicate the corresponding intra\-attribute distance \(i\.e\., the distance between good and bad\) with preserving the order relationship, which is suitable for the distance measurement of ordinal data\. The others define intra\-attribute distances according to the context information reflected by conditional probability distributions between interdependent attributes, which works well for nominal data\. In recent years, more powerful representation\-based methods including structure\-based\[[49](https://arxiv.org/html/2607.05464#bib.bib75)\], coupled\[[30](https://arxiv.org/html/2607.05464#bib.bib72),[31](https://arxiv.org/html/2607.05464#bib.bib77)\], and heterogeneous coupling\[[63](https://arxiv.org/html/2607.05464#bib.bib78)\]representations, have been proposed to represent categorical data by embedding more informative and complex relationships existing in the level of values, attributes, and objects, so as to achieve a more reasonable distance measurement\. Unfortunately, they still work well for nominal data only\.

In summary, all the above mentioned measures are proposed without considering a very common situation that real categorical data are usually composed of a mixture of nominal and ordinal attributes\[[2](https://arxiv.org/html/2607.05464#bib.bib2),[33](https://arxiv.org/html/2607.05464#bib.bib3)\]\. As the fragment of medical scale data set shown in Table[I](https://arxiv.org/html/2607.05464#S1.T1), the values of ordinal Attribute 1 stand for the degrees of lymph enlargement, the values of nominal Attribute 2 stand for the special form of lymph, and the values of the Class attribute indicate the diagnosis results, which are the desired true cluster labels in cluster analysis\.

TABLE I:Fragment of Lymphography data set\.No\.Attribute 1Attribute 2Class\(enlarge\)\(form\)\(diagnosis\)1↑\\uparrownon\-specialnormal2↑\\uparrowvesiclesfibrosis3↑↑\\uparrow\\uparrowvesiclesfibrosis4↑⁣↑⁣↑\\uparrow\\uparrow\\uparrowchalicesmetastases5↑⁣↑⁣↑\\uparrow\\uparrow\\uparrowchalicesmalign6↑⁣↑⁣↑⁣↑\\uparrow\\uparrow\\uparrow\\uparrowvesiclesmalignIn medicine, it is generally believed that the severity of fibrosis, metastasis, and malign increases in sequence\. Apparently, if we treat the ordered values of Attribute 1 as nominal values, information provided by the monotonic relationship between the values of Attribute 1 and the true class labels will be lost\[[19](https://arxiv.org/html/2607.05464#bib.bib62)\], which will directly affect the clustering accuracy\. Moreover, there also exists an awkward gap between the cluster information provided by nominal and ordinal attributes, because the values of an ordinal attribute contain the relative ordering information, but the values of a nominal one do not\. Hence, to avoid the loss of important information, entropy\-based distance metrics\[[59](https://arxiv.org/html/2607.05464#bib.bib47),[62](https://arxiv.org/html/2607.05464#bib.bib48)\]have been proposed to quantify intra\-attribute distances of nominal and ordinal attributes as information entropy\[[46](https://arxiv.org/html/2607.05464#bib.bib13)\]in a unified way\. However, they have not established an essential connection between nominal and ordinal attributes for data clustering\.

As for attribute weighting mechanism, most efforts have tried to weight attributes for each cluster, which is called subspace clustering\. Typical subspace approaches include\[[20](https://arxiv.org/html/2607.05464#bib.bib31),[9](https://arxiv.org/html/2607.05464#bib.bib30),[6](https://arxiv.org/html/2607.05464#bib.bib33),[28](https://arxiv.org/html/2607.05464#bib.bib36)\], which learn the different weight combinations of attributes for each cluster to explore more appropriate subspaces for gathering homogeneous data objects\. Nevertheless, they uniformly weight all intra\-attribute distances measured on the same attribute, which still makes these approaches incompetent in adapting the contributions of different intra\-attribute distances to search for more appropriate clustering results\. Most recently, a distance weighting\-based clustering algorithm\[[61](https://arxiv.org/html/2607.05464#bib.bib37)\]has been proposed to learn the weights of intra\-attribute distances automatically during clustering\. This algorithm has remarkable performance on ordinal data sets, but it relies on the order relationship among attribute values for learning the distance weights, which makes it applicable to ordinal data only\. To the best of our knowledge, clustering algorithm that can learn the weights of intra\-attribute distances for categorical data with nominal and ordinal attributes has yet to be proposed\.

In this paper, we will propose a new clustering method composed of a novel distance definition and an automatic distance weighting mechanism for any\-type categorical data clustering, i\.e\., clustering data composed of any combination of nominal and ordinal attributes\. Specifically, we study the intrinsic difference and connection of nominal and ordinal attributes, and convert each possible value of nominal attributes, e\.g\., “vesicles” of Attribute 2 as shown in Table[I](https://arxiv.org/html/2607.05464#S1.T1), into a Boolean attribute with two possible values “vesicles” and “not vesicles”\. Such Boolean attribute is a special case of ordinal attribute, i\.e\., an ordinal attribute with two extreme degrees “vesicles” and “not vesicles”\. Thus, the heterogeneous clustering information provided by nominal and ordinal attributes becomes homogeneous information provided by ordinal attributes\. On this basis, the information provided by interdependent attributes in three cases \(i\.e\., \(i\) both attributes are nominal, \(ii\) both attributes are ordinal, and \(iii\) one is nominal and the other is ordinal\) is utilized to measure intra\-attribute distances of nominal and ordinal attributes in a unified way\. Since the defined distances are not connected to a certain clustering task, we also propose a novel intra\-attribute distance weighting mechanism to learn the distance weights iteratively based on the present data partition result to search for better clustering results\. The proposed distance definition and weighting mechanism are complementary to each other in clustering\. It turns out that the clustering algorithm utilizing them is competent for the cluster analysis of any\-type categorical data\. The main contributions of this paper are summarized below:

- •Inherent connection of nominal and ordinal attributes is studied, and a novel measure suitable for intra\-attribute distance measurement of any\-type categorical data clustering is proposed accordingly\.
- •An intra\-attribute distance weighting mechanism that iteratively updates the distance weights to search for better data partitions, if any, is designed to make the measured intra\-attribute distances learnable\.
- •A new categorical data clustering algorithm is presented by utilizing the learnable distance measure\. This algorithm is parameter free and has superior clustering performance on any\-type categorical data\.

The remainder of this paper is organized as follows\. Section[2](https://arxiv.org/html/2607.05464#S2)reviews the related works\. Section[3](https://arxiv.org/html/2607.05464#S3)formulates the research problems\. A design of homogeneous distance metric is proposed in Section[4](https://arxiv.org/html/2607.05464#S4)\. Then, Section[5](https://arxiv.org/html/2607.05464#S5)introduces a new clustering algorithm with the novel distance weighting mechanism as the core\. Experimental results are given in Section[6](https://arxiv.org/html/2607.05464#S6)\. Finally, we draw a conclusion in Section[7](https://arxiv.org/html/2607.05464#S7)\.

## 2Related Work

This section makes an overview of the existing related works on categorical data clustering\.

### 2\.1Distance Measure

The distance measures for categorical data clustering can be generally categorized as the direct, context\-based, and representation\-based ones\. The simplest direct measure\[[5](https://arxiv.org/html/2607.05464#bib.bib39)\]directly assigns distances 0 and 1 to identical and different intra\-attribute values, respectively\. The other direct measures\[[41](https://arxiv.org/html/2607.05464#bib.bib40),[60](https://arxiv.org/html/2607.05464#bib.bib46),[59](https://arxiv.org/html/2607.05464#bib.bib47)\]compute the intra\-attribute distance between two possible values according to their occurrence frequencies\. Direct measures are easy to use and have demonstrated great computational efficiency because their computation does not involve parameter selection, context information extraction, iterative learning, etc\. However, since the valuable information provided by the correlated attributes is totally ignored, intra\-attribute distances defined by them are not always reasonable in indicating the real dissimilarity degrees\.

In contrast, the context\-based measures\[[29](https://arxiv.org/html/2607.05464#bib.bib76),[35](https://arxiv.org/html/2607.05464#bib.bib41),[3](https://arxiv.org/html/2607.05464#bib.bib42),[23](https://arxiv.org/html/2607.05464#bib.bib43),[24](https://arxiv.org/html/2607.05464#bib.bib44),[27](https://arxiv.org/html/2607.05464#bib.bib45),[62](https://arxiv.org/html/2607.05464#bib.bib48)\]compute the distance between two intra\-attribute values based on the context information, i\.e\., the statistical information provided by the other attributes that are correlated with the target one\. In general, these measures outperform the direct ones, but their performance dependents more on the interdependence of attributes\. For the data composed of independent attributes, some indirect measures\[[35](https://arxiv.org/html/2607.05464#bib.bib41),[3](https://arxiv.org/html/2607.05464#bib.bib42),[23](https://arxiv.org/html/2607.05464#bib.bib43),[24](https://arxiv.org/html/2607.05464#bib.bib44)\]that are based on the sole information provided by the interdependent attributes would even fail for distance measurement\. Among all the above\-mentioned indirect and context\-based measures, the two measures\[[59](https://arxiv.org/html/2607.05464#bib.bib47),[62](https://arxiv.org/html/2607.05464#bib.bib48)\]that unify the distance concept of nominal and ordinal attributes as the information divergence to avoid information loss are suitable for any\-type categorical data clustering\. Nevertheless, they only provide scale\-level distance unification, but have yet to consider the intrinsic connection between nominal and ordinal attributes\.

The representation\-based distance measures encode categorical values into numerical ones, and then the advanced distance measures and clustering algorithms proposed for numerical data can be utilized\. In many practical application scenarios, the encoding is performed by domain experts, which makes the performance sensitive to the prior knowledge\. Further, for large\-scale, high\-dimensional, and multi\-variate categorical data, the encoding process is a laborious and non\-trivial task\. A commonly adopted way to circumvent these issues is to simply encode each possible value of nominal attributes into a binary\-valued numerical attribute and the ordered possible values of each ordinal attribute into consecutive integers, which is called simple coding\. It turns out that simple coding is applicable to any\-type categorical data\. Nevertheless, since it ignores the original statistical information of possible values, and it assigns the identical distance to different possible value pairs, empirical studies in\[[61](https://arxiv.org/html/2607.05464#bib.bib37)\]have shown that its performance is generally worse than the measures specially designed for categorical data\. Recently, representation learning methods\[[49](https://arxiv.org/html/2607.05464#bib.bib75),[31](https://arxiv.org/html/2607.05464#bib.bib77),[63](https://arxiv.org/html/2607.05464#bib.bib78)\]have been proposed for automatically encoding categorical data in unsupervised environment\. The one called SBC\[[49](https://arxiv.org/html/2607.05464#bib.bib75)\]reconstructs the original data set according to the inter\-object dissimilarities\. CDE in\[[31](https://arxiv.org/html/2607.05464#bib.bib77)\]encodes the original data set by performingkk\-means clustering and PCA on intra\- and inter\-attribute couplings\. The newly proposed UNTIE\[[63](https://arxiv.org/html/2607.05464#bib.bib78)\]represents data set by using more types of couplings learned in multiple kernel spaces, and achieves superior clustering performance\. However, all the above\-mentioned representation learning methods are actually designed for nominal data only, and their performance somewhat depends on the non\-trivial selection of parameters or kernel functions\.

### 2\.2Clustering Algorithm

From the perspective of attribute weighting, the existing categorical data clustering algorithms can be roughly categorized as the non\-attribute\-weighting and attribute\-weighting ones, respectively\. As a non\-attribute\-weighting algorithm, the conventionalkk\-modes\[[22](https://arxiv.org/html/2607.05464#bib.bib27)\]adopts Hamming distance\[[5](https://arxiv.org/html/2607.05464#bib.bib39)\]as a distance measure to compute the distance between data objects and thekkmodes\. Based on the object\-mode distances, it iteratively searches for better partitions of data set\. Furthermore, some of its variants also focus on improving its robustness and scalability\[[21](https://arxiv.org/html/2607.05464#bib.bib28)\]\[[10](https://arxiv.org/html/2607.05464#bib.bib34)\]\. In addition, clustering algorithm adopting entropy as a measure\[[40](https://arxiv.org/html/2607.05464#bib.bib29)\]has been proposed in the literature\. It computes the entropy value of the present partition after moving an object into a cluster, and performs cluster analysis by searching for the partition with the minimum entropy value\[[44](https://arxiv.org/html/2607.05464#bib.bib14)\]\. In general, all the above\-mentioned algorithms assume that the attributes are of identical importance for clustering tasks, which is, however, not always true in practice\.

In the literature, an attribute weighting\-based categorical data clustering algorithm\[[20](https://arxiv.org/html/2607.05464#bib.bib31)\]has been proposed provided that the attributes are of different importance\. It assigns different weights to the attributes according to their contributions in forming more compact clusters\. That is, if the total distance between data objects and their clusters measured on a certain attribute is low, it indicates that this attribute contributes more than the others in forming the clusters with similar objects\. Subsequently, a higher weight is thus assigned to this attribute in the next iteration to search for more compact clusters\. Nevertheless, this weighting mechanism finds only a certain attributes’ subset that is important to a certain subset of clusters, which is evidently incompetent in a more complex case\. Therefore, subspace clustering algorithms\[[9](https://arxiv.org/html/2607.05464#bib.bib30),[40](https://arxiv.org/html/2607.05464#bib.bib29),[6](https://arxiv.org/html/2607.05464#bib.bib33),[28](https://arxiv.org/html/2607.05464#bib.bib36)\]that weight each attribute according to its contribution in forming each certain cluster have been proposed\.

In general, weighting an attribute is equivalent to uniformly weighting all the distances measured on it\. Thus, all the above\-mentioned attribute weighting\-based algorithms actually assume that the distance measure can accurately indicate the intra\-attribute distances\. If the adopted distance measure is not appropriately defined, uniformly weighting the intra\-attribute distances measured by them will just bring more irrationality into the clustering process\. Therefore, the most recently proposed clustering algorithm\[[61](https://arxiv.org/html/2607.05464#bib.bib37)\]addresses this issue by iteratively weighting the importance of intra\-attribute distances according to the present partition to search for more appropriate clustering results of the data set\. Unfortunately, distance weighting of this algorithm relies on the order relationship among intra\-attribute values, which makes it only applicable to the categorical data sets composed of ordinal attributes\.

## 3Problem Statement

We formulate the problem of distance weighting\-based clustering of categorical data in this section\. Table[II](https://arxiv.org/html/2607.05464#S3.T2)lists the styles of notations used in this paper\.

TABLE II:Style of notations and explanation of symbols\.Notation \(example\)StyleAttribute index \(e\.g\.ArA^\{r\}\)SuperscriptValue note \(e\.g\.d\(ord\)d^\{\(\\text\{ord\}\)\}\)Superscript with parenthesesFunction \(e\.g\.dist​\(⋅,⋅\)\\text\{dist\}\(\\cdot,\\cdot\)\)ParenthesesSpace \(e\.g\.ℛ0\+\\mathcal\{R\}\_\{0\}^\{\+\}\)Uppercase, calligraphic fontVector \(e\.g\.plr\\textbf\{p\}\_\{l\}^\{r\}\)Lowercase, bold fontMatrix \(e\.g\.Q\)Uppercase, bold fontSymbol \(example\)Explanation of example∅\\emptyset\(e\.g\.A\(ord\)=∅A^\{\\text\{\(ord\)\}\}=\\emptyset\)A\(ord\)A^\{\\text\{\(ord\)\}\}is an empty set⊤\\top\(e\.g\.\[xi1,xi2,…,xid\]⊤\[x\_\{i\}^\{1\},x\_\{i\}^\{2\},\.\.\.,x\_\{i\}^\{d\}\]^\{\\top\}\)Transpose of\[xi1,xi2,…,xid\]\[x\_\{i\}^\{1\},x\_\{i\}^\{2\},\.\.\.,x\_\{i\}^\{d\}\]≻\\succ\(e\.g\.o1r≻o2ro^\{r\}\_\{1\}\\succ o^\{r\}\_\{2\}\)o1ro^\{r\}\_\{1\}ranks higher thano2ro^\{r\}\_\{2\}¬\\neg\(e\.g\.¬ogs\\neg o^\{s\}\_\{g\}\)AsA^\{s\}’s possible values excludingogso^\{s\}\_\{g\}A categorical data setSScan be represented as a tupleS=<X,A,O\>S=<X,A,O\>, whereX=\{xi\|i∈NX\}X=\\\{\\textbf\{x\}\_\{i\}\|i\\in N\_\{X\}\\\}is the object set withnnelements, andNX=\{1,2,…,n\}N\_\{X\}=\\\{1,2,\.\.\.,n\\\}is the index set ofXX\. For attribute setAAcomposed ofddattributes, we assume that the formerd\(ord\)d^\{\(\\text\{ord\}\)\}attributes are ordinal and the latterd\(nom\)d^\{\(\\text\{nom\}\)\}attributes are nominal for convenience without loss of generality, and we haved\(ord\)\+d\(nom\)=dd^\{\(\\text\{ord\}\)\}\+d^\{\(\\text\{nom\}\)\}=d\. Formally,A\(ord\)=\{Ar\|r∈NA\(ord\)\}A^\{\(\\text\{ord\}\)\}=\\\{A^\{r\}\|r\\in N\_\{A\}^\{\(\\text\{ord\}\)\}\\\}is the ordinal attribute set,A\(nom\)=\{As\|s∈NA\(nom\)\}A^\{\(\\text\{nom\}\)\}=\\\{A^\{s\}\|s\\in N\_\{A\}^\{\(\\text\{nom\}\)\}\\\}is the nominal attribute set,NA\(ord\)=\{1,2,…,d\(ord\)\}N\_\{A\}^\{\(\\text\{ord\}\)\}=\\\{1,2,\.\.\.,d^\{\(\\text\{ord\}\)\}\\\}andNA\(nom\)=\{d\(ord\)\+1,d\(ord\)\+2,…,d\}N\_\{A\}^\{\(\\text\{nom\}\)\}=\\\{d^\{\(\\text\{ord\}\)\}\+1,d^\{\(\\text\{ord\}\)\}\+2,\.\.\.,d\\\}are the index sets ofA\(ord\)A^\{\(\\text\{ord\}\)\}andA\(nom\)A^\{\(\\text\{nom\}\)\}, respectively\.A=A\(ord\)∪A\(nom\)A=A^\{\(\\text\{ord\}\)\}\\cup A^\{\(\\text\{nom\}\)\}is the complete attribute set, andNA=NA\(ord\)∪NA\(nom\)N\_\{A\}=N\_\{A\}^\{\(\\text\{ord\}\)\}\\cup N\_\{A\}^\{\(\\text\{nom\}\)\}is the complete index set ofAA\. Accordingly, three types of categorical data can be distinguished by:

datatype​\(S\)=\{mixed,A\(ord\)≠∅,A\(nom\)≠∅ordinal,A\(ord\)≠∅,A\(nom\)=∅nominal,A\(ord\)=∅,A\(nom\)≠∅\.\\text\{datatype\}\(S\)=\\left\\\{\\begin\{array\}\[\]\{lll\}\\text\{mixed\},&A^\{\(\\text\{ord\}\)\}\\neq\\emptyset,\\ \\ A^\{\(\\text\{nom\}\)\}\\neq\\emptyset\\\\ \\text\{ordinal\},&A^\{\(\\text\{ord\}\)\}\\neq\\emptyset,\\ \\ A^\{\(\\text\{nom\}\)\}=\\emptyset\\\\ \\text\{nominal\},&A^\{\(\\text\{ord\}\)\}=\\emptyset,\\ \\ A^\{\(\\text\{nom\}\)\}\\neq\\emptyset\.\\end\{array\}\\right\.

\(1\)Hereinafter, a categorical data set composed of a mixture of ordinal and nominal attributes, pure ordinal attributes, and pure nominal attributes is called mixed, ordinal, and nominal data set, respectively\.Or=\{omr\|m∈NOr\}O^\{r\}=\\\{o\_\{m\}^\{r\}\|m\\in N\_\{O\}^\{r\}\\\}is the set ofvrv^\{r\}possible values of attributeArA^\{r\}, andNOr=\{1,2,…,vr\}N\_\{O\}^\{r\}=\\\{1,2,\.\.\.,v^\{r\}\\\}is the index set ofArA^\{r\}’s possible values\. Theiith object ofXXis represented asxi=\[xi1,xi2,…,xid\]⊤\\textbf\{x\}\_\{i\}=\[x\_\{i\}^\{1\},x\_\{i\}^\{2\},\.\.\.,x\_\{i\}^\{d\}\]^\{\\top\}withxir∈Orx\_\{i\}^\{r\}\\in O^\{r\},r∈NAr\\in N\_\{A\}\. IfArA^\{r\}is an ordinal attribute \(i\.e\.r≤d\(ord\)r\\leq d^\{\(\\text\{ord\}\)\}\), its possible values satisfyo1r≻o2r≻…≻ovrro\_\{1\}^\{r\}\\succ o\_\{2\}^\{r\}\\succ\.\.\.\\succ o\_\{v^\{r\}\}^\{r\}where the symbol “≻\\succ” indicates that the values on its left are rank higher than the values on its right\.

In crisp partitional clustering task,XXis partitioned intokkclusters, which can be represented as a cluster setC=\{Cl\|l∈NC\}C=\\\{C\_\{l\}\|l\\in N\_\{C\}\\\}withNC=\{1,2,…,k\}N\_\{C\}=\\\{1,2,\.\.\.,k\\\}\. Accordingly,XXcan be represented as a collection ofkkdisjoint subsetsX=⋃l=1kXClX=\\bigcup\_\{l=1\}^\{k\}X\_\{C\_\{l\}\}whereXClX\_\{C\_\{l\}\}is the object set corresponding to thellth cluster\. Thekkclusters are represented by their corresponding statistical informationP=\{Pl\|l∈NC\}P=\\\{P\_\{l\}\|l\\in N\_\{C\}\\\}wherePl=\{plr\|r∈NA\}P\_\{l\}=\\\{\\textbf\{p\}\_\{l\}^\{r\}\|r\\in N\_\{A\}\\\}is the statistical information ofClC\_\{l\}andplr=\[pl​1r,pl​2r,…,pl​vrr\]⊤\\textbf\{p\}\_\{l\}^\{r\}=\[p\_\{l1\}^\{r\},p\_\{l2\}^\{r\},\.\.\.,p\_\{lv^\{r\}\}^\{r\}\]^\{\\top\}is the probability distribution of therrth values of the objects inClC\_\{l\}\. Values ofPPare dependent onQ, which is ann×kn\\times kmatrix indicating the partition ofXX\. The\(i,l\)\(i,l\)th entry ofQis denoted asqi​lq\_\{il\}\. Ifxi\\textbf\{x\}\_\{i\}belongs toClC\_\{l\}, we haveqi​l=1q\_\{il\}=1, otherwise,qi​l=0q\_\{il\}=0\. To learn the importance of intra\-attribute distances, we solve the clustering problem in a distance weighting framework\. The weights of intra\-attribute distances are denoted as a set of matricesW=\{Wr\|r∈NA\}W=\\\{\\textbf\{W\}^\{r\}\|r\\in N\_\{A\}\\\}whereWr\\textbf\{W\}^\{r\}is avr×vrv^\{r\}\\times v^\{r\}symmetric matrix storing the weights of intra\-attribute distances ofArA^\{r\}\. The\(m,h\)\(m,h\)th entry ofWr\\textbf\{W\}^\{r\}is denoted aswm​hrw\_\{mh\}^\{r\}, which represents the weight of the distance between possible valuesomro\_\{m\}^\{r\}andohro\_\{h\}^\{r\}\. The clustering problem can be formulated as minimizing the objective function:

Z​\(Q,P,W\)=∑i=1n∑l=1kqi​l​dist​\(xi,Cl\)Z\(\\textbf\{Q\},P,W\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{l=1\}^\{k\}q\_\{il\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)\(2\)s\.t\.\{∑l=1kqi​l=1,qi​l∈\{0,1\},i∈NX,∑r=1d∑m=1vr−1∑h=m\+1vrwm​hr=1,wm​hr∈ℛ0\+\.s\.t\.\\ \\left\\\{\\begin\{array\}\[\]\{ll\}\\sum\_\{l=1\}^\{k\}q\_\{il\}=1,\\ \\ q\_\{il\}\\in\\\{0,1\\\},&i\\in N\_\{X\},\\\\ \\sum\_\{r=1\}^\{d\}\\sum\_\{m=1\}^\{v^\{r\}\-1\}\\sum\_\{h=m\+1\}^\{v^\{r\}\}w^\{r\}\_\{mh\}=1,&w\_\{mh\}^\{r\}\\in\\mathcal\{R\}^\{\+\}\_\{0\}\.\\\\ \\end\{array\}\\right\.
The object\-cluster distancedist​\(xi,Cl\)\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)is defined as

dist​\(xi,Cl\)=∑r=1ddistr​\(xi,Cl\),\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)=\\sum\_\{r=1\}^\{d\}\\text\{dist\}^\{r\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\),\(3\)anddistr​\(xi,Cl\)\\text\{dist\}^\{r\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)is the object\-cluster distance measured on attributeArA^\{r\}\. Ifxir=omrx^\{r\}\_\{i\}=o^\{r\}\_\{m\},distr​\(xi,Cl\)\\text\{dist\}^\{r\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)can be written as

distr​\(xi,Cl\)=∑h=1vrwm​hr​distr​\(omr,ohr\)​pl​hr,\\text\{dist\}^\{r\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)=\\sum\_\{h=1\}^\{v^\{r\}\}w^\{r\}\_\{mh\}\\text\{dist\}^\{r\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)p^\{r\}\_\{lh\},\(4\)and the intra\-attribute distancedistr​\(omr,ohr\)\\text\{dist\}^\{r\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)is defined as

distr​\(omr,ohr\)=1d​∑s=1ddistr​s​\(omr,ohr\)\\text\{dist\}^\{r\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)=\\frac\{1\}\{d\}\\sum\_\{s=1\}^\{d\}\\text\{dist\}^\{rs\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)\(5\)where the superscript “r​srs” ofdistr​s​\(omr,ohr\)\\text\{dist\}^\{rs\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)indicates that this is the intra\-attribute distance betweenArA^\{r\}’s possible values with respect toAsA^\{s\}\. We define distance in the form of Eq\. \([5](https://arxiv.org/html/2607.05464#S3.E5)\) in order to exploit context information provided by interdependent attributes for distance measurement as most categorical data distance measures do\[[35](https://arxiv.org/html/2607.05464#bib.bib41),[3](https://arxiv.org/html/2607.05464#bib.bib42),[24](https://arxiv.org/html/2607.05464#bib.bib44),[27](https://arxiv.org/html/2607.05464#bib.bib45),[29](https://arxiv.org/html/2607.05464#bib.bib76),[62](https://arxiv.org/html/2607.05464#bib.bib48)\]\. The exact definition ofdistr​s​\(omr,ohr\)\\text\{dist\}^\{rs\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)will be given in Section[4\.3](https://arxiv.org/html/2607.05464#S4.SS3)\.

Similar to most existingkk\-modes\-type algorithms, the minimization problem of Eq\. \([2](https://arxiv.org/html/2607.05464#S3.E2)\) can be solved by iteratively computing one variable and fixing the others\. Since the values ofPPare completely dependent on the values ofQ, we can iteratively solve the following two problems:

- •P\. 1: FixW=W^W=\\hat\{W\}andP=P^P=\\hat\{P\}, solve the reduced problemZ​\(Q,P^,W^\)Z\(\\textbf\{Q\},\\hat\{P\},\\hat\{W\}\), updatePPaccording toQ;
- •P\. 2: FixQ=Q^\\textbf\{Q\}=\\hat\{\\textbf\{Q\}\}andP=P^P=\\hat\{P\}, solve the reduced problemZ​\(Q^,P^,W\)Z\(\\hat\{\\textbf\{Q\}\},\\hat\{P\},W\)\.

## 4Homogeneous Distance Measurement

For cluster analysis, the adopted distance measure usually dominates clustering performance\. In this section, we study the differences and commonalities of ordinal and nominal attributes, and then propose a homogeneous intra\-attribute distance definition for them\.

### 4\.1Attribute Structure

![Refer to caption](https://arxiv.org/html/2607.05464v1/x1.png)

Figure 1:Structural difference between ordinal and nominal attributes from the perspective of graph\. The black nodes stand for possible values and the edges reflect the spatial relationships among possible values\.We firstly discuss the difference between ordinal and nominal attributes\. As shown in Fig\.[1](https://arxiv.org/html/2607.05464#S4.F1), if we treat the intra\-attribute possible values as nodes connected by edges, since nodes of an ordinal attribute are naturally ordered, one node cannot be reached along the edges from another non\-adjacent node without crossing its adjacent node, while for a nominal attribute, a node can be directly reached along an edge from any node without involving such “crossing”\. We construct graphs for studying the heterogeneity between ordinal and nominal attributes because graph is effective in modeling complex relationships between nodes\[[54](https://arxiv.org/html/2607.05464#bib.bib82),[47](https://arxiv.org/html/2607.05464#bib.bib81)\], and has been successfully applied to different machine learning tasks, such as sketch synthesis\[[58](https://arxiv.org/html/2607.05464#bib.bib83)\], item recommendation\[[37](https://arxiv.org/html/2607.05464#bib.bib65)\], object retrieval\[[15](https://arxiv.org/html/2607.05464#bib.bib84)\], etc\. It can be seen according to Fig\.[1](https://arxiv.org/html/2607.05464#S4.F1)that the structure of ordinal attribute is line\-like while the structure of nominal attribute is net\-like\. These structures are consistent with the relationships among intra\-attribute possible values of ordinal and nominal attributes from the practical point of view\. For example, if we compare two choices, i\.e\., bad and very\-good, of the review result regarding the novelty of a manuscript with the five choices\{very\-good,good,neural,bad,very\-bad\}\\\{\\text\{very\-good\},\\text\{good\},\\text\{neural\},\\text\{bad\},\\text\{very\-bad\}\\\}\. We will not skip neutral and good to directly compare bad and very\-good, because all the choices are clearly ordered\. In contrast, if we compare two choices that belong to a choice set without such order relationship, we will directly compare the two choices without involving the other choices\. It is obvious that the structures of ordinal and nominal attributes are heterogeneous, which makes their intra\-attribute distances difficult to be defined in a homogeneous way\.

### 4\.2Homogeneous Learning

![Refer to caption](https://arxiv.org/html/2607.05464v1/x2.png)

Figure 2:Converting a nominal attributeAsA^\{s\}into a set of ordinal attributesBsB^\{s\}: Each nominal possible valueogso^\{s\}\_\{g\}is converted into an ordinal attributeAgA^\{g\}with two ordered possible valuesogso^\{s\}\_\{g\}and¬ogs\\neg o^\{s\}\_\{g\}\.For mixed categorical data, there are two cases for Eq\. \([5](https://arxiv.org/html/2607.05464#S3.E5)\): 1\)As∈A\(ord\)A^\{s\}\\in A^\{\(\\text\{ord\}\)\}, and 2\)As∈A\(nom\)A^\{s\}\\in A^\{\(\\text\{nom\}\)\}\. Since the possible values of an ordinal attribute represent the different degrees of a concept while the possible values of a nominal attribute represent different concepts, we convert possible values of a nominal attribute into ordinal attributes as shown in Fig\.[2](https://arxiv.org/html/2607.05464#S4.F2)so that the original nominal attribute becomes homogeneous with ordinal attributes\. Specifically, forAs∈A\(nom\)A^\{s\}\\in A^\{\(\\text\{nom\}\)\}withvsv^\{s\}possible values, we convert it into a set ofvsv^\{s\}ordinal attributes

Bs=\{Ag\|g∈NOs\}B^\{s\}=\\\{A^\{g\}\|g\\in N\_\{O\}^\{s\}\\\}\(6\)whereAgA^\{g\}is a newly generated ordinal attribute corresponding to the possible valueogso\_\{g\}^\{s\}ofAsA^\{s\}\. EachAgA^\{g\}has two possible valueso1g=ogso\_\{1\}^\{g\}=o\_\{g\}^\{s\}ando2g=¬ogso\_\{2\}^\{g\}=\\neg o\_\{g\}^\{s\}wherevg=2v^\{g\}=2ando1g≻o2go\_\{1\}^\{g\}\\succ o\_\{2\}^\{g\}\. Here,¬ogs\\neg o\_\{g\}^\{s\}stands for all the possible values ofAsA^\{s\}exceptogso\_\{g\}^\{s\}\. EachAgA^\{g\}can be viewed as a special case of ordinal attribute, in which there are only two possible values indicating two extreme degrees, i\.e\., “isogso\_\{g\}^\{s\}” and “is notogso\_\{g\}^\{s\}”\. In this way, all the nominal attributes can be converted into ordinal attributes, and the intra\-attribute distances can then be measured according to the same type of information provided by the attributes\.

### 4\.3Design of Proposed Distance Metric

The distance between two possible values \(e\.g\.,omr\{o\}^\{r\}\_\{m\}andohr\{o\}^\{r\}\_\{h\}of attributeArA^\{r\}\) with respect to another attribute \(e\.g\.AsA^\{s\}\) is defined in this part\. Before presenting the details of this distance definition, let us first define the conditional probability distribution of an attribute \(e\.g\.,AsA^\{s\}\) with respect to a possible value \(e\.g\.,omro\_\{m\}^\{r\}\), which can be written as

umr​s=\[p​\(o1s\|omr\),p​\(o2s\|omr\),…,p​\(ovss\|omr\)\]⊤\\textbf\{u\}\_\{m\}^\{rs\}=\[p\(o\_\{1\}^\{s\}\|o\_\{m\}^\{r\}\),p\(o\_\{2\}^\{s\}\|o\_\{m\}^\{r\}\),\.\.\.,p\(o\_\{v^\{s\}\}^\{s\}\|o\_\{m\}^\{r\}\)\]^\{\\top\}\(7\)wherep​\(ogs\|omr\)p\(o\_\{g\}^\{s\}\|o\_\{m\}^\{r\}\)is the conditional probability ofogs\{o\}\_\{g\}^\{s\}with respect toomr\{o\}\_\{m\}^\{r\}following Bayes’ theorem:

p​\(ogs\|omr\)=card​\(Xgs∩Xmr\)card​\(Xmr\)\.p\(\{o\}\_\{g\}^\{s\}\|\{o\}\_\{m\}^\{r\}\)=\\frac\{\\text\{card\}\(X\_\{g\}^\{s\}\\cap X\_\{m\}^\{r\}\)\}\{\\text\{card\}\(X\_\{m\}^\{r\}\)\}\.\(8\)Here,Xgs=\{xi\|xis=ogs,i∈NX\}X\_\{g\}^\{s\}=\\\{\\textbf\{x\}\_\{i\}\|x^\{s\}\_\{i\}=o^\{s\}\_\{g\},i\\in N\_\{X\}\\\}is a subset ofXXwith thessth values of all its objects equal toogs\{o\}^\{s\}\_\{g\}, and the functioncard​\(⋅\)\\text\{card\}\(\\cdot\)counts the cardinality of a set\. Then, we define the distance between two possible values \(e\.g\.,omr\{o\}^\{r\}\_\{m\}andohr\{o\}^\{r\}\_\{h\}of attributeArA^\{r\}\) with respect to another attribute \(e\.g\.AsA^\{s\}\) as follows:

distr​s​\(omr,ohr\)=\{ψ​\(umr​s,uhr​s\),As∈A\(ord\)1vs​∑g=1vsψ​\(umr​g,uhr​g\),As∈A\(nom\),\\text\{dist\}^\{rs\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)=\\left\\\{\\begin\{array\}\[\]\{ll\}\\psi\(\\textbf\{u\}^\{rs\}\_\{m\},\\textbf\{u\}^\{rs\}\_\{h\}\),&A^\{s\}\\in A^\{\(\\text\{ord\}\)\}\\\\ \\dfrac\{1\}\{v^\{s\}\}\\sum\_\{g=1\}^\{v^\{s\}\}\\psi\(\\textbf\{u\}^\{rg\}\_\{m\},\\textbf\{u\}^\{rg\}\_\{h\}\),&A^\{s\}\\in A^\{\(\\text\{nom\}\)\},\\\\ \\end\{array\}\\right\.\(9\)whereψ​\(⋅,⋅\)\\psi\(\\cdot,\\cdot\)computes the distance between two probability distributions\. For the nominal case \(i\.e\.,As∈A\(nom\)A^\{s\}\\in A^\{\(\\text\{nom\}\)\}\), the distance with respect toAsA^\{s\}is computed as the mean of the distances with respect to the ordinal attributesAg∈BsA^\{g\}\\in B^\{s\}that are converted from a nominal attributeAsA^\{s\}as shown in Fig\.[2](https://arxiv.org/html/2607.05464#S4.F2)\. See Eq\. \([6](https://arxiv.org/html/2607.05464#S4.E6)\) and corresponding discussions in Section[4\.2](https://arxiv.org/html/2607.05464#S4.SS2)for more details\. As bothAsA^\{s\}in the ordinal case andAgA^\{g\}in the nominal case are ordinal attributes, we only need to discuss how to defineψ​\(⋅,⋅\)\\psi\(\\cdot,\\cdot\)in the ordinal case\.

In the literature, although the distance between two probability distributions is commonly computed in the form ofl1l\_\{1\}\-norm \(i\.e\.,‖umr​s−uhr​s‖1\|\|\\textbf\{u\}^\{rs\}\_\{m\}\-\\textbf\{u\}^\{rs\}\_\{h\}\|\|\_\{1\}\) orl2l\_\{2\}\-norm \(i\.e\.,‖umr​s−uhr​s‖2\|\|\\textbf\{u\}^\{rs\}\_\{m\}\-\\textbf\{u\}^\{rs\}\_\{h\}\|\|\_\{2\}\), they are not suitable here because they cannot preserve order relationship among possible values of an ordinal attribute\. For example, givenu1=\[1,0,0,0\]⊤\\textbf\{u\}\_\{1\}=\[1,0,0,0\]^\{\\top\},u2=\[0,1,0,0\]⊤\\textbf\{u\}\_\{2\}=\[0,1,0,0\]^\{\\top\},u3=\[0,0,0,1\]⊤\\textbf\{u\}\_\{3\}=\[0,0,0,1\]^\{\\top\}, we have‖u1−u2‖1=‖u1−u3‖1\|\|\\textbf\{u\}\_\{1\}\-\\textbf\{u\}\_\{2\}\|\|\_\{1\}=\|\|\\textbf\{u\}\_\{1\}\-\\textbf\{u\}\_\{3\}\|\|\_\{1\}\. However, ifu1\\textbf\{u\}\_\{1\},u2\\textbf\{u\}\_\{2\},u3\\textbf\{u\}\_\{3\}are obtained from an ordinal attribute, it is obvious thatu1\\textbf\{u\}\_\{1\}andu2\\textbf\{u\}\_\{2\}are more similar thanu1\\textbf\{u\}\_\{1\}andu3\\textbf\{u\}\_\{3\}, because the two possible values that rank 1st and 2nd are more similar than the two possible values that rank 1st and 4th\. To preserve the order relationship, we defineψ​\(⋅,⋅\)\\psi\(\\cdot,\\cdot\)as the cost of transforming a probability distribution into another according to the structure of ordinal attribute shown in Fig\.[1](https://arxiv.org/html/2607.05464#S4.F1), andψ​\(umr​s,uhr​s\)\\psi\(\\textbf\{u\}^\{rs\}\_\{m\},\\textbf\{u\}^\{rs\}\_\{h\}\)can be written as

ψ​\(umr​s,uhr​s\)=∑t=1vs−1\|∑g=1t\(p\(ogs\|omr\)−p\(ogs\|ohr\)\)\|vs−1\.\\psi\(\\textbf\{u\}^\{rs\}\_\{m\},\\textbf\{u\}^\{rs\}\_\{h\}\)=\\frac\{\\sum\_\{t=1\}^\{v^\{s\}\-1\}\|\\sum\_\{g=1\}^\{t\}\\left\(p\(\{o\}\_\{g\}^\{s\}\|\{o\}\_\{m\}^\{r\}\)\-p\(\{o\}\_\{g\}^\{s\}\|\{o\}\_\{h\}^\{r\}\)\\right\)\|\}\{v^\{s\}\-1\}\.\(10\)The distance defined in Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) computes the minimum moving cost for transformingumr​s\\textbf\{u\}^\{rs\}\_\{m\}intouhr​s\\textbf\{u\}^\{rs\}\_\{h\}\(oruhr​s\\textbf\{u\}^\{rs\}\_\{h\}intoumr​s\\textbf\{u\}^\{rs\}\_\{m\}\), where\|∑g=1t\(p\(ogs\|omr\)−p\(ogs\|ohr\)\)\|\|\\sum\_\{g=1\}^\{t\}\\left\(p\(\{o\}\_\{g\}^\{s\}\|o\_\{m\}^\{r\}\)\-p\(o\_\{g\}^\{s\}\|o\_\{h\}^\{r\}\)\\right\)\|in Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) is the total ‘supplies’ or ‘demands’ at locationotso\_\{t\}^\{s\}that should be moved to locationsot\+1s,ot\+2s,…,ovss\{o\}\_\{t\+1\}^\{s\},\{o\}\_\{t\+2\}^\{s\},\.\.\.,\{o\}\_\{v^\{s\}\}^\{s\}for offsetting\. During the above computation, the ‘moving distance’ between adjacent values is 1 because the prior knowledge we have is that the rank of a possible value is different from its adjacent possible value\(s\) by 1\. A toy example shown in Fig\.[3](https://arxiv.org/html/2607.05464#S4.F3)intuitively illustrates the computation process\.

![Refer to caption](https://arxiv.org/html/2607.05464v1/x3.png)Figure 3:Computation process of Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\)\. In step 1, we haveumr​s=\[0\.5,0\.3,0\.2\]⊤\\textbf\{u\}^\{rs\}\_\{m\}=\[0\.5,0\.3,0\.2\]^\{\\top\}, i\.e\. the upper histogram, anduhr​s=\[0\.2,0\.2,0\.6\]⊤\\textbf\{u\}^\{rs\}\_\{h\}=\[0\.2,0\.2,0\.6\]^\{\\top\}, i\.e\. the lower histogram\. To transformumr​s\\textbf\{u\}^\{rs\}\_\{m\}intouhr​s\\textbf\{u\}^\{rs\}\_\{h\}, we first subtract them and obtain the histogram\[0\.3,0\.1,−0\.4\]⊤\[0\.3,0\.1,\-0\.4\]^\{\\top\}in step 2\. The slash\-filled bins indicate supplies, and the dot\-filled bin indicates demand\. Then, 0\.3 supply at the first place is moved to the second place with 0\.1 supply, the moving cost is \(0\.3×\\times1\)/2 = 0\.15\. In step 3, the total 0\.4 supply at the second place is moved to the third place with 0\.4 demand, the moving cost is \(0\.4×\\times1\)/2 = 0\.2\. Since the supply and demand exactly offset each other after step 3, the transforming is completed in step 4, and the total transforming cost is 0\.15 \+ 0\.2 = 0\.35\.Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) elaborately reflects the distance between two probability distributions obtained from an ordinal attribute, and we discuss it in detail below:

- •According to our design, ‘supplies’ and ‘demands’ are moved strictly according to the structure of ordinal attribute as shown in Fig\.[1](https://arxiv.org/html/2607.05464#S4.F1)\. It turns out that the order relationship among the possible values is taken into account in computing the distance between two distributions by Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\)\.
- •It is intuitive that two more different distributions yield more ‘supplies’ and ‘demands’ for moving, and thus result in a larger distance computed by Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\), which is consistent with the general distance definitions like Manhattan and Euclidean distance\.
- •In terms of the form, Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) can be viewed as a special case of the Earth Movers’ Distance \(EMD\)\[[51](https://arxiv.org/html/2607.05464#bib.bib49),[36](https://arxiv.org/html/2607.05464#bib.bib50),[52](https://arxiv.org/html/2607.05464#bib.bib51)\], as Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) only permits ‘moving’ between adjacent bins of histograms\. However, Eq\. \([10](https://arxiv.org/html/2607.05464#S4.E10)\) is designed under the guidance of the proposed graph structure shown in Fig\.[1](https://arxiv.org/html/2607.05464#S4.F1), which is very different from the motivation and principle for designing EMD\.

Eq\. \([9](https://arxiv.org/html/2607.05464#S4.E9)\) and \([10](https://arxiv.org/html/2607.05464#S4.E10)\) have defined the distance between two possible values with respect to an attribute\. Then, according to the structures of nominal and ordinal attributes studied in Section[4\.1](https://arxiv.org/html/2607.05464#S4.SS1), we define the overall distance between two possible values by combining their distances with respect to each attribute as follows:

distr​\(omr,ohr\)=\{1d​∑s=1d∑t=min⁡\(m,h\)max⁡\(m,h\)−1distr​s​\(otr,ot\+1r\)Ar∈A\(ord\)1d​∑s=1ddistr​s​\(omr,ohr\),Ar∈A\(nom\)\.\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)=\\left\\\{\\begin\{array\}\[\]\{l\}\\dfrac\{1\}\{d\}\\sum\_\{s=1\}^\{d\}\\sum\_\{t=\\min\(m,h\)\}^\{\\max\(m,h\)\-1\}\\text\{dist\}^\{rs\}\(\{o\}^\{r\}\_\{t\},\{o\}^\{r\}\_\{t\+1\}\)\\\\ \\qquad\\qquad\\qquad\\qquad\\qquad\\qquad A^\{r\}\\in A^\{\(\\text\{ord\}\)\}\\\\ \\dfrac\{1\}\{d\}\\sum\_\{s=1\}^\{d\}\\text\{dist\}^\{rs\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\),\\quad\\ \\ \\ A^\{r\}\\in A^\{\(\\text\{nom\}\)\}\.\\\\ \\end\{array\}\\right\.\(11\)
Based on Eq\. \([11](https://arxiv.org/html/2607.05464#S4.E11)\), the distance between two data objectsxi\\textbf\{x\}\_\{i\}andxj\\textbf\{x\}\_\{j\}with theirrrth values denoted asxir=omrx\_\{i\}^\{r\}=o^\{r\}\_\{m\}andxjr=ohrx^\{r\}\_\{j\}=o^\{r\}\_\{h\}, respectively, can be written as

dist​\(xi,xj\)=1d​∑r=1ddistr​\(omr,ohr\)\.\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)=\\frac\{1\}\{d\}\\sum\_\{r=1\}^\{d\}\\text\{dist\}^\{r\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)\.\(12\)
###### Theorem 1\.

Distance measure defined in Eq\. \([9](https://arxiv.org/html/2607.05464#S4.E9)\)\-\([12](https://arxiv.org/html/2607.05464#S4.E12)\) is a distance metric\.

###### Proof\.

According to Eq\. \([9](https://arxiv.org/html/2607.05464#S4.E9)\)\-\([11](https://arxiv.org/html/2607.05464#S4.E11)\), it is clear that the defined intra\-attribute distance satisfies the following properties for anym,h,t∈NOrm,h,t\\in N^\{r\}\_\{O\}andr∈NAr\\in N\_\{A\}:

1. 1\.distr​\(omr,ohr\)≥0\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)\\geq 0;
2. 2\.omr=ohr⇔distr​\(omr,ohr\)=0\{o\}^\{r\}\_\{m\}=\{o\}^\{r\}\_\{h\}\\Leftrightarrow\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)=0;
3. 3\.distr​\(omr,ohr\)=distr​\(ohr,omr\)\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)=\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{h\},\{o\}^\{r\}\_\{m\}\);
4. 4\.distr​\(omr,ohr\)≤distr​\(omr,otr\)\+distr​\(otr,ohr\)\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{h\}\)\\leq\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{m\},\{o\}^\{r\}\_\{t\}\)\+\\text\{dist\}^\{r\}\(\{o\}^\{r\}\_\{t\},\{o\}^\{r\}\_\{h\}\)\.

According to Eq\. \([12](https://arxiv.org/html/2607.05464#S4.E12)\), it is clear that the following properties hold for anyi,j,l∈NXi,j,l\\in N\_\{X\}:

1. 1\.dist​\(xi,xj\)≥0\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)\\geq 0;
2. 2\.xi=xj⇔dist​\(xi,xj\)=0\\textbf\{x\}\_\{i\}=\\textbf\{x\}\_\{j\}\\Leftrightarrow\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)=0;
3. 3\.dist​\(xi,xj\)=dist​\(xj,xi\)\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)=\\text\{dist\}\(\\textbf\{x\}\_\{j\},\\textbf\{x\}\_\{i\}\);
4. 4\.dist​\(xi,xj\)≤dist​\(xi,xl\)\+dist​\(xl,xj\)\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)\\leq\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{l\}\)\+\\text\{dist\}\(\\textbf\{x\}\_\{l\},\\textbf\{x\}\_\{j\}\)\.

The defined distance measure satisfies all the distance metric properties\. ∎

In practice, a set of distance matrices, i\.e\.D=\{Dr\|r∈NA\}D=\\\{\\textbf\{D\}^\{r\}\|r\\in N\_\{A\}\\\}whereDr\\textbf\{D\}^\{r\}is avr×vrv^\{r\}\\times v^\{r\}symmetric matrix storing intra\-attribute distances ofArA^\{r\}, can be computed before clustering\. The\(m,h\)\(m,h\)th entry ofDr\\textbf\{D\}^\{r\}is denoted asdm​hrd^\{r\}\_\{mh\}wheredm​hr=distr​\(omr,ohr\)d^\{r\}\_\{mh\}=\\text\{dist\}^\{r\}\(o^\{r\}\_\{m\},o^\{r\}\_\{h\}\)\. WithDD, distances can be directly read off during clustering\.

###### Theorem 2\.

Time complexity for computing the distance matricesDDisO​\(n​d2\+d2​V3\)O\(nd^\{2\}\+d^\{2\}V^\{3\}\)\.

###### Proof\.

Conditional probability distributionumr​s\\textbf\{u\}\_\{m\}^\{rs\}withr,s∈NAr,s\\in N\_\{A\}andm∈NOrm\\in N^\{r\}\_\{O\}should be obtained before distance computation\. For eachumr​s\\textbf\{u\}\_\{m\}^\{rs\},omro^\{r\}\_\{m\}’s corresponding values onAsA^\{s\}should be scanned once with time complexityO​\(card​\(Xmr\)\)O\(\\text\{card\}\(X^\{r\}\_\{m\}\)\), and for all theumr​s\\textbf\{u\}\_\{m\}^\{rs\}withm∈NOrm\\in N^\{r\}\_\{O\}, the scan is with time complexityO​\(n\)O\(n\)\. Such scan should be performed for each pair of attributes, and thus the time complexity isO​\(n​d2\)O\(nd^\{2\}\)\.

Given a pair of possible valuesomr\{o\}^\{r\}\_\{m\}andohr\{o\}^\{r\}\_\{h\}withm,h∈NOrm,h\\in N^\{r\}\_\{O\}andr∈NAr\\in N\_\{A\}, the time complexity for computing the distance between them based on the knownumr​s\\textbf\{u\}\_\{m\}^\{rs\}anduhr​s\\textbf\{u\}\_\{h\}^\{rs\}isO​\(V\)O\(V\)in both the two cases of Eq\. \([9](https://arxiv.org/html/2607.05464#S4.E9)\)\. Note thatV=max⁡\(v1,v2,…,vd\)V=\\max\(v^\{1\},v^\{2\},\.\.\.,v^\{d\}\)is the maximum number of possible values among all the attributes, which is adopted to simplify the time complexity analysis\. To obtainDr\\textbf\{D\}^\{r\}, the time complexity for computing theV​\(V−1\)/2V\(V\-1\)/2intra\-attribute distances isO​\(d​V3\)O\(dV^\{3\}\)in the caseAr∈A\(nom\)A^\{r\}\\in A^\{\(\\text\{nom\}\)\}of Eq\. \([11](https://arxiv.org/html/2607.05464#S4.E11)\)\. In the caseAr∈A\(ord\)A^\{r\}\\in A^\{\(\\text\{ord\}\)\}of Eq\. \([11](https://arxiv.org/html/2607.05464#S4.E11)\), distance between possible values with order difference 1 can be computed first, and then the distance between possible values with order difference 2, 3, …,V−1V\-1can be successively computed based on the distances computed in the previous step\. Therefore, the time complexity for computing theV​\(V−1\)/2V\(V\-1\)/2intra\-attribute distances is alsoO​\(d​V3\)O\(dV^\{3\}\)in the caseAr∈A\(ord\)A^\{r\}\\in A^\{\(\\text\{ord\}\)\}of Eq\. \([11](https://arxiv.org/html/2607.05464#S4.E11)\)\. The time complexity for computing a total ofdddistance matricesDr\\textbf\{D\}^\{r\}is thusO​\(d2​V3\)O\(d^\{2\}V^\{3\}\)\. Hence, the overall time complexity for obtainingDDisO​\(n​d2\+d2​V3\)O\(nd^\{2\}\+d^\{2\}V^\{3\}\)\. ∎

## 5Clustering Based on Intra\-Attribute Distance Weighting

Often, separately treating the cross\-coupled distance defining and data clustering results in a suboptimal solution\. This section will therefore propose a learning mechanism that adjusts the defined intra\-attribute distances to suit certain clustering tasks\. We have constructed graph\-like structure for the intra\-attribute possible values to define their distances in Section[4](https://arxiv.org/html/2607.05464#S4), and will learn the weights of the distances in an iterative way with data clustering in the following subsections\. Before introducing the details of our algorithm, let us conceptually discuss the existing methods whose learning paradigms are intuitively similar to ours\.

Several clustering of bandits algorithms\[[17](https://arxiv.org/html/2607.05464#bib.bib69),[37](https://arxiv.org/html/2607.05464#bib.bib65),[45](https://arxiv.org/html/2607.05464#bib.bib67)\]have been proposed to construct graph for the objects \(i\.e\., users in their application scenarios\) and dynamically perform graph clustering according to the item preference of users over time\. Further, the one in\[[38](https://arxiv.org/html/2607.05464#bib.bib66)\]captures the collaborative effects of the users, and the one in\[[39](https://arxiv.org/html/2607.05464#bib.bib68)\]captures the bi\-collaborative effects between users and items by iteratively partitioning user and item graphs\. The commonality of our method and the above\-mentioned ones is that they all iteratively learn \(1\) the relationship between objects and \(2\) certain predictions for the objects\. The differences are: \(1\) we construct graphs only for studying the distance definition between possible values, while most of the above\-mentioned methods construct graphs for objects and cutting the graphs for object partitioning, \(2\) we optimize the prediction from objects to object clusters, while they optimize the prediction of items to be recommended to users\. Although the above\-mentioned methods are not solving the same type of problem as ours, their paradigms can provide inspiration for applying our method in more complex environments in the future, for example, in on\-line or distributed situations\. In the following, we will elaborate how to solve the two problemsP\. 1andP\. 2stated in Section[3](https://arxiv.org/html/2607.05464#S3), and present the clustering algorithm, together with the time\-complexity analysis\.

### 5\.1UpdateQAs GivenWWandPP

The process of solving problemP\. 1is to obtain a data partition according to a certain distance measure and cluster representation, which actually adopts the same basic idea as mostkk\-modes\-type algorithms\. The difference is that we use the statistical informationPP\(defined in Section[3](https://arxiv.org/html/2607.05464#S3)\) instead of cluster modes in representing the clusters, which ensures the extraction of more rich information for learning distance weightsWWin solving problemP\. 2\. Specifically, the details of solvingP\. 1are presented as follows\. According to the objective function defined in Eq\. \([2](https://arxiv.org/html/2607.05464#S3.E2)\),P\. 1is solved by fixingW=W^W=\\hat\{W\}andP=P^P=\\hat\{P\}, and computingQ\. Given distance matricesDD,Qis computed by

qi​l=\{1,if​l=arg⁡miny⁡dist​\(xi,Cy\)=arg⁡miny​∑r=1d∑h=1vrwm​hr^​dm​hr​py​hr^0,otherwiseq\_\{il\}=\\left\\\{\\begin\{array\}\[\]\{ll\}1,&\\text\{if\}\\ \{l=\\arg\\min\_\{y\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{y\}\)\}\\\\ &\\quad\\ \\ =\\arg\\min\_\{y\}\\sum\_\{r=1\}^\{d\}\\sum\_\{h=1\}^\{v^\{r\}\}\\hat\{w^\{r\}\_\{mh\}\}d^\{r\}\_\{mh\}\\hat\{p^\{r\}\_\{yh\}\}\\\\ 0,&\\text\{otherwise\}\\end\{array\}\\right\.\\\\\(13\)forxi\\textbf\{x\}\_\{i\}withxir=omrx^\{r\}\_\{i\}=o^\{r\}\_\{m\}\. Since we represent the clusters using their probability distributions byPPinstead of using cluster modes, the form of the solution in Eq\. \([13](https://arxiv.org/html/2607.05464#S5.E13)\) is different form the conventionalkk\-modes\-type algorithms\. Thus, solution toP\. 1is also rigorously given in Theorem[3](https://arxiv.org/html/2607.05464#Thmtheorem3)\.

###### Theorem 3\.

LetWWandPPbe fixed,Z​\(Q,P^,W^\)Z\(\\textbf\{Q\},\\hat\{P\},\\hat\{W\}\)is minimized iffQis computed utilizing Eq\. \([13](https://arxiv.org/html/2607.05464#S5.E13)\)\.

###### Proof\.

For any givenW=W^W=\\hat\{W\}andP=P^P=\\hat\{P\}, all the inner sums of the quantity

Z​\(Q,P^,W^\)=∑i=1n∑l=1kqi​l​dist​\(xi,Cl\)\\displaystyle Z\(\\textbf\{Q\},\\hat\{P\},\\hat\{W\}\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{l=1\}^\{k\}q\_\{il\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)are nonnegative and independent\. Letomr=xiro^\{r\}\_\{m\}=x^\{r\}\_\{i\}, we can write the inner sum contributed byxi\\textbf\{x\}\_\{i\}as

zi=∑l=1kqi​l​dist​\(xi,Cl\)=∑l=1kqi​l​∑r=1d∑h=1vrwm​hr^​dm​hr​pl​hr^\.\\displaystyle z\_\{i\}=\\sum\_\{l=1\}^\{k\}q\_\{il\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)=\\sum\_\{l=1\}^\{k\}q\_\{il\}\\sum\_\{r=1\}^\{d\}\\sum\_\{h=1\}^\{v^\{r\}\}\\hat\{w^\{r\}\_\{mh\}\}d^\{r\}\_\{mh\}\\hat\{p^\{r\}\_\{lh\}\}\.Letzi​l=∑r=1d∑h=1vrwm​hr^​dm​hr​pl​hr^z\_\{il\}=\\sum\_\{r=1\}^\{d\}\\sum\_\{h=1\}^\{v^\{r\}\}\\hat\{w^\{r\}\_\{mh\}\}d^\{r\}\_\{mh\}\\hat\{p^\{r\}\_\{lh\}\}, which is the inner sum contributed byxi\\textbf\{x\}\_\{i\}inClC\_\{l\}\. We then obtain

zi=∑l=1kqi​l​zi​l\.\\displaystyle z\_\{i\}=\\sum\_\{l=1\}^\{k\}q\_\{il\}z\_\{il\}\.Since∑l=1kqi​l=1\\sum\_\{l=1\}^\{k\}q\_\{il\}=1andqi​l∈\{0,1\}q\_\{il\}\\in\\\{0,1\\\}, it is clear thatziz\_\{i\}is minimized iff the minimumzi​lz\_\{il\}is assigned withqi​l=1q\_\{il\}=1wherellis determined by

l\\displaystyle l=arg⁡miny⁡zi​y=arg⁡miny​∑r=1d∑h=1vrwm​hr^​dm​hr​py​hr^\\displaystyle=\\arg\\min\_\{y\}z\_\{iy\}=\\arg\\min\_\{y\}\\sum\_\{r=1\}^\{d\}\\sum\_\{h=1\}^\{v^\{r\}\}\\hat\{w^\{r\}\_\{mh\}\}d^\{r\}\_\{mh\}\\hat\{p^\{r\}\_\{yh\}\}and the otherzi​lz\_\{il\}s are assigned withqi​l=0q\_\{il\}=0\. The result follows\.∎

We have presented the solution of updatingQ\. Each time a newQis obtained, the cluster representationPPis updated accordingly, and such process is iterated until convergence\.

### 5\.2UpdateWWAs GivenQandPP

In Section[5\.1](https://arxiv.org/html/2607.05464#S5.SS1), we have presented the solution ofP\. 1\. Then,P\. 2should be solved based on the presentQandPPto learn distance weightsWW\. In this part, a novel learning scheme is designed by mining the latent interaction between data partition and intra\-attribute distances, so as to seek for more appropriate data partition in the next iteration based on the defined intra\-attribute distances and the newly learnedWW\. The details of solvingP\. 2are presented as follows\. Given fixedQ^\\hat\{\\textbf\{Q\}\}andP^\\hat\{P\}, the objective function defined by Eq\. \([2](https://arxiv.org/html/2607.05464#S3.E2)\) can be written as

Z​\(Q^,P^,W\)\\displaystyle Z\(\\hat\{\\textbf\{Q\}\},\\hat\{P\},W\)=∑i=1n∑l=1kqi​l^​dist​\(xi,Cl\)\\displaystyle=\\sum\_\{i=1\}^\{n\}\\sum\_\{l=1\}^\{k\}\\hat\{q\_\{il\}\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)=∑i=1n∑l=1kqi​l^​∑r=1d∑h=1vrwm​hr​dm​hr​pl​hr^\\displaystyle=\\sum\_\{i=1\}^\{n\}\\sum\_\{l=1\}^\{k\}\\hat\{q\_\{il\}\}\\sum\_\{r=1\}^\{d\}\\sum\_\{h=1\}^\{v^\{r\}\}w^\{r\}\_\{mh\}d^\{r\}\_\{mh\}\\hat\{p^\{r\}\_\{lh\}\}=∑r=1d∑m=1vr∑h=1vrwm​hr​dm​hr​∑l=1kfl​mr​fl​hrfl\\displaystyle=\\sum\_\{r=1\}^\{d\}\\sum\_\{m=1\}^\{v^\{r\}\}\\sum\_\{h=1\}^\{v^\{r\}\}w^\{r\}\_\{mh\}d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}\\frac\{f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\}\{f\_\{l\}\}\(14\)wherefl​mr=card​\(Xmr∩XCl\)f^\{r\}\_\{lm\}=\\text\{card\}\(X^\{r\}\_\{m\}\\cap X\_\{C\_\{l\}\}\)andfl​hr=card​\(Xhr∩XCl\)f^\{r\}\_\{lh\}=\\text\{card\}\(X^\{r\}\_\{h\}\\cap X\_\{C\_\{l\}\}\)are the total number of objects inClC\_\{l\}with theirrrth values equal toomro^\{r\}\_\{m\}andohro^\{r\}\_\{h\}, respectively,fl=card​\(XCl\)f\_\{l\}=\\text\{card\}\(X\_\{C\_\{l\}\}\)is the number of objects inClC\_\{l\}, and we havefl​hr/fl=pl​hr^f^\{r\}\_\{lh\}/f\_\{l\}=\\hat\{p^\{r\}\_\{lh\}\}\. In mostkk\-modes\-type algorithm with attribute weighting mechanism\[[20](https://arxiv.org/html/2607.05464#bib.bib31),[9](https://arxiv.org/html/2607.05464#bib.bib30),[6](https://arxiv.org/html/2607.05464#bib.bib33)\], Lagrangian multiplier is used to convert the constrained weights computation problem into an unconstrained problem so that the optimal attribute weights can be computed directly in each iteration\. However, solving our intra\-attribute distance weighting problem in this way may encounter two awkward issues:

- •Frequency Effect:For attribute weighting, each attribute has the identical number of values, which is the basis for success in making the computed weights comparable\. However, the occurrence frequencies of intra\-attribute distances \(i\.e\.∑l=1kfl​mr​fl​hr\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}ofdm​hrd^\{r\}\_\{mh\}\) are usually different from each other, which makes the computed weights of intra\-attribute distances incomparable\.
- •Co\-occurrence Sparsity:It is common for a real categorical data set that an intra\-attribute distance \(i\.e\.dm​hrd^\{r\}\_\{mh\}\) never occur in a cluster, so that no statistical information is provided for the computation of its corresponding weightwm​hrw^\{r\}\_\{mh\}\. If we set such weights to 0, the problem still cannot be fixed because there are many such weights preventing the algorithm from convergence\.

We propose a novel intra\-attribute distance weight updating scheme to circumvent the above\-discussed issues\. In general, a largerdm​hrd\_\{mh\}^\{r\}indicates that the two corresponding possible valuesomro^\{r\}\_\{m\}andohro^\{r\}\_\{h\}are more dissimilar\. That is,dm​hrd\_\{mh\}^\{r\}is expected to contribute more in partitioning the objects inXmr=\{xi\|xir=omr,i∈NX\}X^\{r\}\_\{m\}=\\\{\\textbf\{x\}\_\{i\}\|x^\{r\}\_\{i\}=o^\{r\}\_\{m\},i\\in N\_\{X\}\\\}and the objects inXhr=\{xi\|xir=ohr,i∈NX\}X^\{r\}\_\{h\}=\\\{\\textbf\{x\}\_\{i\}\|x^\{r\}\_\{i\}=o^\{r\}\_\{h\},i\\in N\_\{X\}\\\}into different clusters\. Thus, given a data partitionQ^\\hat\{\\textbf\{Q\}\}, ifdm​hrd\_\{mh\}^\{r\}is larger but more objects inXmrX^\{r\}\_\{m\}andXhrX^\{r\}\_\{h\}are assigned into the same cluster, it is indicated thatdm​hrd\_\{mh\}^\{r\}does not contribute in partitioning the objectsXmrX^\{r\}\_\{m\}andXhrX^\{r\}\_\{h\}into different clusters as expected\. Accordingly, the weight ofdm​hrd\_\{mh\}^\{r\}should be estimated as its expectation in reducingZ​\(Q^,P^,W\)Z\(\\hat\{\\textbf\{Q\}\},\\hat\{P\},W\), and we have

wm​hr∝\[dm​hr​∑l=1kfl​mr​fl​hrfmr​fhr\]−1w\_\{mh\}^\{r\}\\propto\[d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}\\frac\{f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\]^\{\-1\}\(15\)wherefmr=card​\(Xmr\)=∑l=1kfl​mrf^\{r\}\_\{m\}=\\text\{card\}\(X^\{r\}\_\{m\}\)=\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}andfhr=card​\(Xhr\)=∑l=1kfl​hrf^\{r\}\_\{h\}=\\text\{card\}\(X^\{r\}\_\{h\}\)=\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lh\}are the intra\-cluster occurrence frequencies ofomro^\{r\}\_\{m\}andohro^\{r\}\_\{h\}, respectively\. The term\(fl​mr​fl​hr\)/\(fmr​fhr\)\(f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)quantifies the occurrence ofdm​hrd^\{r\}\_\{mh\}inClC\_\{l\}as a joint occurrence probability ofomro^\{r\}\_\{m\}andohro^\{r\}\_\{h\}inClC\_\{l\}, which avoids theFrequency Effect\. If we directly updateWWbywm​hr=\[dm​hr​∑l=1k\(fl​mr​fl​hr\)/\(fmr​fhr\)\]−1w\_\{mh\}^\{r\}=\[d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}\(f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)\]^\{\-1\}according to Eq\. \([15](https://arxiv.org/html/2607.05464#S5.E15)\), theCo\-occurrence Sparsityissue may make the values of different weights vary greatly in the interval\[1/dm​hr,∞\)\[1/d^\{r\}\_\{mh\},\\infty\), which may cause non\-convergence\. Thus, we discuss how to novelly circumvent theCo\-occurrence Sparsityissue in the following\.

###### Lemma 1\.

Given an arbitrary partitionQof data setSS, sum of the intra\-cluster distanceEm​hr​\(intra\)E^\{r\(\\text\{intra\}\)\}\_\{mh\}and inter\-cluster distanceEm​hr​\(inter\)E^\{r\(\\text\{inter\}\)\}\_\{mh\}contributed bydm​hrd^\{r\}\_\{mh\}is a constant\.

###### Proof\.

We first note thatEm​hr​\(intra\)=dm​hr​∑l=1kfl​mr​fl​hrE^\{r\(\\text\{intra\}\)\}\_\{mh\}=d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}andEm​hr​\(inter\)=dm​hr​∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)E\_\{mh\}^\{r\(\\text\{inter\}\)\}=d^\{r\}\_\{mh\}\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)\. LetEm​hr​\(total\)=Em​hr​\(intra\)\+Em​hr​\(inter\)E^\{r\(\\text\{total\}\)\}\_\{mh\}=E\_\{mh\}^\{r\(\\text\{intra\}\)\}\+E\_\{mh\}^\{r\(\\text\{inter\}\)\}, we have

Em​hr​\(total\)\\displaystyle E^\{r\(\\text\{total\}\)\}\_\{mh\}=dm​hr​\(∑l=1kfl​mr​fl​hr\+∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)\)\\displaystyle=d^\{r\}\_\{mh\}\\left\(\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\+\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\\left\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\\right\)\\right\)=dm​hr\(∑s=1k∑u=sfs​mrfu​hr\\displaystyle=d^\{r\}\_\{mh\}\\left\(\\sum\_\{s=1\}^\{k\}\\sum\_\{u=s\}f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\\right\.\+∑s=1k−1∑u=s\+1kfs​mrfu​hr\+∑s=1k−1∑u=s\+1kfu​mrfs​hr\)\\displaystyle\\ \\ \\ \\qquad\\left\.\+\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\\right\)=dm​hr​∑s=1k∑u=1kfs​mr​fu​hr=dm​hr​∑s=1kfs​mr​∑u=1kfu​hr\\displaystyle=d^\{r\}\_\{mh\}\\sum\_\{s=1\}^\{k\}\\sum\_\{u=1\}^\{k\}f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}=d^\{r\}\_\{mh\}\\sum\_\{s=1\}^\{k\}f^\{r\}\_\{sm\}\\sum\_\{u=1\}^\{k\}f^\{r\}\_\{uh\}=dm​hr​fmr​fhr\.\\displaystyle=d^\{r\}\_\{mh\}f^\{r\}\_\{m\}f^\{r\}\_\{h\}\.Sincedm​hrd^\{r\}\_\{mh\},fmrf^\{r\}\_\{m\}, andfhrf^\{r\}\_\{h\}are constants for a given data setSS, it is clear thatEm​hr​\(total\)E^\{r\(\\text\{total\}\)\}\_\{mh\}is a constant\. The result follows\. ∎

Based on Lemma[1](https://arxiv.org/html/2607.05464#Thmlemma1), Eq\. \([15](https://arxiv.org/html/2607.05464#S5.E15)\) can be transformed to avoid theCo\-occurrence Sparsityissue\.

###### Lemma 2\.

Given Eq\. \([15](https://arxiv.org/html/2607.05464#S5.E15)\),wm​hr∝dm​hr​∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)/\(fmr​fhr\)w\_\{mh\}^\{r\}\\propto d\_\{mh\}^\{r\}\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)holds when∃l∈NC\\exists\\ l\\in N\_\{C\}so thatfl​mr​fl​hr≠0f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\\neq 0\.

###### Proof\.

LetHm​hr=dm​hr​∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)/\(fmr​fhr\)H^\{r\}\_\{mh\}=d\_\{mh\}^\{r\}\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)\. We first prove thatHm​hr<Em​hr​\(total\)/\(fmr​fhr\)H^\{r\}\_\{mh\}<E^\{r\(\\text\{total\}\)\}\_\{mh\}/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)\. According to the proof of Lemma[1](https://arxiv.org/html/2607.05464#Thmlemma1), we derive

Em​hr​\(total\)fmr​fhr−Hm​hr=dm​hr​∑l=1kfl​mr​fl​hrfmr​fhr\.\\displaystyle\\frac\{E^\{r\(\\text\{total\}\)\}\_\{mh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\-H^\{r\}\_\{mh\}=\\frac\{d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\.\(16\)Since∃l∈NC\\exists\\ l\\in N\_\{C\}so thatfl​mr​fl​hr≠0f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\\neq 0, andfl​mrf^\{r\}\_\{lm\}andfl​hrf^\{r\}\_\{lh\}are non\-negative integers, we have∑l=1kfl​mr​fl​hr\>0\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\>0; Sincefmrf^\{r\}\_\{m\}andfhrf^\{r\}\_\{h\}are positive constants anddm​hr\>0d^\{r\}\_\{mh\}\>0for two different possible valuesomro^\{r\}\_\{m\}andohro^\{r\}\_\{h\}, we then have

dm​hr​∑l=1kfl​mr​fl​hrfmr​fhr\>0⇒Hm​hr<Em​hr​\(total\)fmr​fhr\.\\displaystyle\\dfrac\{d^\{r\}\_\{mh\}\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\>0\\ \\Rightarrow\\ H^\{r\}\_\{mh\}<\\frac\{E^\{r\(\\text\{total\}\)\}\_\{mh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\.From Eq\. \([15](https://arxiv.org/html/2607.05464#S5.E15)\) and \([16](https://arxiv.org/html/2607.05464#S5.E16)\), we derive

wm​hr∝1Em​hr​\(total\)fmr​fhr−Hm​hr\.\\displaystyle w^\{r\}\_\{mh\}\\propto\\frac\{1\}\{\\frac\{E^\{r\(\\text\{total\}\)\}\_\{mh\}\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\-H^\{r\}\_\{mh\}\}\.Since we have provedHm​hr<Em​hr​\(total\)/\(fmr​fhr\)H^\{r\}\_\{mh\}<E^\{r\(\\text\{total\}\)\}\_\{mh\}/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\), andEm​hr​\(total\)/\(fmr​fhr\)E^\{r\(\\text\{total\}\)\}\_\{mh\}/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)is a constant, it is clear that the value ofwm​hrw^\{r\}\_\{mh\}is proportional to the value ofHm​hrH^\{r\}\_\{mh\}, which can be written as

wm​hr∝dm​hr​∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)fmr​fhr\.\\displaystyle w\_\{mh\}^\{r\}\\propto\\frac\{d\_\{mh\}^\{r\}\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\.\(17\)The result follows\. ∎

According to Lemma[2](https://arxiv.org/html/2607.05464#Thmlemma2), the weights of intra\-attribute distances are updated by

wm​hr​\(new\)=dm​hr​∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)fmr​fhr\.w\_\{mh\}^\{r\\text\{\(new\)\}\}=\\dfrac\{d\_\{mh\}^\{r\}\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)\}\{f^\{r\}\_\{m\}f^\{r\}\_\{h\}\}\.\(18\)Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) is obtained with restriction∃l∈NC\\exists\\ l\\in N\_\{C\}so thatfl​mr​fl​hr≠0f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}\\neq 0\. We also demonstrate that when∀l∈NC\\forall\\ l\\in N\_\{C\},fl​mr,fl​hr=0f^\{r\}\_\{lm\},f^\{r\}\_\{lh\}=0, Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) is still meaningful\.∀l∈NC\\forall\\ l\\in N\_\{C\},fl​mr,fl​hr=0f^\{r\}\_\{lm\},f^\{r\}\_\{lh\}=0indicates that the objects inXmrX\_\{m\}^\{r\}and the objects inXhrX\_\{h\}^\{r\}never appear in the same cluster, which means that the contribution ofdm​hrd^\{r\}\_\{mh\}in partitioning the objects inXmrX\_\{m\}^\{r\}and the objects inXhrX\_\{h\}^\{r\}into different clusters reaches the maximum, i\.e\.∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)/\(fmr​fhr\)=1\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)=1\. Since the value of∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)/fmr​fhr\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)/f^\{r\}\_\{m\}f^\{r\}\_\{h\}is in the interval\[0,1\]\[0,1\], it is clear that weights updating utilizing Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) will not be influenced by theCo\-occurrence Sparsityissue\. We also use soft\-max, i\.e\.wm​hr=wm​hr​\(new\)/∑s=1d∑g=1vs−1∑t=g\+1vswg​ts​\(new\)w\_\{mh\}^\{r\}=w\_\{mh\}^\{r\\text\{\(new\)\}\}/\\sum\_\{s=1\}^\{d\}\\sum\_\{g=1\}^\{v^\{s\}\-1\}\\sum\_\{t=g\+1\}^\{v^\{s\}\}w\_\{gt\}^\{s\\text\{\(new\)\}\}, to make the updated weights satisfy∑r=1d∑m=1vr−1∑h=m\+1vrwm​hr=1\\sum\_\{r=1\}^\{d\}\\sum\_\{m=1\}^\{v^\{r\}\-1\}\\sum\_\{h=m\+1\}^\{v^\{r\}\}w^\{r\}\_\{mh\}=1\.

Advantages of the proposed weights updating scheme are summarized below:

- •Frequency Dominanceissue is avoided\.
- •Co\-occurrence Sparsityissue is novelly circumvented\.
- •It is parameter\-free, and the clustering algorithm based on it \(see Section[5\.3](https://arxiv.org/html/2607.05464#S5.SS3)\) always converge quickly, which has been illustrated in Section[6](https://arxiv.org/html/2607.05464#S6)\.

### 5\.3Complete Clustering Algorithm

The complete clustering algorithm called HD\-NDW integrates the solutions ofP\. 1and the Novel Distance Weighting \(NDW\) mechanism for solvingP\. 2\. As described in Algorithm[1](https://arxiv.org/html/2607.05464#alg1), it iteratively updates the data partitions and weights of the distances defined by the Homogeneous Distance \(HD\) metric for data partitioning\. More specifically,Step 1acts as a complete clustering algorithm that learns a data partition, which provides information for updating the weights of distances inStep 2\. This is why we putStep 1beforeStep 2in HD\-NDW\. After reasonable distance weights are learned according to the data partition, the weights are fed back toStep 1for learning more appropriate data partition, and such procedures iterate until convergence\. Time complexity of HD\-NDW is analyzed in Theorem[4](https://arxiv.org/html/2607.05464#Thmtheorem4)\.

Algorithm 1HD\-NDW Clustering AlgorithmInput:Data setSS, numberkkof clusters, distance matricesDD\.

Output:PartitionQ\.

Step 0:Initialize the time\-step byτ=0\\tau=0; InitializeP\(τ\)P^\{\(\\tau\)\}andW\(τ\)W^\{\(\\tau\)\};

Step 1:FixW\(τ\)W^\{\(\\tau\)\}andP\(τ\)P^\{\(\\tau\)\}, iteratively updateQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}by Eq\. \([13](https://arxiv.org/html/2607.05464#S5.E13)\) and updateP\(τ\)P^\{\(\\tau\)\}according toQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}until convergence, obtainQ\(τ\+1\)\\textbf\{Q\}^\{\(\\tau\+1\)\}andP\(τ\+1\)P^\{\(\\tau\+1\)\}; IfQ\(τ\+1\)≠Q\(τ\)\\textbf\{Q\}^\{\(\\tau\+1\)\}\\neq\\textbf\{Q\}^\{\(\\tau\)\}, go toStep 2; Otherwise, stop andOutputQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}\.

Step 2:FixQ\(τ\+1\)\\textbf\{Q\}^\{\(\\tau\+1\)\}andP\(τ\+1\)P^\{\(\\tau\+1\)\}, updateW\(τ\)W^\{\(\\tau\)\}by Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\), obtainW\(τ\+1\)W^\{\(\\tau\+1\)\}; Update the time\-step byτ=τ\+1\\tau=\\tau\+1, go toStep 1;

###### Theorem 4\.

Time complexity of Algorithm[1](https://arxiv.org/html/2607.05464#alg1)isO​\(E​\(k​d​V​n​I\+d​n\+d​V2​k\)\)O\(E\(kdVnI\+dn\+dV^\{2\}k\)\), supposingStep 1needsIIiterations to converge, and the loop ofStep 1and2needsEEiterations to converge\.

###### Proof\.

InStep 1, time complexity for computing the values of a row ofQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}isO​\(k​d​V\)O\(kdV\)because there arekkclusters to be considered, and for each cluster, the distance is computed based on theddintra\-attribute distances stored inDD, and each attribute has a maximum ofVVpossible values\. See the proof of Theorem[3](https://arxiv.org/html/2607.05464#Thmtheorem3)for more details of the computing ofQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}\. Since there arennrows inQ\(τ\)\\textbf\{Q\}^\{\(\\tau\)\}andStep 1repeatsIItimes, the total time complexity ofStep 1isO​\(k​d​V​n​I\)O\(kdVnI\)\.

According to the proof of Lemma[1](https://arxiv.org/html/2607.05464#Thmlemma1), the term∑s=1k−1∑u=s\+1k\(fs​mr​fu​hr\+fu​mr​fs​hr\)/\(fmr​fhr\)\\sum\_\{s=1\}^\{k\-1\}\\sum\_\{u=s\+1\}^\{k\}\(f^\{r\}\_\{sm\}f^\{r\}\_\{uh\}\+f^\{r\}\_\{um\}f^\{r\}\_\{sh\}\)/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)in Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) can be directly computed by1−∑l=1kfl​mr​fl​hr/\(fmr​fhr\)1\-\\sum\_\{l=1\}^\{k\}f^\{r\}\_\{lm\}f^\{r\}\_\{lh\}/\(f^\{r\}\_\{m\}f^\{r\}\_\{h\}\)\. Before the computation, we should first obtain the set of occurrence frequency matricesF=\{F1,F2,…,Fd\}F=\\\{\\textbf\{F\}^\{1\},\\textbf\{F\}^\{2\},\.\.\.,\\textbf\{F\}^\{d\}\\\}whereFr\\textbf\{F\}^\{r\}is ak×vrk\\times v^\{r\}matrix storing the occurrence frequencies ofArA^\{r\}’s possible values in each cluster, and the\(l,m\)\(l,m\)th entry ofFr\\textbf\{F\}^\{r\}isfl​mrf^\{r\}\_\{lm\}\. To obtainFF, theddvalues of each data objectxi\\textbf\{x\}\_\{i\}should be scanned once according to the correspondingqi​l=1q\_\{il\}=1inQ\. Since there arennobjects in total, the time complexity for obtainingFFisO​\(d​n\)O\(dn\)\. It is therefore clear that the time complexity for computing thed​V​\(V−1\)/2dV\(V\-1\)/2weights according to each of thekkclusters using Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) isO​\(d​n\+d​V2​k\)O\(dn\+dV^\{2\}k\)inStep 2\.

Since the loop ofStep 1and2repeatsEEtimes, the time complexity of HD\-NDW isO​\(E​\(k​d​V​n​I\+d​n\+d​V2​k\)\)O\(E\(kdVnI\+dn\+dV^\{2\}k\)\)\. ∎

## 6Experiments

We conduct a series of experiments on various benchmark and real data sets to evaluate the proposed clustering method\. We first describe the experimental settings\. Then, we demonstrate and discuss the experimental results\.

### 6\.1Experimental Settings

#### 6\.1\.1Experimental Design

Five experiments are designed as follows:

- •Clustering Performance of HD\-NDW\.We compare HD\-NDW with various clustering algorithms on mixed, ordinal, and nominal categorical data sets to illustrate the superiority of HD\-NDW\.
- •Effectiveness of HD\.HD is a core component of HD\-NDW\. We compare HD and various distance measures by combining them with the simplestkk\-modes clustering algorithm to illustrate the effectiveness of HD\.
- •Effectiveness of NDW\.NDW is also a core component of HD\-NDW\. We compare HD\-NDW and its non\-weighting version to prove the effectiveness NDW\.
- •Convergence Evaluation\.Convergence curves of HD\-NDW on various data sets are demonstrated to illustrate its effectiveness and fast convergence\.
- •Computational Efficiency Evaluation\.We compare the execution time of various clustering methods on synthetic data sets to illustrate the efficiency of HD\-NDW\.

For all the experiments, the numberkkof the clusters is set at the true numberk∗k^\{\*\}of the clusters according to the data label\. We run all the experiments 50 times and report the average results\.

#### 6\.1\.2Validity Indices

We select the commonly used Adjusted Rand Index \(ARI\)\[[53](https://arxiv.org/html/2607.05464#bib.bib58)\]because it is powerful in discriminating clustering performance\[[50](https://arxiv.org/html/2607.05464#bib.bib59),[16](https://arxiv.org/html/2607.05464#bib.bib60)\]\. Normalized Mutual Information \(NMI\)\[[14](https://arxiv.org/html/2607.05464#bib.bib61)\]\[[27](https://arxiv.org/html/2607.05464#bib.bib45)\]is selected to evaluate clustering performance from the perspective of information theory\[[34](https://arxiv.org/html/2607.05464#bib.bib9)\]\. To make the evaluation comprehensive, the traditional Clustering Accuracy \(CA\)\[[42](https://arxiv.org/html/2607.05464#bib.bib56),[18](https://arxiv.org/html/2607.05464#bib.bib57)\]is also selected\. NMI and CA are in the interval\[0,1\]\[0,1\]and ARI is in the interval\[−1,1\]\[\-1,1\]\. For all these selected validity indices, a higher value indicates a better clustering performance\. We also adopt Wilcoxon signed\-rank test and Bonferroni\-Dunn test\[[11](https://arxiv.org/html/2607.05464#bib.bib79)\]to evaluate the statistical significance of the difference between clustering performance of different methods\. In addition, we compute the averaged Intra\- and Inter\-Cluster Distance \(ICD for short\)\[[3](https://arxiv.org/html/2607.05464#bib.bib42)\]to intuitively demonstrate the cluster discrimination ability of different methods\.

#### 6\.1\.3Counterpart Selection

The most representative partitional clustering algorithms are selected as counterparts for the experiments\. We selectkk\-modes \(KMD\)\[[22](https://arxiv.org/html/2607.05464#bib.bib27)\]because it is the most conventional one\. We select Entropy\-based Categorical data Clustering \(ECC\)\[[40](https://arxiv.org/html/2607.05464#bib.bib29)\]because it is conventional and representative among the entropy\-based clustering algorithms\. We also select attribute Weightingkk\-modes \(WKM\)\[[20](https://arxiv.org/html/2607.05464#bib.bib31)\], Mixed\-attribute Weightingkk\-modes \(MWKM\)\[[6](https://arxiv.org/html/2607.05464#bib.bib33)\], and attribute Weighting and Object\-cluster\-similarity\-based Clustering \(WOC\)\[[28](https://arxiv.org/html/2607.05464#bib.bib36)\]algorithms as another three counterparts\. WKM and MWKM are two representative algorithms in the attribute\-weighting clustering stream, and WOC is the most state\-of\-the\-art one that extends the attribute weighting into subspace\. Space structure\-Based Clustering \(SBC\)\[[49](https://arxiv.org/html/2607.05464#bib.bib75)\], Coupled Data Embedding\-based clustering \(CDE\)\[[31](https://arxiv.org/html/2607.05464#bib.bib77)\], and UNsupervised heTerogeneous couplIng lEarning\-based clustering \(UNTIE\)\[[63](https://arxiv.org/html/2607.05464#bib.bib78)\]are also chosen as the counterparts in the stream of data representation\-based clustering\. SBC has two versions, denoted as SBC\-1 and SBC\-2, whose difference is to adopt the different distance functions only\. For simplicity, we just therefore report the performance of the one with better performance on each data set\. Also, the state\-of\-the\-art Distance Learning\-based Clustering \(DLC\)\[[61](https://arxiv.org/html/2607.05464#bib.bib37)\]algorithm is selected\. Since it is designed for ordinal data only, we first perform the ‘simple coding’ as discussed in Section[2\.1](https://arxiv.org/html/2607.05464#S2.SS1)to encode the nominal attributes of mixed data sets, and then perform DLC for clustering\.

We select categorical data distance measures as counterparts of the proposed HD distance metric\. We select Hamming distance metric\[[5](https://arxiv.org/html/2607.05464#bib.bib39)\]because it is the most commonly used one in categorical data clustering\. We also select Lin’s Similarity Measure \(LSM\)\[[41](https://arxiv.org/html/2607.05464#bib.bib40)\]as a representative for the stream of entropy\-based measures, and Context\-Based Distance Metric \(CBDM\)\[[24](https://arxiv.org/html/2607.05464#bib.bib44)\]as a representative for the stream of context\-based metrics\. We also select three state\-of\-the\-art categorical data distance metrics, i\.e\., Jia’s Distance Metric \(JDM\)\[[27](https://arxiv.org/html/2607.05464#bib.bib45)\], Entropy\-Based Distance Metric \(EBDM\)\[[62](https://arxiv.org/html/2607.05464#bib.bib48)\], and Coupled Metric Similarity \(CMS\)\[[29](https://arxiv.org/html/2607.05464#bib.bib76)\]as counterparts\. We set the parameters of the above\-mentioned counterparts at the values suggested by the corresponding papers\.

#### 6\.1\.4Data Sets

We collect 15 data sets for the experiments, and the data statistics are shown in Table[III](https://arxiv.org/html/2607.05464#S6.T3)\.

TABLE III:Statistics of the 15 utilized data sets\. “\# Attribute” of mixed categorical data sets indicates “\# ordinal attributes \+ \# nominal attributes”Data typeData set\# Instance\# Attribute\# ClassMixedLenses242\+212Assistant722\+23Hayes1322\+23Lym1483\+154Cancer2864\+52Nursery12,9607\+14OrdinalPhoto6643Selection48849Lecturer1,00045Social1,000104Car1,72874NominalSoybean47214Zoo101167Solar32396Voting435162Among the six mixed categorical data sets \(mixed data sets for short\), Lenses, Breast Cancer \(abbreviated as Cancer\), Hayes\-Roth \(abbreviated as Hayes\), Lymphography \(abbreviated as Lym\), and Nursery, are benchmark data sets collected from the UCI Machine Learning Repository \(UCI\-MLR\)111http://archive\.ics\.uci\.edu/ml/datasets\.html\[[13](https://arxiv.org/html/2607.05464#bib.bib54)\], Assistant Evaluation \(abbreviated as Assistant\) is a real mixed categorical data set collected from university questionnaires\. Among the five ordinal data sets, Lecturer Evaluation \(abbreviated as Lecturer\), Social Works \(abbreviated as Social\), and Employee Selection \(abbreviated as Selection\) are benchmark data sets collected from the Weka website222https://www\.cs\.waikato\.ac\.nz/ml/weka/datasets\.html\[[55](https://arxiv.org/html/2607.05464#bib.bib55)\], Photo Evaluation \(abbreviated as Photo\) is a real ordinal data set collected from university questionnaires, and Car Evaluation \(abbreviated as Car\) is a benchmark data set collected from UCI\-MLR\. For all these five ordinal data sets, monotonic correlation exists among all the attributes, i\.e\., an object composed of higher ranked values always ranks higher in comparison with the other objects composed of lower ranked values\[[19](https://arxiv.org/html/2607.05464#bib.bib62)\]\. To utilize such known monotonicity, the original object\-cluster distance is replaced withdist​\(xi,Cl\)=\|dist​\(xi,x0\)−dist​\(xi,x0\)\|\\text\{dist\}\(\\textbf\{x\}\_\{i\},C\_\{l\}\)=\|\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{0\}\)\-\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{0\}\)\|for the measures \(i\.e\., LSM, EBDM, DLC, and HD\) that are capable in distinguishing the order of values, in conducting the clustering experiment in Section[6\.2](https://arxiv.org/html/2607.05464#S6.SS2)\. Note thatx0\\textbf\{x\}\_\{0\}here is a constructed object composed of the lowest ranked value of each attribute\. All the four nominal data sets, i\.e\., Solar Flare \(abbreviated as Solar\), Zoo, Voting Records \(abbreviated as Voting\), and Soybean, are benchmark data sets collected from UCI\-MLR\.

#### 6\.1\.5Initialization of HD\-NDW

InStep 0of the proposed HD\-NDW algorithm, values ofPPandWWshould be initialized\. ForPP, although different initialization strategies can be utilized, we adopt a strategy similar to the random initialization of the conventionalkk\-modes algorithm\. That is, we randomly selectk∗k^\{\*\}objects as modes, and then assign values to thek∗×dk^\{\*\}\\times dvectors ofPPaccordingly\. Taking the data set shown in Table[I](https://arxiv.org/html/2607.05464#S1.T1)as an example, suppose we haveo11=↑o^\{1\}\_\{1\}=\\uparrow,o21=↑↑o^\{1\}\_\{2\}=\\uparrow\\uparrow,o31=↑↑↑o^\{1\}\_\{3\}=\\uparrow\\uparrow\\uparrow,o41=↑↑↑↑o^\{1\}\_\{4\}=\\uparrow\\uparrow\\uparrow\\uparrow,o12=o^\{2\}\_\{1\}=non\-special,o22=o^\{2\}\_\{2\}=vesicles, ando32=o^\{2\}\_\{3\}=chalices\. If the 6th object in Table[I](https://arxiv.org/html/2607.05464#S1.T1)\(i\.e\.x6=\[↑↑↑↑,vesicles\]⊤\\textbf\{x\}\_\{6\}=\[\\uparrow\\uparrow\\uparrow\\uparrow,\\text\{vesicles\}\]^\{\\top\}\) is initialized as the mode of the 2nd cluster, then the corresponding two vectors inP2P\_\{2\}will bep21=\[0,0,0,1\]⊤\\textbf\{p\}\_\{2\}^\{1\}=\[0,0,0,1\]^\{\\top\}andp22=\[0,1,0\]⊤\\textbf\{p\}\_\{2\}^\{2\}=\[0,1,0\]^\{\\top\}, respectively\. ForWW, we uniformly initialize each weight of it to1/\(∑r=1dvr​\(vr−1\)/2\)1/\(\\sum\_\{r=1\}^\{d\}v^\{r\}\(v^\{r\}\-1\)/2\)\. In this way, the sum of all the initialized weights equals to 1, which is equal to the sum of the weights after updating, as the updated weights will be processed using soft\-max \(see the discussions following Eq\. \([18](https://arxiv.org/html/2607.05464#S5.E18)\) for more details\)\. Another purpose of such a uniform initialization is to make the initialized weights have no effect on the learning ofStep 1in Algorithm[1](https://arxiv.org/html/2607.05464#alg1)\. If we randomly initializeWW, inappropriate distance weights will preventStep 1from learning reasonable data partition, which will further influence the subsequent learning iterations\.

### 6\.2Clustering Performance Evaluation of HD\-NDW

TABLE IV:Clustering performance of various clustering algorithms on mixed and ordinal categorical data sets\. The column of ‘Δ\\Delta’ reports the improvements achieved by HD\-NDW in comparison with the best\-performing counterparts on different data sets\. Results of significance tests are shown in Table[VI](https://arxiv.org/html/2607.05464#S6.T6)and Fig\.[4](https://arxiv.org/html/2607.05464#S6.F4)\.IndexData SetKMDECCWKMMWKMSBCWOCCDEUNTIEDLCHD\-NDWΔ\\DeltaARIAssistant0\.111±\\pm0\.060\.133±\\pm0\.090\.113±\\pm0\.080\.138±\\pm0\.090\.153±\\pm0\.040\.194±\\pm0\.080\.131±\\pm0\.060\.152±\\pm0\.040\.152±\\pm0\.090\.330±\\pm0\.0570\.1%Lenses0\.088±\\pm0\.130\.104±\\pm0\.140\.087±\\pm0\.170\.124±\\pm0\.130\.148±\\pm0\.110\.117±\\pm0\.160\.085±\\pm0\.150\.088±\\pm0\.130\.146±\\pm0\.100\.227±\\pm0\.2153\.4%Cancer0\.018±\\pm0\.050\.050±\\pm0\.070\.014±\\pm0\.040\.056±\\pm0\.060\.083±\\pm0\.080\.076±\\pm0\.070\.083±\\pm0\.080\.085±\\pm0\.110\.035±\\pm0\.050\.090±\\pm0\.106\.5%Hayes\-0\.001±\\pm0\.030\.017±\\pm0\.050\.020±\\pm0\.020\.016±\\pm0\.01\-0\.012±\\pm0\.010\.019±\\pm0\.040\.081±\\pm0\.040\.084±\\pm0\.060\.026±\\pm0\.030\.091±\\pm0\.038\.8%Lym0\.108±\\pm0\.040\.194±\\pm0\.040\.075±\\pm0\.050\.131±\\pm0\.050\.127±\\pm0\.070\.163±\\pm0\.060\.193±\\pm0\.030\.197±\\pm0\.050\.200±\\pm0\.060\.195±\\pm0\.03\-2\.4%Nursery0\.054±\\pm0\.020\.072±\\pm0\.100\.083±\\pm0\.110\.058±\\pm0\.020\.017±\\pm0\.010\.002±\\pm0\.000\.053±\\pm0\.020\.084±\\pm0\.020\.115±\\pm0\.080\.133±\\pm0\.0715\.8%Photo0\.102±\\pm0\.060\.121±\\pm0\.090\.100±\\pm0\.080\.140±\\pm0\.090\.186±\\pm0\.050\.158±\\pm0\.090\.115±\\pm0\.070\.115±\\pm0\.090\.267±\\pm0\.070\.318±\\pm0\.0619\.3%Lecturer0\.034±\\pm0\.020\.035±\\pm0\.020\.032±\\pm0\.020\.038±\\pm0\.010\.046±\\pm0\.010\.040±\\pm0\.020\.034±\\pm0\.020\.033±\\pm0\.020\.151±\\pm0\.010\.154±\\pm0\.011\.5%Social0\.043±\\pm0\.020\.059±\\pm0\.020\.043±\\pm0\.010\.047±\\pm0\.020\.093±\\pm0\.020\.036±\\pm0\.020\.068±\\pm0\.020\.071±\\pm0\.020\.108±\\pm0\.000\.112±\\pm0\.013\.2%Selection0\.151±\\pm0\.040\.181±\\pm0\.030\.173±\\pm0\.030\.171±\\pm0\.030\.200±\\pm0\.010\.183±\\pm0\.040\.219±\\pm0\.030\.221±\\pm0\.030\.313±\\pm0\.010\.328±\\pm0\.025\.1%Car0\.025±\\pm0\.040\.058±\\pm0\.050\.026±\\pm0\.040\.031±\\pm0\.020\.027±\\pm0\.030\.035±\\pm0\.030\.019±\\pm0\.050\.023±\\pm0\.060\.112±\\pm0\.020\.128±\\pm0\.0414\.5%Averaged Rank8\.555\.828\.186\.185\.095\.646\.454\.913\.001\.18NMIAssistant0\.152±\\pm0\.070\.182±\\pm0\.100\.160±\\pm0\.100\.172±\\pm0\.100\.184±\\pm0\.050\.262±\\pm0\.090\.159±\\pm0\.070\.188±\\pm0\.060\.212±\\pm0\.110\.390±\\pm0\.0448\.8%Lenses0\.227±\\pm0\.100\.255±\\pm0\.140\.199±\\pm0\.180\.276±\\pm0\.120\.305±\\pm0\.070\.262±\\pm0\.140\.203±\\pm0\.140\.213±\\pm0\.130\.308±\\pm0\.090\.342±\\pm0\.1611\.3%Cancer0\.011±\\pm0\.020\.029±\\pm0\.040\.008±\\pm0\.020\.024±\\pm0\.030\.040±\\pm0\.030\.034±\\pm0\.030\.045±\\pm0\.040\.046±\\pm0\.050\.014±\\pm0\.020\.062±\\pm0\.0337\.1%Hayes0\.019±\\pm0\.040\.032±\\pm0\.050\.026±\\pm0\.020\.033±\\pm0\.030\.003±\\pm0\.010\.043±\\pm0\.060\.087±\\pm0\.030\.086±\\pm0\.050\.032±\\pm0\.030\.103±\\pm0\.0318\.3%Lym0\.168±\\pm0\.040\.243±\\pm0\.040\.130±\\pm0\.050\.188±\\pm0\.050\.170±\\pm0\.040\.231±\\pm0\.060\.237±\\pm0\.040\.243±\\pm0\.050\.223±\\pm0\.050\.258±\\pm0\.035\.9%Nursery0\.059±\\pm0\.020\.103±\\pm0\.130\.105±\\pm0\.130\.103±\\pm0\.030\.032±\\pm0\.020\.006±\\pm0\.000\.056±\\pm0\.020\.101±\\pm0\.030\.117±\\pm0\.110\.162±\\pm0\.0939\.2%Photo0\.143±\\pm0\.060\.177±\\pm0\.090\.151±\\pm0\.100\.180±\\pm0\.100\.221±\\pm0\.050\.222±\\pm0\.110\.181±\\pm0\.080\.200±\\pm0\.100\.339±\\pm0\.030\.373±\\pm0\.0310\.1%Lecturer0\.054±\\pm0\.020\.059±\\pm0\.020\.057±\\pm0\.020\.060±\\pm0\.020\.073±\\pm0\.020\.064±\\pm0\.030\.056±\\pm0\.020\.059±\\pm0\.020\.215±\\pm0\.010\.217±\\pm0\.010\.8%Social0\.065±\\pm0\.020\.086±\\pm0\.020\.060±\\pm0\.020\.068±\\pm0\.020\.131±\\pm0\.020\.059±\\pm0\.020\.094±\\pm0\.020\.088±\\pm0\.010\.167±\\pm0\.000\.168±\\pm0\.010\.2%Selection0\.280±\\pm0\.040\.335±\\pm0\.030\.305±\\pm0\.030\.308±\\pm0\.020\.353±\\pm0\.010\.307±\\pm0\.040\.370±\\pm0\.020\.368±\\pm0\.020\.491±\\pm0\.010\.510±\\pm0\.013\.7%Car0\.047±\\pm0\.020\.121±\\pm0\.070\.062±\\pm0\.050\.064±\\pm0\.030\.071±\\pm0\.040\.079±\\pm0\.060\.091±\\pm0\.070\.106±\\pm0\.060\.219±\\pm0\.010\.228±\\pm0\.013\.9%Averaged Rank9\.005\.558\.456\.275\.555\.645\.644\.553\.361\.00CAAssistant0\.522±\\pm0\.070\.536±\\pm0\.080\.527±\\pm0\.090\.546±\\pm0\.090\.568±\\pm0\.080\.621±\\pm0\.070\.531±\\pm0\.060\.549±\\pm0\.050\.570±\\pm0\.090\.639±\\pm0\.072\.9%Lenses0\.534±\\pm0\.090\.537±\\pm0\.110\.538±\\pm0\.100\.557±\\pm0\.100\.564±\\pm0\.090\.544±\\pm0\.110\.512±\\pm0\.100\.513±\\pm0\.070\.561±\\pm0\.070\.588±\\pm0\.134\.1%Cancer0\.564±\\pm0\.060\.586±\\pm0\.090\.536±\\pm0\.070\.614±\\pm0\.080\.624±\\pm0\.110\.629±\\pm0\.100\.630±\\pm0\.100\.630±\\pm0\.100\.584±\\pm0\.080\.651±\\pm0\.093\.4%Hayes0\.384±\\pm0\.030\.414±\\pm0\.060\.439±\\pm0\.050\.416±\\pm0\.020\.354±\\pm0\.020\.413±\\pm0\.080\.442±\\pm0\.050\.452±\\pm0\.040\.446±\\pm0\.050\.487±\\pm0\.057\.7%Lym0\.462±\\pm0\.050\.512±\\pm0\.040\.433±\\pm0\.070\.482±\\pm0\.060\.505±\\pm0\.060\.551±\\pm0\.050\.519±\\pm0\.040\.550±\\pm0\.050\.538±\\pm0\.060\.601±\\pm0\.079\.2%Nursery0\.378±\\pm0\.040\.368±\\pm0\.070\.395±\\pm0\.090\.359±\\pm0\.030\.323±\\pm0\.030\.292±\\pm0\.020\.366±\\pm0\.000\.397±\\pm0\.010\.404±\\pm0\.040\.423±\\pm0\.064\.8%Photo0\.511±\\pm0\.070\.524±\\pm0\.080\.517±\\pm0\.090\.553±\\pm0\.090\.557±\\pm0\.050\.584±\\pm0\.090\.501±\\pm0\.060\.500±\\pm0\.090\.668±\\pm0\.060\.698±\\pm0\.054\.4%Lecturer0\.335±\\pm0\.030\.328±\\pm0\.030\.319±\\pm0\.030\.322±\\pm0\.030\.339±\\pm0\.020\.331±\\pm0\.040\.319±\\pm0\.030\.338±\\pm0\.050\.455±\\pm0\.040\.465±\\pm0\.042\.2%Social0\.370±\\pm0\.030\.384±\\pm0\.030\.371±\\pm0\.020\.372±\\pm0\.030\.421±\\pm0\.020\.372±\\pm0\.030\.391±\\pm0\.020\.409±\\pm0\.020\.414±\\pm0\.020\.453±\\pm0\.047\.6%Selection0\.365±\\pm0\.040\.372±\\pm0\.040\.373±\\pm0\.030\.369±\\pm0\.040\.386±\\pm0\.010\.427±\\pm0\.050\.407±\\pm0\.030\.437±\\pm0\.040\.505±\\pm0\.030\.489±\\pm0\.03\-3\.2%Car0\.370±\\pm0\.040\.384±\\pm0\.060\.375±\\pm0\.070\.369±\\pm0\.030\.357±\\pm0\.040\.366±\\pm0\.050\.389±\\pm0\.050\.390±\\pm0\.050\.437±\\pm0\.040\.453±\\pm0\.063\.5%Averaged Rank8\.186\.557\.456\.915\.645\.456\.324\.413\.001\.09

TABLE V:Clustering performance of various clustering algorithms on nominal data sets\. The column of ‘Δ\\Delta’ reports the improvements achieved by HD\-NDW in comparison with the best\-performing counterparts on different data sets\.IndexData SetKMDECCWKMMWKMSBCWOCCDEUNTIEHD\-NDWΔ\\DeltaARISolar0\.223±\\pm0\.060\.194±\\pm0\.060\.132±\\pm0\.090\.199±\\pm0\.060\.126±\\pm0\.030\.229±\\pm0\.100\.237±\\pm0\.080\.255±\\pm0\.100\.318±\\pm0\.0824\.8%Zoo0\.628±\\pm0\.180\.530±\\pm0\.150\.651±\\pm0\.180\.594±\\pm0\.180\.413±\\pm0\.140\.618±\\pm0\.130\.741±\\pm0\.110\.748±\\pm0\.130\.721±\\pm0\.15\-3\.6%Voting0\.520±\\pm0\.020\.544±\\pm0\.010\.535±\\pm0\.000\.542±\\pm0\.010\.560±\\pm0\.030\.537±\\pm0\.000\.534±\\pm0\.080\.558±\\pm0\.070\.564±\\pm0\.000\.6%Soybean0\.688±\\pm0\.220\.659±\\pm0\.160\.772±\\pm0\.210\.740±\\pm0\.220\.816±\\pm0\.110\.788±\\pm0\.210\.821±\\pm0\.190\.829±\\pm0\.170\.803±\\pm0\.21\-3\.1%Averaged Rank6\.757\.006\.256\.255\.755\.253\.751\.752\.25NMISolar0\.300±\\pm0\.050\.278±\\pm0\.060\.218±\\pm0\.100\.271±\\pm0\.060\.196±\\pm0\.030\.331±\\pm0\.090\.319±\\pm0\.080\.348±\\pm0\.100\.408±\\pm0\.0817\.2%Zoo0\.753±\\pm0\.090\.700±\\pm0\.060\.779±\\pm0\.080\.745±\\pm0\.080\.595±\\pm0\.080\.786±\\pm0\.050\.810±\\pm0\.050\.808±\\pm0\.080\.809±\\pm0\.08\-0\.1%Voting0\.448±\\pm0\.020\.476±\\pm0\.010\.452±\\pm0\.010\.473±\\pm0\.010\.473±\\pm0\.000\.475±\\pm0\.000\.462±\\pm0\.070\.458±\\pm0\.080\.489±\\pm0\.002\.7%Soybean0\.805±\\pm0\.150\.771±\\pm0\.100\.849±\\pm0\.120\.847±\\pm0\.130\.856±\\pm0\.060\.885±\\pm0\.110\.892±\\pm0\.110\.902±\\pm0\.100\.897±\\pm0\.11\-0\.6%Averaged Rank7\.006\.256\.756\.506\.753\.503\.503\.251\.50CASolar0\.482±\\pm0\.050\.442±\\pm0\.050\.400±\\pm0\.060\.462±\\pm0\.050\.400±\\pm0\.040\.483±\\pm0\.070\.483±\\pm0\.070\.498±\\pm0\.060\.540±\\pm0\.058\.3%Zoo0\.676±\\pm0\.130\.623±\\pm0\.100\.703±\\pm0\.120\.647±\\pm0\.130\.554±\\pm0\.090\.669±\\pm0\.100\.758±\\pm0\.080\.778±\\pm0\.090\.760±\\pm0\.10\-2\.4%Voting0\.861±\\pm0\.010\.869±\\pm0\.010\.852±\\pm0\.000\.868±\\pm0\.000\.875±\\pm0\.000\.867±\\pm0\.000\.864±\\pm0\.040\.872±\\pm0\.050\.876±\\pm0\.000\.1%Soybean0\.791±\\pm0\.170\.773±\\pm0\.140\.837±\\pm0\.170\.811±\\pm0\.170\.874±\\pm0\.100\.821±\\pm0\.170\.874±\\pm0\.140\.876±\\pm0\.130\.849±\\pm0\.16\-3\.1%Averaged Rank6\.507\.006\.756\.255\.255\.504\.001\.752\.00

TABLE VI:Wilcoxon signed\-rank test on the performance of HD\-NDW vs\. DLC and HD\-NDW vs\. UNTIE\. The symbol “\+” indicates that HD\-NDW is significantly different from a certain counterpart for the two\-tailed Wilcoxon signed\-rank test at confidence interval 99% \(i\.e\.,α\\alpha= 0\.01\)\.IndexHD\-NDW vs\. DLCHD\-NDW vs\. UNTIEARI\+\+NMI\+\+CA\+\+![Refer to caption](https://arxiv.org/html/2607.05464v1/x4.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x5.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x6.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x7.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x8.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x9.png)

\(a\) Test for recent\-five\-year methods\.

![Refer to caption](https://arxiv.org/html/2607.05464v1/x10.png)

\(b\) Test for all the compared methods\.

Figure 4:Bonferroni\-Dunn \(BD\) test on the performance of \(a\) methods proposed in recent five years, and \(b\) all the compared methods\. Critical Difference \(CD\) for the two\-tailed BD tests in \(a\) at confidence interval 95% \(α\\alpha= 0\.05\) and 90% \(α\\alpha= 0\.1\) are 2\.05 and 1\.86, respectively\. CD for the two\-tailed BD tests in \(b\) at confidence interval 95% \(α\\alpha= 0\.05\) and 90% \(α\\alpha= 0\.1\) are 3\.58 and 3\.28, respectively\. The counterparts rank outside the CD intervals are believed to be significantly different from HD\-NDW\.Since a key working principle of HD\-NDW is to convert the nominal attributes into ordinal ones for more reasonable distance measurement, the superiority of HD\-NDW will be more prominent on mixed and ordinal data sets\. In order to conduct a more targeted evaluation, we report the clustering performance on mixed and ordinal data sets in Table[IV](https://arxiv.org/html/2607.05464#S6.T4)\. To ensure the completeness of the evaluation, the performance on nominal data sets is reported in Table[V](https://arxiv.org/html/2607.05464#S6.T5)\. The best and second\-best results are highlighted using boldface and underline, respectively\. Improvements achieved by HD\-NDW in comparison with the best\-performing counterparts on different data sets are reported in the column of ‘Δ\\Delta’\. For each data set, the compared methods are ranked according to their performance, and the averaged rank of each method is reported\. From the results shown in Table[IV](https://arxiv.org/html/2607.05464#S6.T4)and[V](https://arxiv.org/html/2607.05464#S6.T5), we have the following observations:

- •HD\-NDW obviously outperforms the other counterparts on mixed categorical data sets, because the homogeneous distance definition and the distance weighting mechanism may have desired effects on mixed categorical data sets\.
- •HD\-NDW and DLC significantly outperform the other counterparts on ordinal data sets, because they take into account the intra\- and inter\-attribute order relationship, by which the learned distances are more appropriate for clustering\.
- •In the comparison on nominal data sets, superiority of HD\-NDW is not as significant as on mixed and ordinal data sets because the HD component that uniformly defines distances for ordinal and nominal attributes will not have desired impact when processing nominal data\. Nevertheless, since NDW still acts in booting the clustering performance, HD\-NDW is still competitive in comparison with the state\-of\-the\-art UNTIE, and obviously outperforms the others\.
- •Although UNTIE is not specially designed for representing data set with ordinal attributes, it still shows strong data representation ability, because it performs the best in comparison with the counterparts except the two methods \(i\.e\., DLC and HD\-NDW\) that contain specially designed mechanisms for exploiting the information embedded in ordinal attributes\. As for the performance on nominal data sets, UNTIE performs the best in general, while HD\-NDW is still very competitive\.

#### 6\.2\.1Significance Test

According to the averaged rank shown in Table[IV](https://arxiv.org/html/2607.05464#S6.T4), UNTIE and DLC are clearly the two most competitive counterparts\. We conduct significance test using Wilcoxon signed\-rank test and report the results in Table[VI](https://arxiv.org/html/2607.05464#S6.T6)\. It can be seen that even at 99% confidence interval, HD\-NDW is still significantly better than the two counterparts in terms of all three validity indices\.

To intuitively compare the proposed HD\-NDW with the other counterparts, we further perform Bonferroni\-Dunn test\[[11](https://arxiv.org/html/2607.05464#bib.bib79)\]on the performance of different methods and visualize the results in Fig\.[4](https://arxiv.org/html/2607.05464#S6.F4)\. The counterparts rank outside the Critical Difference \(CD\) intervals are believed to be significantly different from HD\-NDW\. It can be observed from Fig\.[4](https://arxiv.org/html/2607.05464#S6.F4)\(a\) that HD\-NDW is significantly better than almost all five methods proposed in recent five years at confidence interval 90%\. In comparison with all nine counterparts in Fig\.[4](https://arxiv.org/html/2607.05464#S6.F4)\(b\), HD\-NDW is still significantly better than eight counterparts at confidence interval 90%\. Although HD\-NDW is not significantly better than DLC, HD\-NDW is capable in processing any\-type categorical data, while DLC is designed for ordinal data only, which cannot be directly used for mixed data and is incompetent for nominal data\. Therefore, HD\-NDW also demonstrates superiority in comparison with DLC in terms of availability for nominal data clustering\.

#### 6\.2\.2Visualization of Data Representation

![Refer to caption](https://arxiv.org/html/2607.05464v1/x11.png)

UNTIE Representation

![Refer to caption](https://arxiv.org/html/2607.05464v1/x12.png)

DLC Representation

![Refer to caption](https://arxiv.org/html/2607.05464v1/x13.png)

HD\-NDW Representation

Figure 5:t\-SNE visualization of the representations produced by UNTIE, DLC, and HD\-NDW on Assistant data set\. The three types of markers indicate data objects belonging to different true clusters\.To intuitively compare the reasonableness of the learned representation or distances of the three best performing methods, i\.e\., UNTIE, DLC, and HD\-NDW, we visualize their representations in Fig\.[5](https://arxiv.org/html/2607.05464#S6.F5)by converting them into two\-dimensional points using t\-Distributed Stochastic Neighbor Embedding \(t\-SNE\)\[[43](https://arxiv.org/html/2607.05464#bib.bib80)\]\. Since DLC and HD\-NDW are not representation\-based methods, we first use them to learn intra\-attribute distances, and then encode the data values using the learned distances for representation\. Since the distances learned by DLC satisfydist​\(oa,ob\)\+dist​\(ob,oc\)=dist​\(oa,oc\)\\text\{dist\}\(o\_\{a\},o\_\{b\}\)\+\\text\{dist\}\(o\_\{b\},o\_\{c\}\)=\\text\{dist\}\(o\_\{a\},o\_\{c\}\)fora<b<ca<b<cora\>b\>ca\>b\>c, we directly encode the possible values byo1=0o\_\{1\}=0,o2=dist​\(o1,o2\)o\_\{2\}=\\text\{dist\}\(o\_\{1\},o\_\{2\}\),o3=dist​\(o1,o3\)o\_\{3\}=\\text\{dist\}\(o\_\{1\},o\_\{3\}\), and so on, which will not twist the distances learned by DLC\. For the distances learned by HD\-NDW, we encode a possible value using the distances between it and all the intra\-attribute possible values to preserve the information of the learned distances\. For example, for an attribute with possible values \{oao\_\{a\},obo\_\{b\},oco\_\{c\}\}, the valueobo\_\{b\}is encoded into a vector\[dist​\(oa,ob\),dist​\(ob,ob\),dist​\(oc,ob\)\]⊤\[\\text\{dist\}\(o\_\{a\},o\_\{b\}\),\\text\{dist\}\(o\_\{b\},o\_\{b\}\),\\text\{dist\}\(o\_\{c\},o\_\{b\}\)\]^\{\\top\}by the HD\-NDW learned distance metric\. Note that the HD\-NDW distance here is the one defined by HD multiplied by the corresponding distance weight learned by HD\-NDW\.

It can be observed that the true clusters in the HD\-NDW\-represented data set are obviously more separable in comparison with UNTIE and DLC\. The reason should be that Assistant is a mixed categorical data set that is composed of nominal and ordinal attributes\. For this kind of data, UNTIE is unable to take into account the order information embedded in ordinal attributes, while DLC is unsuitable for learning distances of nominal attributes\.

#### 6\.2\.3Visualization of Cluster Discrimination

![Refer to caption](https://arxiv.org/html/2607.05464v1/x14.png)

Figure 6:Gray scale maps of the ICD matrices produced by UNTIE, DLC, and HD\-NDW on Assistant data set\. Darker on the main diagonal and lighter on the other locations indicate a better distance metric\.Averaged ICD computed based on the true cluster labels of a data set can intuitively indicate the discrimination ability of a distance metric\. According to\[[3](https://arxiv.org/html/2607.05464#bib.bib42)\], averaged ICD between two clustersClC\_\{l\}andCtC\_\{t\}withnln\_\{l\}andntn\_\{t\}data objects, respectively, is computed by∑xi∈Cl∑xj∈Ctdist​\(xi,xj\)/\(nl​nt\)\\sum\_\{\\textbf\{x\}\_\{i\}\\in C\_\{l\}\}\\sum\_\{\\textbf\{x\}\_\{j\}\\in C\_\{t\}\}\\text\{dist\}\(\\textbf\{x\}\_\{i\},\\textbf\{x\}\_\{j\}\)/\(n\_\{l\}n\_\{t\}\)\. Whenl=tl=t, it computes the averaged intra\-attribute distance; otherwise, it computes the averaged inter\-attribute distance\. Since different distance metrics may have different scales, computing the multiple relationship between the averaged intra\- and inter\-cluster distances is a feasible solution\[[27](https://arxiv.org/html/2607.05464#bib.bib45)\]to fairly compare the discrimination ability of different metrics\. Therefore, we pre\-process the ICD matrix of each distance metric by dividing all the values in the matrix by the minimum value in this matrix\. Then we visualize the pre\-processed ICD matrices as gray scale maps in Fig\.[6](https://arxiv.org/html/2607.05464#S6.F6)\. ICD matrix of a better distance metric should be darker on the main diagonal and lighter on the other locations, which indicates smaller averaged intra\-cluster distances and larger averaged inter\-cluster distances, respectively\. From Fig\.[6](https://arxiv.org/html/2607.05464#S6.F6), it is clear that HD\-NDW has better cluster discrimination ability than UNTIE and DLC\.

### 6\.3Effectiveness Evaluation of HD

A1A^\{1\}

Hamming

![Refer to caption](https://arxiv.org/html/2607.05464v1/x15.png)

LSM

![Refer to caption](https://arxiv.org/html/2607.05464v1/x16.png)

CBDM

![Refer to caption](https://arxiv.org/html/2607.05464v1/x17.png)

CMS

![Refer to caption](https://arxiv.org/html/2607.05464v1/x18.png)

EBDM

![Refer to caption](https://arxiv.org/html/2607.05464v1/x19.png)

DLC

![Refer to caption](https://arxiv.org/html/2607.05464v1/x20.png)

HD

![Refer to caption](https://arxiv.org/html/2607.05464v1/x21.png)

HD\-NDW

![Refer to caption](https://arxiv.org/html/2607.05464v1/x22.png)

A2A^\{2\}

![Refer to caption](https://arxiv.org/html/2607.05464v1/x23.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x24.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x25.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x26.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x27.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x28.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x29.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x30.png)

Figure 7:Gray scale maps of the intra\-attribute distance matrices of the two ordinal attributes of Assistant data set produced by various distance metrics\.In Fig\.[7](https://arxiv.org/html/2607.05464#S6.F7), we visualize the intra\-attribute distances produced by different distance measures to intuitively compare them\. JDM is not compared in Fig\.[7](https://arxiv.org/html/2607.05464#S6.F7)because it directly measures object\-cluster distance and does not produce intra\-attribute distances\. The produced distances are first normalized into the interval \[0,1\] using min\-max scaling, and then the normalized distances are visualized by converting them into corresponding gray scale pixels\. A lighter pixel represents a larger distance between two possible values, and a pure black pixel represents a distance value of 0\. In Fig\.[7](https://arxiv.org/html/2607.05464#S6.F7), the pixel located at themmth column andhhth row of a gray scale map represents the distance between themmth andhhth possible values of the corresponding attribute\. In general, two possible values with larger order difference should have larger distance, and thus the pixels should be darker on the main diagonal, and lighter towards the upper right and lower left corners in the gray scale maps\.

It can be observed that Hamming distance is completely incapable in distinguishing the distances between different possible values\. Although CBDM and CMS exploits more context information for distance measurement, they cannot reveal the order relationship among possible values of ordinal attributes\. Obviously, the distances produced by LSM, EBDM, DLC, HD, and HD\-NDW are consistent with the order relationship among possible values of the two ordinal attributes\. Since the distances produced by HD\-NDW is the weighted version of the distances produced by HD, gray scale maps of HD and HD\-NDW are different in Fig\.[7](https://arxiv.org/html/2607.05464#S6.F7), but they both reflect the order relationship\.

![Refer to caption](https://arxiv.org/html/2607.05464v1/x31.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x32.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x33.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x34.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x35.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x36.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x37.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x38.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x39.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x40.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x41.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x42.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x43.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x44.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x45.png)

Figure 8:Clustering performance of various distance measures on mixed, ordinal, and nominal data sets, where a better measure yields a higher value\.Fig\.[8](https://arxiv.org/html/2607.05464#S6.F8)compares clustering performance of different distance measures and illustrates that even not weighted by NDW, distance measured using HD is still very competent\. More detailed observations are provided below:

- •HD outperforms the other counterparts on mixed data sets because it is the only one that can measure intra\-attribute distances of nominal and ordinal attributes in a homogeneous way\. HD outperforms the other counterparts on ordinal data sets because it preserves the order relationship among ordered possible values\.
- •On Zoo, Voting, Cancer, and Lym data sets, performance of HD is competitive but cannot be obviously better than the others\. This may be because that the above\-mentioned four data sets are composed of more nominal attributes, which weakens the advantages of HD accordingly\.
- •ARI performance of CBDM is exactly 0 on Lenses, Nursery, and Car data sets because these data sets are composed of independent attributes and CBDM fails in measuring distances for such data sets\.

### 6\.4Effectiveness Evaluation of NDW

![Refer to caption](https://arxiv.org/html/2607.05464v1/x46.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x47.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x48.png)

Figure 9:Clustering performance of HD\-NDW and its version without NDW \(non\-NDW for short\) on mixed, ordinal, and nominal data sets\. A higher value indicates a better clustering performance\.Clustering performance of the original version of HD\-NDW and the version without NDW \(abbreviated as non\-NDW\) is demonstrated in Fig\.[9](https://arxiv.org/html/2607.05464#S6.F9)\. By comparing them, effectiveness of the NDW mechanism can be empirically proved\.

It can be observed that HD\-NDW performs better than the non\-NDW version on all the data sets, which indicates that the NDW mechanism does optimize the distance weights during the clustering of HD\-NDW to obtain better clustering results\. It can also be observed that HD\-NDW does not outperform non\-NDW a lot on Lenses, Voting and Soybean data sets\. This may be because most attributes of these three data sets have only two possible values, and for such attributes, there is only one intra\-attribute distance to be weighted during clustering, which makes NDW degrades into a conventional attribute weighting mechanism, and thus obscures the merits of NDW\.

### 6\.5Convergence Evaluation

![Refer to caption](https://arxiv.org/html/2607.05464v1/x49.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x50.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x51.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x52.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x53.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x54.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x55.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x56.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x57.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x58.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x59.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x60.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x61.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x62.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x63.png)

Figure 10:Convergence curves of HD\-NDW on mixed, ordinal, and nominal data sets\. The circles indicate the moments that Step 2 of Algorithm[1](https://arxiv.org/html/2607.05464#alg1)is triggered, and the boxes indicate the moments of convergence of Algorithm[1](https://arxiv.org/html/2607.05464#alg1)\.We plot the convergence curves of HD\-NDW on each data set in Fig\.[10](https://arxiv.org/html/2607.05464#S6.F10)\. Specifically, after each iteration ofStep 1in Algorithm[1](https://arxiv.org/html/2607.05464#alg1), ‘No\. of Iteration’ is added by 1, and the current ‘Error’ \(i\.e\., the current value of objective function\) is plotted\. WhenStep 1converges andStep 2is triggered, the current ‘Error’ is marked by a circle\. When the whole algorithm converges, the current ‘Error’ is marked by a box\.

It can be seen that HD\-NDW converges within 6 \- 22 iterations on different data sets, which is very fast for learning a large number \(i\.e\.∑rdvr​\(vr−1\)/2\\sum\_\{r\}^\{d\}v^\{r\}\(v^\{r\}\-1\)/2\) of intra\-attribute distance weights\. Moreover, the convergence curves are monotonically decreasing, and ‘Error’ decreases sharply after updating the distance weights, which clearly illustrates the effectiveness of HD\-NDW\.

In our experiments, since the true numberk∗k^\{\*\}of the clusters is utilized, partition learned byStep 1is relatively reasonable, which offers useful information for learningWWinStep 2\. This would be the reason whyStep 2is always triggered 2 \- 3 times for different data sets\.

### 6\.6Computational Efficiency Evaluation

![Refer to caption](https://arxiv.org/html/2607.05464v1/x64.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x65.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x66.png)

![Refer to caption](https://arxiv.org/html/2607.05464v1/x67.png)

Figure 11:Execution time of various clustering algorithms w\.r\.t\. number of objects \(nn\), number of attributes \(dd\), number of possible values per attribute \(VV\), and number of clusters \(kk\)\.We randomly generate synthetic categorical data sets to evaluate the computational efficiency of different clustering methods in terms of four data factors: \(1\) number of data objects \(nn\), \(2\) number of attributes \(dd\), \(3\) number of possible values per attribute \(VV\), and number of clusters \(kk\)\. Synthetic data sets are generated by increasing the value of one factor and fixing the other three factors at the default values\. The default values are set atn=10​kn=10k,d=10d=10,V=3V=3, andk=2k=2\. The value ranges for increasing each factor are set atn=\{10​k,20​k,…,100​k\}n=\\\{10k,20k,\.\.\.,100k\\\},d=\{10,20,…,100\}d=\\\{10,20,\.\.\.,100\\\},V=\{3,10,20,…,90\}V=\\\{3,10,20,\.\.\.,90\\\}, andk=\{2,4,…,20\}k=\\\{2,4,\.\.\.,20\\\}\. As HD\-NDW is proposed for mixed categorical data clustering, we let it treat each generated data set as comprisingd/2d/2nominal andd/2d/2ordinal attributes in this experiment\. Since the data representation learning of SBC, CDE, UNTIE, and the distance computation of HD\-NDW are necessarily processed for clustering, their execution time is counted in for comparison\. We plot the execution time of different methods in terms of the four data factors in Fig\.[11](https://arxiv.org/html/2607.05464#S6.F11)\. It can be observed that the computation cost of HD\-NDW has approximately linear relation withnnandkk, which are consistent with the time complexity analysis in Section[4\.3](https://arxiv.org/html/2607.05464#S4.SS3)and[5\.3](https://arxiv.org/html/2607.05464#S5.SS3)\.

In comparison with the state\-of\-the\-art methods \(i\.e\., UNTIE and DLC\), it can be observed that the trends and values of the computation cost of HD\-NDW and DLC are almost the same in terms ofnnandkk\. Furthermore, HD\-NDW has lower computation cost than UNTIE in terms ofnn\. The computation cost of HD\-NDW and DLC has higher increasing rate than UNTIE overkk, because HD\-NDW and DLC connect the distance learning with the target clustering task, and thus have better clustering performance in general as shown in Table[IV](https://arxiv.org/html/2607.05464#S6.T4)\. Sincekkis usually a very small value from the practical point of view,kkwill not have a big impact on the efficiency of HD\-NDW\. Moreover, although the computation cost of HD\-NDW has higher increasing rate overddandVV, the computations \(e\.g\., the computation of each value inDD, and the computation of each value inWW\) that are related to these two factors are independent and can be easily parallelized for acceleration\.

In summary, HD\-NDW does not bring much extra computation cost in comparison with the state\-of\-the\-art methods, and its computation cost has a linear relation withnn, which is generally the most concerned factor in terms of the computational efficiency of a clustering method\.

## 7Conclusion

In this paper, we have proposed HD intra\-attribute distance definition and NDW distance weighting mechanism, both of which are utilized to present HD\-NDW clustering algorithm for data clustering with nominal and ordinal attributes\. HD is formed based on the intrinsic connection of ordinal and nominal attributes, and can therefore define their intra\-attribute distances in a homogeneous way\. In the clustering process of HD\-NDW, NDW novelly quantifies and iteratively updates the weights of intra\-attribute distances defined by HD according to the present data partition, thereby ensuring an effective learning of the importance of intra\-attribute distances for searching optimal clustering results\. It turns out that HD\-NDW is capable of clustering categorical data composed of any combination of nominal and ordinal attributes\. Extensive experimental results have demonstrated that HD\-NDW always converges quickly and has superior clustering performance in comparison with the existing counterparts\.

## References

- \[1\]A\. Agresti\(2003\)Categorical data analysis\.John Wiley & Sons\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[2\]A\. Agresti\(2010\)Analysis of ordinal categorical data\.John Wiley & Sons\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p3.1)\.
- \[3\]A\. Ahmad and L\. Dey\(2007\)A method to compute distance between two categorical values of same attribute in unsupervised learning for categorical data set\.Pattern Recognition Letters28\(1\),pp\. 110–118\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11),[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2),[§6\.2\.3](https://arxiv.org/html/2607.05464#S6.SS2.SSS3.p1.6)\.
- \[4\]M\. Alamuri, B\. R\. Surampudi, and A\. Negi\(2014\)A survey of distance/similarity measures for categorical data\.InProceedings of the 2014 International Joint Conference on Neural Networks,pp\. 1907–1914\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[5\]P\. Arabie, N\. D\. Baier, C\. F\. Critchley, and M\. Keynes\(2006\)Studies in classification, data analysis, and knowledge organization\.Cited by:[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1)\.
- \[6\]L\. Bai, J\. Liang, C\. Dang, and F\. Cao\(2011\)A novel attribute weighting algorithm for clustering high\-dimensional categorical data\.Pattern Recognition44\(12\),pp\. 2843–2861\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1),[§1](https://arxiv.org/html/2607.05464#S1.p5.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.05464#S5.SS2.p1.18),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[7\]G\. H\. Ball and D\. J\. Hall\(1967\)A clustering technique for summarizing multivariate data\.Behavioral Science12\(2\),pp\. 153–155\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[8\]S\. Boriah, V\. Chandola, and V\. Kumar\(2008\)Similarity measures for categorical data: a comparative evaluation\.InProceedings of the 2008 SIAM International Conference on Data Mining,pp\. 243–254\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[9\]E\. Y\. Chan, W\. K\. Ching, M\. K\. Ng, and J\. Z\. Huang\(2004\)An optimization algorithm for clustering using weighted dissimilarity measures\.Pattern Recognition37\(5\),pp\. 943–952\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1),[§1](https://arxiv.org/html/2607.05464#S1.p5.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.05464#S5.SS2.p1.18)\.
- \[10\]Y\. Cheung and H\. Jia\(2013\)Categorical\-and\-numerical\-attribute data clustering based on a unified similarity metric without knowing cluster number\.Pattern Recognition46\(8\),pp\. 2228–2238\.Cited by:[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2)\.
- \[11\]J\. Demšar\(2006\)Statistical comparisons of classifiers over multiple data sets\.Journal of Machine Learning Research7\(1\),pp\. 1–30\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2),[§6\.2\.1](https://arxiv.org/html/2607.05464#S6.SS2.SSS1.p2.1)\.
- \[12\]T\. R\. dos Santos and L\. E\. Zárate\(2015\)Categorical data clustering: what similarity measure to recommend?\.Expert Systems with Applications42\(3\),pp\. 1247–1260\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[13\]D\. Dua and E\. Karra Taniskidou\(2017\)UCI machine learning repository\.University of California, Irvine, School of Information and Computer Sciences\.External Links:[Link](http://archive.ics.uci.edu/ml)Cited by:[§6\.1\.4](https://arxiv.org/html/2607.05464#S6.SS1.SSS4.p2.2)\.
- \[14\]P\. A\. Estévez, M\. Tesmer, C\. A\. Perez, and J\. M\. Zurada\(2009\)Normalized mutual information feature selection\.IEEE Transactions on Neural Networks20\(2\),pp\. 189–201\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[15\]V\. Garro and A\. Giachetti\(2015\)Scale space graph representation and kernel matching for non rigid and textured 3d shape retrieval\.IEEE Transactions on Pattern Analysis and Machine Intelligence38\(6\),pp\. 1258–1271\.Cited by:[§4\.1](https://arxiv.org/html/2607.05464#S4.SS1.p1.1)\.
- \[16\]A\. J\. Gates and Y\. Ahn\(2017\)The impact of random models on clustering similarity\.The Journal of Machine Learning Research18\(1\),pp\. 3049–3076\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[17\]C\. Gentile, S\. Li, and G\. Zappella\(2014\)Online clustering of bandits\.InProceedings of the 31st International Conference on International Conference on Machine Learning,pp\. 757–765\.Cited by:[§5](https://arxiv.org/html/2607.05464#S5.p2.2)\.
- \[18\]X\. He, D\. Cai, and P\. Niyogi\(2005\)Laplacian score for feature selection\.InProceedings of the 18th International Conference on Neural Information Processing Systems,pp\. 507–514\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[19\]Q\. Hu, W\. Pan, L\. Zhang, D\. Zhang, Y\. Song, M\. Guo, and D\. Yu\(2012\)Feature selection for monotonic classification\.IEEE Transactions on Fuzzy Systems20\(1\),pp\. 69–81\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p4.1),[§6\.1\.4](https://arxiv.org/html/2607.05464#S6.SS1.SSS4.p2.2)\.
- \[20\]J\. Z\. Huang, M\. K\. Ng, H\. Rong, and Z\. Li\(2005\)Automated variable weighting in k\-means type clustering\.IEEE Transactions on Pattern Analysis and Machine Intelligence27\(5\),pp\. 657–668\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1),[§1](https://arxiv.org/html/2607.05464#S1.p5.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p2.1),[§5\.2](https://arxiv.org/html/2607.05464#S5.SS2.p1.18),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[21\]Z\. Huang\(1997\)Clustering large data sets with mixed numeric and categorical values\.InProceedings of the First Pacific\-Asia Conference on Knowledge Discovery and Data Mining,pp\. 21–34\.Cited by:[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2)\.
- \[22\]Z\. Huang\(1998\)Extensions to the k\-means algorithm for clustering large data sets with categorical values\.Data Mining and Knowledge Discovery2\(3\),pp\. 283–304\.Cited by:[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[23\]D\. Ienco, R\. G\. Pensa, and R\. Meo\(2009\)Context\-based distance learning for categorical data clustering\.InProceedings of the Eighth International Symposium on Intelligent Data Analysis,pp\. 83–94\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1)\.
- \[24\]D\. Ienco, R\. G\. Pensa, and R\. Meo\(2012\)From context to distance: learning dissimilarity for categorical data clustering\.ACM Transactions on Knowledge Discovery from Data6\(1\),pp\. 1–25\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1)\.
- \[25\]A\. K\. Jain, M\. N\. Murty, and P\. J\. Flynn\(1999\)Data clustering: a review\.ACM Computing Surveys31\(3\),pp\. 264–323\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[26\]A\. K\. Jain\(2010\)Data clustering: 50 years beyond k\-means\.Pattern Recognition Letters31\(8\),pp\. 651 – 666\.External Links:ISSN 0167\-8655,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.patrec.2009.09.011)Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[27\]H\. Jia, Y\. Cheung, and J\. Liu\(2016\)A new distance metric for unsupervised learning of categorical data\.IEEE Transactions on Neural Networks and Learning Systems27\(5\),pp\. 1065–1079\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11),[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1),[§6\.2\.3](https://arxiv.org/html/2607.05464#S6.SS2.SSS3.p1.6)\.
- \[28\]H\. Jia and Y\. Cheung\(2018\)Subspace clustering of categorical and numerical data with an unknown number of clusters\.IEEE Transactions on Neural Networks and Learning Systems29\(8\),pp\. 3308–3325\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1),[§1](https://arxiv.org/html/2607.05464#S1.p5.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p2.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[29\]S\. Jian, L\. Cao, K\. Lu, and H\. Gao\(2018\)Unsupervised coupled metric similarity for non\-iid categorical data\.IEEE Transactions on Knowledge and Data Engineering30\(9\),pp\. 1810–1823\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1)\.
- \[30\]S\. Jian, L\. Cao, G\. Pang, K\. Lu, and H\. Gao\(2017\)Embedding\-based representation of categorical data by hierarchical value coupling learning\.InProceedings of the 26th International Joint Conference on Artificial Intelligence,pp\. 1937–1943\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1)\.
- \[31\]S\. Jian, G\. Pang, L\. Cao, K\. Lu, and H\. Gao\(2018\)CURE: flexible categorical data representation by hierarchical coupling learning\.IEEE Transactions on Knowledge and Data Engineering31\(5\),pp\. 853–866\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p3.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[32\]L\. Jing, M\. K\. Ng, and J\. Z\. Huang\(2007\)An entropy weighting k\-means algorithm for subspace clustering of high\-dimensional sparse data\.IEEE Transactions on Knowledge and Data Engineering19\(8\)\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[33\]V\. E\. Johnson and J\. H\. Albert\(2006\)Ordinal data modeling\.Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p3.1)\.
- \[34\]S\. Kullback\(1997\)Information theory and statistics\.Courier Corporation\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[35\]S\. Q\. Le and T\. B\. Ho\(2005\)An association\-based dissimilarity measure for categorical data\.Pattern Recognition Letters26\(16\),pp\. 2549–2557\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11)\.
- \[36\]E\. Levina and P\. Bickel\(2001\)The earth mover’s distance is the mallows distance: some insights from statistics\.InProceedings Eighth IEEE International Conference on Computer Vision,pp\. 251–256\.Cited by:[3rd item](https://arxiv.org/html/2607.05464#S4.I1.i3.p1.1)\.
- \[37\]S\. Li, C\. Gentile, and A\. Karatzoglou\(2016\)Graph clustering bandits for recommendation\.arXiv preprint arXiv:1605\.00596\.Cited by:[§4\.1](https://arxiv.org/html/2607.05464#S4.SS1.p1.1),[§5](https://arxiv.org/html/2607.05464#S5.p2.2)\.
- \[38\]S\. Li and P\. Kar\(2015\)Context\-aware bandits\.arXiv preprint arXiv:1510\.03164\.Cited by:[§5](https://arxiv.org/html/2607.05464#S5.p2.2)\.
- \[39\]S\. Li, A\. Karatzoglou, and C\. Gentile\(2016\)Collaborative filtering bandits\.InProceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval,pp\. 539–548\.Cited by:[§5](https://arxiv.org/html/2607.05464#S5.p2.2)\.
- \[40\]T\. Li, S\. Ma, and M\. Ogihara\(2004\)Entropy\-based criterion in categorical clustering\.InProceedings of the 21st International Conference on Machine Learning,pp\. 536–543\.Cited by:[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p2.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[41\]D\. Lin\(1998\)An information\-theoretic definition of similarity\.\.InProceedings of the 15th International Conference on Machine Learning,pp\. 296–304\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p1.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1)\.
- \[42\]L\. Lov¨¢sz\(1986\)Matching theory\.North\-Holland\.External Links:LCCN 87\-117473Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[43\]L\. v\. d\. Maaten and G\. Hinton\(2008\)Visualizing data using t\-sne\.Journal of Machine Learning Research9\(11\),pp\. 2579–2605\.Cited by:[§6\.2\.2](https://arxiv.org/html/2607.05464#S6.SS2.SSS2.p1.11)\.
- \[44\]D\. J\. MacKay\(2003\)Information theory, inference and learning algorithms\.Cambridge university press,Cambridge, UK\.Cited by:[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p1.2)\.
- \[45\]K\. Mahadik, Q\. Wu, S\. Li, and A\. Sabne\(2020\)Fast distributed bandits for online recommendation systems\.InProceedings of the 34th ACM International Conference on Supercomputing,pp\. 1–13\.Cited by:[§5](https://arxiv.org/html/2607.05464#S5.p2.2)\.
- \[46\]T\. Mitchell\(1997\)Machine learning\.McGraw Hill\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p4.1)\.
- \[47\]M\. C\. Nascimento and A\. C\. De Carvalho\(2011\)Spectral methods for graph clustering–a survey\.European Journal of Operational Research211\(2\),pp\. 221–231\.Cited by:[§4\.1](https://arxiv.org/html/2607.05464#S4.SS1.p1.1)\.
- \[48\]R\. Nock and F\. Nielsen\(2006\)On weighting clustering\.IEEE Transactions on Pattern Analysis and Machine Intelligence28\(8\),pp\. 1223–1235\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[49\]Y\. Qian, F\. Li, J\. Liang, B\. Liu, and C\. Dang\(2016\)Space structure and clustering of categorical data\.IEEE Transactions on Neural Networks and Learning Systems27\(10\),pp\. 2047–2059\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p3.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[50\]W\. M\. Rand\(1971\)Objective criteria for the evaluation of clustering methods\.Journal of the American Statistical Association66\(336\),pp\. 846–850\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[51\]Y\. Rubner, C\. Tomasi, and L\. Guibas\(2000\)The earth mover’s distance as a metric for image retrieval\.International Journal of Computer Vision40\(2\),pp\. 99–121\.Cited by:[3rd item](https://arxiv.org/html/2607.05464#S4.I1.i3.p1.1)\.
- \[52\]R\. Sandler and M\. Lindenbaum\(2011\)Nonnegative matrix factorization with earth mover’s distance metric for image analysis\.IEEE Transactions on Pattern Analysis and Machine Intelligence33\(8\),pp\. 1590–1602\.Cited by:[3rd item](https://arxiv.org/html/2607.05464#S4.I1.i3.p1.1)\.
- \[53\]J\. M\. Santos and M\. Embrechts\(2009\)On the use of the adjusted rand index as a metric for evaluating supervised classification\.InProceedings of the 19th International Conference on Artificial Neural Networks,pp\. 175–184\.Cited by:[§6\.1\.2](https://arxiv.org/html/2607.05464#S6.SS1.SSS2.p1.2)\.
- \[54\]S\. E\. Schaeffer\(2007\)Graph clustering\.Computer Science Review1\(1\),pp\. 27–64\.Cited by:[§4\.1](https://arxiv.org/html/2607.05464#S4.SS1.p1.1)\.
- \[55\]I\. H\. Witten, E\. Frank, M\. A\. Hall, and C\. J\. Pal\(2016\)Data mining: practical machine learning tools and techniques\.Morgan Kaufmann,Cambridge, MA, USA\.Cited by:[§6\.1\.4](https://arxiv.org/html/2607.05464#S6.SS1.SSS4.p2.2)\.
- \[56\]R\. Xu and D\. Wunsch\(2005\)Survey of clustering algorithms\.IEEE Transactions on Neural Networks16\(3\),pp\. 645–678\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[57\]D\. S\. Yeung and X\. Wang\(2002\)Improving performance of similarity\-based clustering by feature weight learning\.IEEE Transactions on Pattern Analysis and Machine Intelligence24\(4\),pp\. 556–561\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p1.1)\.
- \[58\]M\. Zhang, N\. Wang, Y\. Li, and X\. Gao\(2020\)Neural probabilistic graphical model for face sketch synthesis\.IEEE Transactions on Neural Networks and Learning Systems31\(7\),pp\. 2623–2637\.Cited by:[§4\.1](https://arxiv.org/html/2607.05464#S4.SS1.p1.1)\.
- \[59\]Y\. Zhang, Y\. Cheung, and K\. Tan\(2020\)A unified entropy\-based distance metric for ordinal\-and\-nominal\-attribute data clustering\.IEEE Transactions on Neural Networks and Learning Systems31\(1\),pp\. 39–52\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p4.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1)\.
- \[60\]Y\. Zhang and Y\. Cheung\(2018\)Exploiting order information embedded in ordered categories for ordinal data clustering\.InProceedings of the 24th International Symposium on Methodologies for Intelligent Systems,pp\. 247–257\.Cited by:[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p1.1)\.
- \[61\]Y\. Zhang and Y\. Cheung\(2020\)An ordinal data clustering algorithm with automated distance learning\.InProceedings of the 34th AAAI Conference on Artificial Intelligence,pp\. 6869–6876\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p5.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p3.1),[§2\.2](https://arxiv.org/html/2607.05464#S2.SS2.p3.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.
- \[62\]Y\. Zhang and Y\. Cheung\(DOI: 10\.1109/TCYB\.2020\.2983073\)A new distance metric exploiting heterogeneous inter\-attribute relationship for ordinal\-and\-nominal\-attribute data clustering\.IEEE Transactions on Cybernetics\.Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p4.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p2.1),[§3](https://arxiv.org/html/2607.05464#S3.p4.11),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p2.1)\.
- \[63\]C\. Zhu, L\. Cao, and J\. Yin\(2020\)Unsupervised heterogeneous coupling learning for categorical representation\.IEEE Transactions on Pattern Analysis and Machine Intelligence\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2020.3010953)Cited by:[§1](https://arxiv.org/html/2607.05464#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.05464#S2.SS1.p3.1),[§6\.1\.3](https://arxiv.org/html/2607.05464#S6.SS1.SSS3.p1.3)\.