We use K Nearest Neighbors (KNN) classic classification model and the Best Match (BM)25 probabilistic information retrieval model to assess how eficiently the classic KNN model could be modified to solve the real-life product categorizing problem. This paper gives a system description of the KNN-based algorithm for solving the product classification problem. Our submissions experimented are based on the Rakuten 1M product listings datasets in tsv format provided by the Rakuten Institute of Technology Boston. The classification of our KNN algorithm was based on the product title similarity scores generated from the BM25 Information Retrieval Model. With the setting of k=3 in KNN, our proposed program achieved 0.7809, 0.7821, 0.7790 in weighted-{precision, recall and F1 score} respectively in the test dataset.
• Information systems → Probabilistic retrieval models; Clustering and classification ; • Computing methodologies →
SIGIReCom’ 18; Large-scale taxonomy classification
As the fast-paced development of the internet, there has been a huge rise of the e-commerce market. Online shopping platforms such as Amazon and Alibaba provide not only goods meeting consumers’ specific needs, but also products that are basically everyone’s daily consumption in life. Almost all the e-commerce platforms aim for updating their shopping lists and inventories at their fastest speed to target certain consumers in order to win a bigger proportion of the market. Therefore, the technologies adopted to eficiently and efectively recognizing product categories become more important. This would, on one hand, help the system operators to add in or delete certain items from consumers’ shopping list. On the other hand, it would also be easier for system operators or managers to deal with data analysis and data management in future. This specific data challenge belongs to the large-scale taxonomy classification domain and focuses on the fundamental problem of predicting product’s category in the taxonomy tree with given product’s title. 2
Properly categorizing a new product as a dynamically updated
category in the form of a taxonomy tree is of critical importance for
e-commerce. Algorithms in support automated process for
categorizing need to be straightforwardly simple for its scalability, flexible
to allow labeling errors and noises, distributive over tree branches
and paths hence the taxonomy trees they create are largely balanced.
Leading approaches for measuring path similarities in a taxonomy
tree make use of Wordnet [
Nearest-neighbor for classification can be traced back to as early
as 1950s [
Cosine similarity (or Vector Space Model (VSM)) is often used
to measure similarity between two text documents[
In this section we first give brief introduction to technical preliminaries, BM25 the ranking function in particular. Categorization through classification in terms of KNN+BM25 is explained next (pseudo code in the upper part of Table 1), with an example provided. The framework in support of the classifier is also presented (illustration in Figure 1 and pseudo code in the lower part of Table 1). 3.1
We chose the K nearest neighbors (KNN), which is a classic classification algorithm, as our major classification approach. KNN is traditionally a simple algorithm that stores all the available candidates for classification, and it classifies each new candidate based on the similarity measure.
Definition 1: KNN classification:
K-nearest neighbors algorithm is structured on the basis of feature similarity measurement. In other words, the degree of how closely the sparse sample features resemble the training dataset determines how we classify a given data point.
The most intuitive K-nearest neighbor classifier is to set the k = 1, or the one nearest neighbor classifier which assigns point a to the class of its closest neighbor in the feature space, Cn1nn (a) = Y (1) (1)
Thus, k-nearest neighbor classifier could be considered as a generalized weighted nearest neighbor classifier where the assignment of k nearest neighbors is a weight of k1 and all others weigh zero. Specifically, Íin=1 wni = 1 represents the ith nearest neighbor is assigned with a weight of wni . Therefore, with the weighted score of the nearest neighbor classifier, the class of its closest neighbor in a feature space will denote as Cnwnn with weights {wni }in=1.
BM25 (Best Match) [
To get a document D’s BM25 score given a query Q, a weighting function for each query term qi ∈ Q and the document D is first calculated as follows: w(qi , D) = (k1 + 1) × T F (qi , D)
K + T F (qi , D) × (k3 + 1) × QT F (qi ) k3 + QT F (qi ) (2) where K = k1 × [(1 − b) + b × dl /avdl ], dl is the length of D, avdl is the average document length. k1, k3, b are parameters. I DF (qi ) = log (1 + N − DF (qi ) + 0.5 ). N is the number of indexed documents
DF (qi ) + 0.5 in the collection. DF (qi ) is the number of documents containing qi . T F (qi , D) is the number of occurrence of qi in D, and QT F (qi ) is the number of occurrence of qi in Q. A document D’s BM25 similarity score given a query Q is calculated as the sum of D’s weight for each Q’s term: × I DF (qi ) |Q | Õ i=1 BM25(Q, D) = w(qi , D), (3) where w is the term weight obtained from the above Equation (2), |Q | is the number of terms in Q. 3.2
In our program, k of our KNN classifier is set as a parameter with respect to a given query. The output of searcher using BM25 model will return at most k top matches. And these top matched products’ categoy id paths are the input of our KNN classifier. In other words, an input of our KNN algorithm consists of category id paths of k closest training titles given a test title. And the output of our KNN algorithm is the majority category id path among category id paths of those training titles, i.e. the category with highest occurrence. We wanted to examine whether it was efective to use a flat classification structure to solve the given problem instead of a hierarchical one. Thus, all items in the product list are classified in one shot.
A BM25 similarity score is calculated for each title in the training set and a title in test set. In KNN paradigm, the similarity function of our approach is the BM25 similarity score between an item title in test set and an item title in training set. The higher the BM25 score, the more similar a training title and a test title. We tried setting diferent values of k in KNN to see whether or not predicting based on individual match is better than on multiple matches, since the individual match may be an outlier. Our KNN+BM25 algorithm is shown in the upper part of Table 1.
Suppose pi is a product in the training dataset T R. pi contains product title pti and product category id path ci . tj is a product title in the test dataset T E. N is the number of products in T R. When k = 1, we assign the category id path c1 of the top 1 matched training title (document), i.e. the title pt1 with highest BM25 similarity score given that test title (query) t , as the predicted category id path pc: pc = c1 where BM25(t , pt1) = maxm ∈ {1,2, ..., N } BM25(t , ptm )
Generally, when k > 1, we assign the majority category id path of returned top n (n ≤ k, since it is possible that the number of matches is less than k) products’ category id paths {c1, c2, ..., cn }. Specifically, the algorithm finds the distinct category id paths {dc1, dc2, ..., dci } ⊂ {c1, c2, ..., cn }(i ≤ n) and their number of occurrences {Occur (dc1), Occur (dc2), ..., Occur (dci )} (Ími=1 Occur (dcm ) = n). The distinct category id path dcj with the highest number of occurrences among the category id paths of the top k matched training titles given a test title is deemed the predicted category id path pc: pc = dcj where
Occur (dcj ) =
max q ∈ {1,2, ...,i }
(4) If the category id paths have same number of occurrence within the top matched training titles, we assign the category id path of the higher ranked matched training title(s) as predicted category id path. For example, if
Occur (dc1) = Occur (dc2) =
max q ∈ {1,2, ...,i }
(5) , then dc1 is the predicted category id path. If no match is found (n = 0), we assign "2296>3597>689" as predicted category id path, which corresponds to "Media>Music>Pop" (manually judging from training data and Rakuten website1).
Here is an example to show a typical product listing in our dataset. We set k1 = 1.2, b = 0.92 in BM25. As shown in Fig.2, given this item (query) in test dataset: "Sterling Silver Dangle Ball Earrings w/ Brilliant Cut CZ Stones & Yellow Topaz-colored Crystal Balls, 1"" (26 mm) tall" 1https://www.rakuten.com function KNN_BM25(q, DC, k) returns predicted category id path inputs: q: the query (test title)
DC: the document collection of product titles and corresponding category id paths k: the k value in KNN algorithm local variables: pj : the jth matched training product containing ptj (product title) and cj (its corresponding category id path) pc: the predicted category id path search q in DC with BM25 IR model get top n (n ≤ k) matches {pt1, pt2, ..., ptn } ⊂ DC and corresponding {c1, c2, ..., cn } if n equals 0 then
set pc as "2296>3597>689" else
set pc as the majority category id path of {c1, c2, ..., cn } end if return pc procedure Main_program(T R, T E, k) returns prediction file inputs: T R: the training dataset
T E: the test dataset k: the k value for KNN algorithm local variables: pj : the jth training product containing ptj (product title) and cj (its corresponding category id path) tj : the jth test product title pcj : the predicted category id path of tj for each pj ∈ T R do preprocess ptj tokenize ptj normalize ptj lowercase ptj index ptj store (ptj , cj ) in DocumentCollection end for for each tj ∈ T E do preprocess tj and store it in temp_t get pcj through KNN_BM25(temp_t , DocumentCollection, k) write tj and pcj in prediction file end for
If we set k = 10, then the searcher will return the item’s top 10 matches in training set according to BM25 similarity score of a document and the query in descending order as shown in Table 2 below.
As an illustration, the term weight for the matched term "sterling" (q1) in the top 1 document (D1) is calculated as follows: Ranking Product Title Category Id Path
BM25 score 1 2 3 4 5 6 7 8 9 10
The KNN algorithm (majority voting) then counts the occurrences of the categories within these matches. As shown in Table 3 below, "1608>2320>2173>2878" (corresponding to "Clothing, Shoes & Accessories>Jewelry & Watches>Earrings>Stud Earrings") has the highest number of occurrences among the top 1/3/5/7/10 matches’ categories. Thus, the category ’1608>2320>2173>2878’ is assigned as the predicted category id path when our KNN algorithm’s k is set to 1/3/5/7/10. We have mannually verified on the Rakuten website2 that this prediction is correct. Based on the classifier as above, we actually implement a system for the classifier in action. Figure 1 is a pictorial description of the system, where ovals are functional components, cylinder is index and rounded rectangles are data inputs/outputs in interaction with the classifier system. Specifically, input product can be efectively categorized through searching the index of product titles in training dataset. Training data are preprocessed and tokenized to get to a word-based index pool. Given a query, the system calculates the BM25 relevance score of the given product title and training titles, and categorizes it into the category of its most relevant product title(s) in training set. The implementation is in JAVA. We explored diferent approaches and strategies for minimizing the classification error and matching the product categories with high accuracy.
More precisely, as shown in Figure 1 and lower part of Table 1, major flow of the product categorizing system is as follows:
First, the Rakuten Training Dataset T R (800,000 product titles with category id paths) in tsv format is read line by line as document inputs. Each document pj ∈ T R has two fields, one for product title
Candidate Category Id Path
Candidate Category 1608>2320>2173>2878 1608>2320>498>1546 1608>2320>2173>3881
1608>2320>3648 1608>2320>2495>3682
Clothing, Shoes & Accessories>Jewelry & Watches>Earrings>Stud Earrings 1 Clothing, Shoes & Accessories>Jewelry & Watches>Pendants & Neck- 0 laces>Pendants Clothing, Shoes & Accessories>Jewelry & Watches>Earrings>Earring Sets 0 Clothing, Shoes & Accessories>Jewelry & Watches>Rings 0 Clothing, Shoes & Accessories>Jewelry & Watches>Accessories>Individual 0 Charms ptj and one for category id path cj . Second, documents’ product titles ptj are preprocessed. Specifically, "w/out" was replaced by "without", "w/" was replaced by "with", "&" was replaced by "and", "’" was replaced by "feet" and """" was replaced by "inches". After that, documents’ product titles ptj and category id paths cj are indexed in text field and string field respectively. Product titles ptj in text fields are analyzed by Lucene Standard Analyzer. Specifically, they are tokenized by Lucene’s standard tokenizer, before being normalized by Lucene’s standard filter and turned into lowercase by lowercase filter. In contrast, category id paths cj in string fields are not analyzed, since they are target categories for later classification. After that, Test Dataset T E (200,000 product titles without category id paths) is read line by line as query inputs. Same as the training data, test titles tj ∈ T E are preprocessed in the same way. Then, the searcher searches the index with test title tj with BM25 similarity to get top n (n ≤ k) most relevant training titles {pt1, ..., ptn } and their corresponding category id paths {c1, ..., cn }. This is followed by our KNN algorithm (as shown in upper part of Table 1) that returns the most frequent category id path among top n matched training title(s)’ category id paths {c1, c2, ..., cn } given a test title tj as predicted category id path pcj . Finally, test titles and their predicted category id paths are written in a tsv file. 4
In this section, we test our system on Rakuten data. Experimental set-ups are introduced first, results obtained are analyzed. We specifically tested on diferent k values in KNN and diferent values of k1 and b in BM25 for their impacts on efectiveness of the classifier and the system. 4.1
Experiments were mainly done on a laptop with 4GB RAM. We trained the K nearest neighbors algorithm using the Rakuten 800,000 product listings in tsv format provided. And we used the Java program to exercise the experiments. Lucene is an open-source information retrieval (IR) software library which is empowered to do full text indexing and full text searching capability. This architecture is built on the idea of a document with fields of text. We exercise our experiments on top of the Lucene API in order to get a full product list search for the most accurate result of product categorization.
We tried setting diferent values of k in KNN to see whether or not predicting based on individual match (k = 1) is better than The results in Table 4 above show the oficial results of our primary submissions. In this classification problem, the experimental results are evaluated with weighted-{precision (P), recall (R) and F1 score} respectively. Precision is an evaluation of the fraction of relevant items among all retrieved times; Recall is an evaluation of the fraction of relevant items that have been retrieved over the total amount of the relevant items. And the F1 Score is a measure of the accuracy of the test. In our experiment, with the setting of parameter k = 3 in KNN classification algorithm, our program achieved 0.79, 0.78 and 0.78 for the weighted-{P, R and F1 score} respectively in a subset of the test dataset. The results of k=1, 3 and 5 are roughly the same, because the top document matches of a query are highly similar to each other and thus have high probability of belonging to the same category. Also, the results for k = 3 rather than k = 1 is the best one among diferent settings of k, because the top documents have high probability to have the same BM25 similarity score and thus the top 1 document’s category may be an outlier. Generally, we can see that the prediction result declines as k increases, since titles with lower similarity are less likely to belong to the same category, as shown in the Example in Section 3.2.
Aside from tuning k in KNN, we have tried to tune the parameters of the BM25 IR model to get higher classification accuracy. We found a slight diference in between the tuning of the parameters. Specifically, with the same setting of k = 1 in KNN algorithm, by setting k1 = 1.2, b=0.35, we achieved slightly lower results of (0.78, 0.77, 0.77) for weighted-{P, R and F1 score} respectively than those of the default parameters (k1 = 1.2, b = 0.75) which get (0.78, 0.78, 0.78) for weighted-{P, R and F1 score} respectively. Also, we splited the training dataset into 2 parts, 1 as training set (1-in-2-TRAIN) and 1 as testing set (2-in-2-TEST)(category id paths are removed) and gold standard (2-in-2-GOLD). Then, we conducted parameter tuning by fixing k for KNN to 3, k1 to 1.2 and changing the value of b. We found the optimal weighted-F1 score is obtained when b = 0.92 or 0.93.
We have also compared results of using the stopword filter in Lucene’s standard analyzer to those of not using it. We found that using stopword filter would slightly reduce the results, since after stop word removal, documents (training titles) may have no terms.
Apart from the BM25 model, we also used Lucene’s VSM
(default setting, parameter-free) to conduct searching on the product
list. When k is set to 1 in KNN, the results (0.77, 0.77, 0.77) are
slightly lower than those of BM25 IR model on a subset of the test
dataset. This is because compared to VSM that only incorporates
term frequency (TF) and inverse document frequency (IDF), BM25
also takes the average document length (avdl) into account , which
leads to higher accuracy rate as results. We also tried Lucene’s
implementation of Dirichlet Language Model [
In this paper, we described our taxonomy classification system based on KNN with Lucene BM25 similarity score.
The insights from participating this competition are as follows: IR model can be used as similarity function in KNN to generate competitive prediction results.
For future work, we are going to incorporate word associations
into our analysis by adding algorithms like bigram or Word2Vec
skip-gram [
We gratefully acknowledge the support by NSERC (Natural Sciences and Engineering Research Council of Canada) CREATE (Collaborative Research and Training Experience Program) award in ADERSIM (Advanced Disaster, Emergency and Rapid-response Simulation)3, ORF-RE (Ontario Research Fund - Research excellence)4 award in BRAIN (Big Data Research, Analytics, and Information Network) Alliance5, and the Research Chair Program at York University, Canada. 5 http://www.brainalliance.ca/