Fuzzy Clustering

A mid-sized insurance company based in Peoria IL was in need of a technique to group together the policies stored in their database by the unique client who owned the policy. Unfortunately, insurance laws required that new policies be entered manually into the database. Consequently, many of their policies had misspelled names, inverted characters in their SSNs, improper addresses, etc. In order to counter this challenge, they were in need of a way to fuzzy-cluster their policies by the client to account for the misspellings.

Table of Contents

1. Abstract
2. Dataset
3. Approach
   1. Weighted Average
   2. Weight Adjustment
   3. The Most Human Human
   4. Representing Hierarchy
4. Proof of Process
   1. Preservation of Proportion
   2. Similarity Scores
   3. Grouping
   4. Centroid Assessment
5. Algorithm Demonstration

Abstract

A common problem for database administrators is that of grouping unique entities when the integrity of the records is questionable. In other words, names might be missing or mispelled, records might be incomplete but still individually identifiable using human intuition. With tens of thousands of records to identity, human intuition must be supplemented with technical muscle. One approach to this problem is to apply Levenshtein distance across the fields of two records to determine if they are related. Groups will be formed by similarity and weights will be applied to the data fields according to their value to us (e.g. SNN is more identifiable than suffix or zip code).

Dataset

The synthesized data that we will be studying comes in the form of records. I have simulated data fields with names, addresses and SSNs. There are multiple groups within this dataset and therefore multiple groups should be identified by our algorithm. Many of these identities are one to one such that a single identity has a single record but several identities are described by several records in a one to many scenario. It is my hope that my algorithm will successfully identify these relationships.

Approach

My process for clustering will follow a standard card analogy. Imagine that we have a deck of cards and we wish to cluster them. By what? Suit? Royalty? Value? We say that we want to sort by suit but that the symbols for the suite have been obscured and disfigured. We know that hearts and diamonds, clubs and spades look similar but that there is a way to compare their similarity. Our process follows:

1. Throw one card on the table and make it a group
2. Select the next card
3. Compare suits
   1. If the new suit is sufficiently similar to an existing group then it joins the group that it is most similar to
   2. If the new suit it not sufficiently similar to any existing group then it becomes its own group
4. Are there more cards in the deck?
   1. Yes, go to 1.
   2. No, end.

This process ensures that a new group can only be formed by failing to belong to an existing group.

Weighted Average

Obviously, the card analogy does not entirely apply to the specifics of this problem. We have records with features (entries for a column) to identify them, some of which matter more to us than others for the purpose of identification.

$$R_n = \{ \; f_0, f_1, f_N \; \}$$

We express our system of priority by assigning weights to each feature by order of significance, like so:

$$\vec{ \omega } = \omega_0 + \omega_1 + \omega_N = \sum_{n = 0}^{N} \omega_n = 1.0$$

Individual features of a record can be compared to the features of another record using Levenshtein distance. A ratio can be obtained which refects the percentage of similarity between the features. To express the similarity between the records however, we must apply the weights to the individual feature similarities. We can find the similarity $\text{s}$:

$$R_a = \{ \; f_{a0}, f_{a1}, ... \; f_{aN} \; \} \\ R_b = \{ \; f_{b0}, f_{b1}, ... \; f_{bN} \; \}$$

$$\text{s} = \omega_0 \cdot \text{Lev}( f_{a0}, f_{b0} ) \; + \; \omega_1 \cdot \text{Lev}( f_{a1}, f_{b1} ) \; + \; ... \; \omega_N \cdot \text{Lev}( f_{aN}, f_{bN} )$$

If $R_a$ is an existing group unto itself and $\text{s}$ is greater than some threshhold big $\text{S}$ then $R_b$ joins the group for $R_a$. Then a new record $R_c$ is compared to the center of $R_a$ (more on this later). The process repeats.

However, if $\text{s} < \text{S}$, then $R_b$ becomes its own group. Then record $R_c$ is compared to records $R_a$ and $R_b$ and the process repeats.

Weight Adjustment

If a record has missing features, then the algorithm suffers a statistical nightmare. For example, imagine that we have two records $R_a$ and $R_b$ with four features which are equal in all respects except for one: $f_{a2} = \text{NaN} \neq f_{b2}$. If all weights are adjusted equally, then the best similarity that these records could obtain would be a 75%, which might be too low to exceed the threshhold. If we want these records to be equated, then we must either lower our standards of adjust the weights, but how?

When a feature is missing, the algorithm drops the feature from the comparison and adjusts the weights while preserving the biasing. Say that feature number 2 is missing, then let $\vec{ \omega_{A} }$ represent the adjusted weights:

$$\text{Let} \; \vec{ \omega } = \left[ \omega_0, \omega_1, \omega_2, \omega_3 \right] \; \text{s.t.} \; \sum_{n = 0}^{N} \omega_n = 1.0$$

