Electricity based external similarity of categorical attributes
Christopher R. Palmer, Christos Faloutsos · 2003
Abstract. Data mining tools use similarity or distance computations as a fundamental and critical data prop-erty. Categorical attributes abound in databases. For example, the Car Make, Gender, Occupation, etc. elds in a car insurance database contain a great deal of useful information that is encoded as categorical values. Sadly, categorical data is not easily amenable to similarity computations. Typically, a domain expert could manually specify some or all of the similarity relationships. This is error-prone and not feasible for attributes that take on many values, nor is it useful for cross-attribute similarities, such as between Gender and Occupation. External similarity functions dene a similarity between, say, Car Makes by looking at how they co-occur with the other categorical attributes. In this paper we exploit a rich duality between random walks on graphs and electrical circuits to develop an external similarity function called REP. The only previously proposed external similarity function is ad-hoc while REP is theoretically grounded. To illustrate the usefulness of REP, we conduct two experiments. First, we cluster categorical attribute values to show the relationships inferred by REP. Second, we use REP eectively as a nearest neighbour classier. 1