The customer addresses are important in e-Commerce for eficient shipment delivery. A predefined structure in addresses is not usually followed in developing countries. Further, some customer addresses are found to be noisy as they contain avoidable additional details such as directions to reach the place. In the presence of such challenges, understanding and equivalence mapping of the addresses becomes necessary for eficient shipment delivery as well as customer linking. We discuss the challenges with actual address data in Indian context. We propose efective methods for eficient large scale address clustering using conventional as well as deep learning approaches. We demonstrate efectiveness of these approaches through elaborate experimentation with real address dataset of an Indian e-commerce company. We further discuss efectiveness of such solution in fraud prediction models.
Geographical addresses form basic references for delivering
shipments ordered online with an e-Commerce organisation. These
organisations focus on machine learning models for faster and
accurate delivery of the orders. As the organisations expand to serve
diferent business verticals such as perishable grocery, the need of
delivering shipments within hours of the order placement becomes
pivotal. The geographical addresses form basic building block for
each of these services. Address is formally defined as the one that
specifies a location by reference to a thoroughfare or a landmark; or it
specifies a point of postal delivery [
In the online retail, customers at the time of their user registration specify one or more of their addresses. In reality, these Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
SIGIR 2018 eCom, July 2018, Ann Arbor, Michigan, USA © 2018 Copyright held by the owner/author(s).
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. https://doi.org/10.1145/nnnnnnn.nnnnnnn addresses in developing countries contain following interesting challenges.
• Unlike places in Europe, US, Japan and North Korea, the
written addresses in developing countries do not follow a
prescribed structure [
Such depiction of addresses pose challenges for a machine
learning based automated solutions such as address classification [
E-Commerce companies face a number of frauds such as reseller fraud, and fraudulent claims related to missing items or mis-shipments. The resellers are those customers who exploit online discounts or ofers, and sell the items ofline for profit. The e-Commerce companies limit the number of purchases made by a single customer in order to reach out to larger customer base. Under this constraint, resellers would vary their address patterns to register as a new user for making another purchase. The reseller fraud relates to an online fraud where some fraudulent customers buy items by making use of ofers and discounts and selling them ofline for profit. Such fraud reduces opportunity for genuine customers to make purchases. Machine learning models are built to identify of fraudulent transactions, such as, reseller fraud as discussed above, missing item fraud where a buyer claims that delivered package did not contain an ordered item, etc. The customer addresses written diferently with fraud intent but belonging to the same customer form an important signal in such models. Similarly, identification of those addresses of the customers belonging to same household but registered diferently is another important application where similar addresses need identification.
In the presence of above challenges in our current work, we examine ways of clustering the same addresses that are written diferently either as non-standard sequencing of words or as large set of additional words. An example for non-standard sequencing of words in addresses of same location but written diferently is, House No.xxx, 2nd Main, ISRO Layout, Bikasipura, Bangalore vs. House No.xxx, Bikasipura, ISRO Layout, 2nd Main, Bangalore. Such addresses are very common in the current problem. Another important challenge is the massive address dataset that spans across the country, which needs to be clustered. Thus, in the presence of these challenges, the choice of clustering approach is important.
We examine multiple clustering schemes. After relative evaluation, we consider one base clustering scheme that requires single database pass to generate clusters. Its distinct advantage as noniterative algorithm is ideally suited for mining large datasets. In terms of features, we consider two approaches. In Approach-1, we consider words directly as features. In Approach-2, we consider address word embeddings computed using huge address corpus. We provide interesting insights on word embedding in clustering addresses, in the presence of avoidable additional words such as directions to reach a place. The word embedding on address corpus is more suitable for the present application than using a generic pre-trained embeddings. We also examine afinity propagation approach to clustering using word embeddings. We carry out experimentation. We demonstrate efectiveness and eficiency of such approaches. We integrate following aspects in the paper. • A discussion of eficient clustering approaches • Clustering using text similarity • Word embedding of addresses • Clustering using word embedding • Experiments on large datasets • Cluster evaluation
We organise the paper in the following manner. Section 2 contains motivation for solving the proposed problem and a discussion on related work. The data challenges and preprocessing are discussed in Section 3. Section 4 contains a discussion on proposed solutions. The proposed algorithms are tested on a huge corpus of actual Indian addresses. The results are discussed in Section 5. The application usecases are presented in Section 6. A summary of contributions of the work and outline of future work are provided in Section 7. 2
The clustering of addresses is essential to identify groups of users
that have same address but written diferently. It helps to identify
groups of same or similar users for reaching out to them with
possible business initiatives as well as to identify potential fraudsters.
The variability in addresses arises due to inadvertent entries,
nonexistence or non-conformance of address standards, and the nature
of users who provide avoidable additional details. Apart from these
sources, the user entered addresses contain many challenges in
terms of spell variants, abbreviations, monkey typed addresses
containing jumbled alphanumeric characters [
We did not come across any work related to clustering of
customer or postal addresses in the literature. We discuss works on
related topics. The objective of clustering is to separate patterns
into groups such that the patterns within a group are similar with
reference to a chosen criterion than to those patterns in the other
groups [
Address could be considered as short text documents in terms of
length. In clustering short text documents, exact keyword matching
is not found to be suficient and text representation is expanded by
making use of larger related documents [
For large datasets, the choice of clustering algorithm needs to be
eficient. Ideally, such algorithms should be able to cluster a large
dataset with a single or two passes of the dataset since iterative
algorithms seek multiple passes through the dataset which are
prohibitively expensive. In view of this, we consider leader clustering
algorithm [
As discussed previously, the addresses contain a number of spell
variations, variable sequence of keywords and additional text that
indicate description of reaching the place, phone numbers, etc. Thus
a word based matching can be challenging. For example, word based
matching of words like ‘apartment’ and ‘apartmnts’ would be
successful depending on threshold of number of characters, whereas
the words ‘apartment’ and ‘apt.’ do not match although they
represent the same. In view of this, we also consider word embeddings
as bag of words for generating equivalent sets of words [
Another important related area is evaluating the clusters. If the
objective of clustering is data reduction through prototype selection,
the clustering can be evaluated by labelling large enough sample
of patterns and evaluate the clustering based prototype selection
through conventional supervised learning metrics [
We consider address data of over a million of Indian addresses. It is observed that rural addresses are short. The urban addresses are usually long. Table 1 contains average length of addresses across India at five representative states in the East, West, North, South and Central part of India. It can be observed from the table that average number of words per address is about 9, across the country. But the maximum number of words vary from 50 to 166 which is much larger than average number of words per address over any region. Such large number of words indicates avoidable additional details. As discussed earlier, examples of such details are the text on directions to reach a location, times of customer availability, etc. They pose challenges to the address clustering algorithms.
90 58 65 92 53
Surat Ahmedabad Chennai Kolkata Delhi The discussion on address data in Section 3 provides insights on the data challenges. We need to cluster the same and similar addresses. In this context, we briefly discuss about Indian address system.
The postal index number or PIN code [
We consider a number of clustering algorithms. The objective is
to obtain clustering of similar addresses. The data under
consideration is text, and the number of candidate addresses is large. We look
for representative patterns. These considerations eliminate popular
k-means algorithm as number of clusters can not be predefined,
and secondly the centroid is unlikely to be a pattern in the original
dataset. As we cannot predetermine the number of clusters, and
also based on earlier study comparing k-medoids to leader for
prototype selection [
In the Leader algorithm, we have the flexibility of defining the similarity threshold and the number of clusters is determined by that threshold. Further, prototypes generated by the leader algorithm will be the patterns from the original dataset. Another advantage of the algorithm is that it requires single pass through the large database to generate clusters. For pattern similarity we consider conventional text similarity approach as well as word embedding vectors. We discuss the algorithms, ways of combining words, and algorithm complexity in this section. We discuss leader algorithm in Section 4.1, afinity propagation in Section 4.2, leader with conventional text comparison in Section 4.3 and leader with word embeddings in Section 4.4. 4.1
The leader algorithm is presented in Algorithm 1. It is based on a predefined similarity threshold, ξ . Initially, a random pattern among the input patterns is selected as leader. Subsequently, similarity of every other pattern is compared with that of selected leaders. If the similarity of new pattern is more than the threshold, the corresponding pattern falls in the cluster with the initial leader. Otherwise, the pattern is identified as a new leader. The computation of leaders is continued till all the patterns are considered. We can tune the similarity threshold according to the task in hand. The number of leaders is directly proportional to the selected threshold. Therefore, smaller the similarity threshold, smaller will be the number of clusters, but it may afect intra-cluster distance of the clustering and high the threshold, more will be number of clusters, but it may afect inter-cluster distance of clustering.
Input: patterns: P [1, ..., n] , similarity threshold: ξ
Output: ldrpat [1, ..., k] , leaders which are cluster
representatives
ldrpat [
ldrpat [j] = P [i] end if end for end for 4.2
Similar flexibility of having a representative pattern or
prototype from the original dataset and avoid pre-specifying number
of clusters a priori can be obtained by the Afinity propagation
algorithm [
The messages sent between pairs represent the suitability for one sample to be the exemplar of the other, which is updated in response to the values from other pairs. This updating happens iteratively until convergence, at which point the final exemplars are chosen, and hence the final clustering is given. Afinity Propagation does not require the number of clusters to be suggested a priori or estimated before running the algorithm and chooses the number of clusters based on the data provided. The main drawback of Afinity Propagation is its complexity. The algorithm has a time complexity of the order O (n2 ∗ d ∗ T ), where n is the number of samples, d is maximum number of words in address and T is the number of iterations until convergence. Therefore, scalability is the concern for this algorithm.
We discuss following two address clustering approaches that uses Leader as base clustering algorithm.
In case of address data, we need to find similarity between the addresses. Since the objective is to group similar addresses, the addresses are expected to have terms that are similar but variant in position, spelling and number of terms. In view of this, we consider actual term matching. We use edit distance with appropriate threshold.
Input: patterns: p1, p2, similarity threshold: ξ , edit distance threshold: ϵ count = 0 for word1 in p1 do for word2 in p2 do if editdistance (word1, word2) ≤ ϵ then
count ← count + 1 end if end for end for if count ≥ ξ ∗ min(no_o f _words_p1, no_o f _words_p2) then return YES else
return NO end if
Leader clustering algorithm is provided in Algorithm 1. The proposed approach has two parameters, such as, ξ for similarity threshold and ϵ for edit distance threshold in terms of number of characters. The similarity algorithm used in the algorithm is described in Algorithm 2. The worst case complexity of Algorithm 1 is O (n2). The worst case complexity of Algorithm 2 is O (d2 ∗ m2), where d is the maximum number of words in any pattern p and m is the maximum length of any word w in any pattern p. So, overall worst case complexity of the algorithm is O ((n ∗ d ∗ m)2).
The clusters are represented by leaders which are essentially one of the patterns in the given dataset. Leader should be contrasted against a centroid which in most cases is not a pattern in the given dataset. The number of clusters identified depends on the similarity threshold ξ . The value of ξ is empirically chosen and is data dependent. However, it should be noted that the leaders are order dependent.
The clustering of addresses with appropriate edit distance provides good homogeneous clusters. But when the addresses contain additional words, beyond a certain threshold, such addresses form a diferent clusters. At this stage, it is educative to examine alternate approaches to group those addresses that have additional words which are reasonably rare but still belong to the same location. Such additional words include such rare descriptions like directions to reach a place, as we discussed in Section 3. Secondly, it is interesting to explore ways to bring all the vocabulary that are semantically similar but syntactically variant. This motivated us to examine word embeddings based clustering.
In this approach, instead of using edit distance based method,
we will use word embeddings of all the addresses. Each word is
embedded into vector using the continuous bag of words (CBOW)
algorithm [
Input: patterns: p1, p2, distance threshold: ξ vec1 ← 0, vec2 ← 0 for word1 in p1 do
vec1 ← vec1 + word2vec(word1) end for for word2 in p2 do
vec2 ← vec2 + word2vec(word2) end for if cosine_similarity (vec1, vec2) ≥ ξ then
return YES else
return NO end if
As we notice in Algorithm 2, edit distance based similarity is polynomially dependent on the number of words as well as the length of words in the pattern. Whereas, add2vec based cosine similarity linearly depends on the number of words in the pattern and constant vector length l. Therefore, the complexity of add2vec similarity algorithm is O (2d ), where d is the maximum number of words in any pattern p. So, overall, the worst case complexity of the algorithm is O (n2 ∗ d ), whereas worst case complexity of Afinity propagation algorithm with add2vec based cosine similarity is O (n2 ∗ d ∗ T ).
The first advantage of using add2vec approach is that it is scalable and requires less computation time, given the address word embeddings. Secondly word2vec can capture spell variants which can go beyond the threshold chosen for term based comparison as discussed in Section 4.3. Also, it can handle additional uncommon words such as directions to reach a place. We carried out elaborate experimentation to compare and validate results generated by address clustering algorithms. We used both human evaluation and commonly used metrics to compute cluster validity.
In the setting of address clustering, the actual number of clusters in the dataset is not known, a priori. In the context of e-Commerce customers, it is unlikely that one would arrive at clusters of large sizes except in case of fraud scenario such as resellers or large apartment complexes. The reseller fraud modelling is one of the applications of the current exercise of address clustering. In the experiments as shown in Figure 2, maximum cluster size is of the order of about 500.
Let us consider a case of validating a clustering algorithm by
making use of labeled patterns [
In Section 5.1, we discuss two metrics, known as, silhouette
coeficient and Calinski-Harabasz index. The alternate approach
to metrics based validation is by making use of human experts
validating whether cluster members are homogeneous. The
experimentation, results and insights are presented in Section 5.2.
Calinski-Harabasz index: For k clusters, the Calinski-Harabaz
score [
Consider that there are k clusters. Given the mean of squared distances of between all samples, d2 and mean of squared distance 2 within a group, g, dд , the weighted mean of the diferent between overall and within group mean squared diferences is given by, (2) (3) (4) (5) 1 k 2 2 Ak = X(np − p) (d − dp )
n − k p=1 The between group sum of squares is given by,
1 2
BGSS = 2 ((k − 1)d + (n − k )Ak ) The within group sum of squares is given by,
W GSS = 1 Xk(np − p)dp 2 2
p=1
BGSS/k − 1 s =
W GSS/n − k
The score is higher for dense and well separated clusters.
We generate word embeddings by training a large corpus of addresses of over a million of customer addresses across India by considering those words that have minimum support of 100. The approach identifies all spell variants that are close by in cosine similarity sense. In Table 7, we present spelling variants captured by Clustering with edit distance and Clustering with word2vec algorithms. The spell variants that are shown against embeddings are in addition to those identified using edit distance.
We aim to cluster similar addresses. Practically, the addresses are similar within a given geographical locality. The locality is captured well by PIN code as discussed in Section 4. For the exercises, we ignore error in PIN codes as mentioned by the customers. This usually forms a small percentage of the addresses. Further, their presence would only lead to singleton or clusters of very small size. Even within a PIN code the number of addresses reaches a hundreds of thousand addresses. Thus we restrict clustering to a given PIN code. We conducted PIN code-wise experiments across the country. We carry out experiments for choosing appropriate thresholds for clustering. Figure 1 contains number of clusters per PIN code using add2vec. We consider similarity as threshold as against conventional measure of dissimilarity for clustering. As similarity increases, number of clusters increases.
140000
We repeat this experiment for diferent States within India for various similarity thresholds. We further study the number of addresses per cluster for all the states. For illustration, we present the results for one state of Punjab in India. Figure 2 contains number of cluster members for each cluster for thresholds, 0.85(topleft),0.90(top-right),0.95(bottom-left),0.98(bottom-right). Following observations can be made from these plots.
• No. of singleton clusters increases with increasing similarity threshold • No. of cluster members is of the order of {27 to 212} for 0.85, {26.7 to 211} for 0.90, {26 to 29} for 0.95 and {25 to 29} • No. of cluster members per cluster is near optimal (changeover point) for the score of 0.95 217 s214 r te211 s lu28 c fo25 o N22 217 s214 r te211 s lu28 c fo25 o
N22 217 s214 r te211 s lu28 c fo25 o N22 217 s214 r te211 s lu28 c fo25 o N22 2−1 2−1 21 23 25 27 29 211 213
No of addresses in cluster 2−1 2−1 21 23 25 27 29 211 213
No of addresses in cluster 2−1 2−1 21 23 25 27 29 211 213
No of addresses in cluster 2−1 2−1 21 23 25 27 29 211 213
No of addresses in cluster
The cluster metrics for each of the above thresholds is placed in Table 8. It can be noted from the table the metrics increase with increasing similarity value till 0.95 and reduce subsequently.
Based on the empirical evaluation and observations from the plots in Figures 1 and 2, and Table 8, we consider a threshold of 0.95 for leader with add2vec.
For leader clustering with edit distance, where we compare actual words between two addresses using edit distance, we use two thresholds. The first threshold, ϵ, is on the edit distance between two words and the second threshold, ξ , is on the number of words that could be diferent between two addresses so that they could be placed in the same clusters. The choice of ϵ depends on word length. We carried out experiments for diferent values of ϵ and ξ . The values for ϵ are chosen as {1,2} for word lengths of {≤4,≥5} respectively. Based on empirical evaluation, we consider a value of 0.95 for the threshold, ξ .
We present quality of clustering results of proposed Leader clustering algorithm with add2vec similarity, Leader clustering algorithm with edit distance similarity and Afinity propagation algorithm with add2vec similarity. To visualise homogeneity of clusters generated by each of these algorithms, we have chosen a sample of 1000 addresses randomly from a pincode. The results for similar address are shown in Tables 9, 10, 11 .
It can be observed from the tables, that cluster quality with afinity propagation with add2vec similarity and leader with add2vec produce similar clusters. But computation complexity of afinity propagation is very high. We observe that the algorithm is not scalable for large data. In case of leader with edit distance, by virtue of choice of ξ and ϵ, the clusters contained a patterns that does not belong to the cluster. An example is shown in italics, in Table 10.
For the above samples, we computed cluster metrics and placed them in Table 12. The CPU time presented in seconds is based on random sample of 10,000 addresses. The CPU time on Intel(R) Xeon(R) CPU E5-2690 v4 @ 2.60GHz with Sklearn 0.19.1 implementation of python 2.7 is presented in Column-4. We show the efectiveness of clustering approach with word embeddings in Table 13. Here we consider an address of leader or cluster prototype and compare its similarity as new words get added. Both the leader and final address with additional words are taken from actual address database of Flipkart. For the sake of brevity we show additional words in small bursts instead of considering them word by word. The table contain address and its similarity with the address in row-1. The corresponding similarity is with itself in row-1 and hence it is 1.0. Further in order to appreciate the changes from previous address, relatively new terms are shown in italics. Column-2 contains cosine similarity of the address to the leaderaddress (row-1). We note from the table, even after doubling of number of words from 16 of the leader to the address in the last row that contained 32 words, the similarity remains within the chosen threshold of 0.95. However this approach will have dificulty when the additional words are frequent words that appear in the address.
We deployed this solution in conjunction with supervised machine learning model for classifying resellers and found significant gains in fraud prevention.
In general, the address clustering solution has multiple applications in the e-Commerce companies. A efective algorithm links all the users belonging to the same address but written diferently either by deliberate attempt with fraud intent or due to inadvertence. This in turn has multiple applications such as (a) reaching out to diferent groups of users, (b) plan multiple shipment delivery initiatives, (c) machine learning models to detect frauds, etc. A pre-emptive action at the time of ordering can prevent fraudulent transactions. In summary, this forms an important signal for machine learning models in Trust and Safety domain of e-commerce transactions. 7
We consider a practical problem of clustering addresses in places where the addresses do not follow a predefined structure. It is compounded by limited literacy of the customer which result in spell variations, merged words where space separator between two address components is missed, abbreviations, inadvertent separation of a joint word, etc. We consider a clustering algorithm that is suitable for mining large datasets, known as Leader. It uses single database scan for forming clusters. In terms of features, we consider text components of address directly and word embeddings of the entire address corpus independently for diferent approaches. With word embeddings, for a given address, we obtain vector representation by averaging each of the word embeddings. In addition to these algorithms, we also study the utility of afinity propagation algorithm and highlight its limitations. We present the algorithms, discuss relative advantage and disadvantages along with the elaborate experimental results. We carry out elaborate experiments and demonstrate that leader clustering with word embeddings, which we term as add2vec provides address clustering solution. The clustering approaches of leader with edit-distance could lead to outliers entering a cluster. And the afinity propagation algorithm is found to be non-scalable.
Another advantage of the clustering approach is that we obtain address prototypes for a clusters of similar address. The huge corpus of address of hundreds of thousands of addresses for each PIN code is reduced to smaller set of prototype vectors, which is a proper subset of original address dataset. This makes comparison of addresses, and insertion of a new address to the existing set of clusters as eficient operations, since we only consider the prototypes for these operations.
As future work, we propose to evaluate the use of tf-idf weighting of individual word embeddings to obtain representative address vector for more efective clusters and hierarchical clustering using the same approach with diferent valid thresholds for scaling to larger datasets. Also, we considered a window size of 3 for CBOW and embedding of 200. The efect of choice of hyper parameters on clustering performance is also considered for future work.