$$\vec{ \omega_{A} } = [ \omega_0, \omega_1, 0, \omega_3 ] \longrightarrow \left[ \frac{\omega_0}{\omega_0 + \omega_1+ \omega_3}, \frac{\omega_1}{\omega_0 + \omega_1+ \omega_3}, 0, \frac{\omega_3}{\omega_0 + \omega_1+ \omega_3} \right]$$

Using numeric values, let's say that $\vec{ \omega } = [ 0.20, 0.20, 0.50, 0.10 ]$ with feature number 2 missing, then:

$$\vec{ \omega_{A} } = [ 0.20, 0.20, 0, 0.10 ] \longrightarrow \left[ \frac{0.20}{0.20 + 0.20 + 0.10}, \frac{0.20}{0.20 + 0.20 + 0.10}, 0, \frac{0.10}{0.20 + 0.20 + 0.10} \right] = [ 0.40, 0.40, 0.20 ]$$

The first and second weights maintain their proportionality to the final weight. Our algorithm has adjusted without loosing its assigned biases.

The Most Human Human

One issue facing our algorithm lies in the representation of groups. Storing groups programmatically is an issue unto itself, but comparing individual records against a group is the key challenge. With numeric data, there exists an idea of the centroid: an n-dimensional center of mass for a set of records. With text data, however, the centroid becomes more abstract.

There are two approaches for finding the best representative of a group identity:

1. Completeness - The record with the fewest missing fields.
2. Similarity - The record that is the most common to the other records in the group.

We will use approach 1 for groups with 2 or fewer records and approach 2 for groups with three or more records.

Representing Hierarchy

Another issue facing this system is how to store the hierarchy. My solution to this problem is to have a separate table with a column for group number, record number, and a flag for the centroid. Then we can quickly select a group number, obtain its records, and query the main dataframe for the record level details. We can manage the hierarchy efficiently without needing to pull the heavier records through the query, this approach should lower the computation requirements.

Proof of Process

Prior to developing sets of functions to execute my proposed algorithm, I want to develop the process to prove that it works in its raw form. Once I have established the viability of this route I can proceed to the next stage.

Preservation of Proportion1

As described in the previous section, missing fields in a record can complicate the comparison process. However, the weights can be readjusted to preserve the balance such that they remain proportional to each other and still add up to a whole. First, we setup the weights used for establishing the bias or preference towards one field of a record over another. The balance of the weights is verified before we continue.

>>> Omega = [ 0.18, 0.15, 0.20, 0.05, 0.05, 0.10, 0.02, 0.25 ]
>>> if np.sum( Omega ) != 1:
    print('Weights are not in balance.')

We select two records from the dataset for our example comparison rec_ind=[1,2].

The first record is not missing any fields but the second record is missing one field (field 6, ZIP), which we detect below.

>>> for i in range( 0, len(rec_ind) ):
        true_ind = np.where( Data.iloc[ rec_ind[i] ].isnull().values == True )
        status = 'Missing {}'.format( *true_ind )
        print("R{} \t: {}".format(rec_ind[i], status) )
R1  : Missing []
R2  : Missing [6]

The weights are adjusted according to the methods described in the previous section, we simply divide the weights by the sum of the weights for non-missing records.

>>> Omega_A = Omega.copy()
>>> print('Original: \t{}'.format( Omega ) )
>>> for i in true_ind[0]:
        Omega_A[ i ] = 0
>>> Omega_A = Omega_A / round( np.sum( [ Omega_A[i] for i in np.nonzero( Omega_A )[0] ] ), 20 )
>>> print('Adjusted: \t{}'.format( Omega_A ))
>>> if not math.isclose( np.sum( Omega_A ), 1, abs_tol = 1e-100 ):
        print('Weights are not in balance.')
Original:   [0.18, 0.15, 0.2, 0.05, 0.05, 0.1, 0.02, 0.25]
Adjusted:   [0.18367347 0.15306122 0.20408163 0.05102041 0.05102041 0.10204082 0.0000000 0.25510204]

Checking these weights, we can see that dividing any two weights ($\omega$) by each other from the original/initial set results in the same proportion ($p$) as the same weights divided from the adjusted set $\omega_{im} / \omega_{in} = p_{mn} = \omega_{am} / \omega_{an}$. Proportion of bias is preserved for missing fields.

Similarity Scores

Now the similarity of the records can be calculated. The similarity threshold ($S$) is set and the Levenshtein ratios for the individual fields ($\vec{s}$) are calculated. The sum-product of the similarity scores and the weights reflect the aggregate similarity score ($s$) for the records. If $s >= S$ then the records are said to be sufficiently similar according to the weights and threshold set for the calculation.

>>> S = 85
>>> s = np.array([])
>>> for j in range(0, len(Data.columns)):
        s = np.append(s, fuzz.ratio( Data.iloc[ rec_ind[0] ].apply(str)[j], Data.iloc[ rec_ind[1] ].apply(str)[j] ) )
>>> print( 'Lev Ratios: {}'.format(s) )
>>> s = np.inner( s, Omega_A )
>>> print( 'Similarity: {}'.format(s) )
Lev Ratios: [ 29. 100. 100. 100. 100. 100.   0. 100.]
Similarity: 86.95918367346937

By human intiuition², these records are clearly similar and they meet the similarity criteria set for the study since $s > S$. However, let's compare records that are not similar by human intuition:

Rerunning the analysis described above for rec_ind=[1,4] yields no changes to the weights since no fields in the records are missing. The aggregate similarity score comes out to $s = 24.42 < S$ and therefore these dissimilar records are correctly identified as dissimilar (true negative).

It is worth noting that, for any sufficiently large and diverse dataset, false possitives and false negatives will occur. Establishing the optimal weights and threshold for the study is a matter of art and, at this time, no analytical solution to this optimization problem has been found.

Grouping

We will pretend, for simplicity sake, that the first record in the comparison was a group centroid and that it was in the Groups dataframe the whole time as the only existing group. The groups dataframe is created the the first record is added as a group centroid.

grp_col = [ 'Group Number', 'Record Number', 'Centroid Flag' ]
Groups = pd.DataFrame( data = { grp_col[0] : 0, grp_col[1] : rec_ind[0], grp_col[2] : True }, index = {0} )

If a record is sufficiently similar to a group centroid then it is appended to that group.

if s >= S:
    grp_no = Groups.loc[ Groups[ Groups.columns[1] ] == rec_ind[0] ][ Groups.columns[0] ].values[0]
    rec_no = rec_ind[1]
    Record = pd.DataFrame(data = { grp_col[0] : grp_no, grp_col[1] : rec_no, grp_col[2] : False }, index = {0})
    Groups = Groups.append( Record, ignore_index = True )

Otherwise, it becomes the sole member and acting centroid of its own group with a new group number.

else:
    grp_no = Groups[ Groups.columns[0] ].values.max() + 1
    rec_no = rec_ind[1]
    Record = pd.DataFrame(data = { grp_col[0] : grp_no, grp_col[1] : rec_no, grp_col[2] : True }, index = {0})
    Groups = Groups.append( Record, ignore_index = True )

For rec_ind=[1,2], our sufficiently similar records, we are left with the single group:

And for rec_ind=[1,4], our dissimilar records, we are left with the two groups:

Centroid Assessment

Within the K-means algorithm, the center of a cluster adjusts when new records are assigned. Similarly, we may create individual groups due to uniqueness or incompleteness and then find a more accurate representative for a given identity. Consequently, we must periodically reevaluate which records are centroids.

In a previous section, I describe two measurements for determining the centroid of a group. If the number of records in a group is 2 or fewer then the centroid must be the most complete record: the record with the fewest missing values.³ If a group has three or more records then we can take the inner similarity between such records and determine which record is most similar to the records within its set. This way we know that we have selected the best representative of the group.

Algorithm Demonstration

With the proof of process completed, functions were developed and the full algorithm can now be run against the mock dataset. The study is instantiated and global weights and the threshold are set.

Omega = [ 0.18, 0.15, 0.20, 0.05, 0.05, 0.10, 0.02, 0.25 ]
S = 75
verb = False
Master = Data.copy()
Deck   = Data.copy()
grp_col = [ 'Group Number', 'Record Number', 'Centroid Flag' ]
Groups = pd.DataFrame( columns = grp_col )
card = iterator( Deck, True, False )
Groups.loc[0] = [ 0, card.name, 1 ]

Ergo, we have a single group consisting of the first record, which is assigned as the centroid by default.

We iterate through the deck of unassigned records and grade single record (card) against the centroid of each existing group. If the record is sufficiently similar to the centroid of the group then the record becomes a member of said group. Otherwise, it becomes the acting centroid of its own group. After each iteration, the centroids for each group are reassessed according to the criteria described previously.⁴

number_of_elements = len(Deck)
for c in range( 0, len(Deck) ):
    card = iterator( Deck, True, False )
    scores = score_against_groups( Master, card, verb )
    max_score_ind = np.argmax( scores )
    if scores[ max_score_ind ] >= S:
        Groups = append_to_groups( Groups, max_score_ind, card.name, False, verb )
    else:
        Groups = append_to_groups( Groups, np.max( Groups[ Groups.columns[0] ].values )+1, card.name, True, verb )
    centroid_assessment( Master, verb )

The final groups dataframe is presented below.

For ease of reference, we can append the group number column to the original dataset.

Pretty great, honestly. Wizard, one could say, but perhaps one shouldn't until Vader brings it back.⁵ One interesting phenomena can be seen in the Harvey Milk entries (records 0-3). The group is split by the algorithm into two distinct groups which would otherwise be combined by human intuition.⁶ This phenomena is bound to occur for larger datasets but methods may be developed to integrate factions. For instance, after centroid-assessment, centroids could be compared against each other and integrated according to the theshold.