Compressed kNN for Efficient Classification: A Review and Application to Social Media Emotion Analysis

Written by: Sang Ah Lee, Natalie Leung, Louisa Stumpf, & Ananya Yallapragada

Our group was looking for papers related to our project on Emotional Complexity Fingerprints. The goal of our project is to analyze whether emotion can serve as an element in identifying different community segments in social media. We will analyze the Google GoEmotions dataset

to identify clusters of communities based on their emotional distributions. The second part of the project focuses on determining which community segment a subreddit belongs to. We came across a research paper written by Jaime Salvador-Meneses, Zoila Ruiz-Chavez, and Jose Garcia Rodriguez, titled Compressed kNN: K-Nearest Neighbors with Data Compression [7].

KEY TOPICS

kNN (k-nearest neighbors) classification algorithm, compression

ABOUT THE PAPER

The MDPI (Multidisciplinary Digital Publishing Institute), a Switzerland-based publisher of open-access scientific journals, published the paper in Entropy, an international and interdisciplinary peer-reviewed open access journal from MDPI, on February 28, 2019. The paper was Jaime Salvador-Meneses’ PhD paper. The paper received no outside funding and was solely supported directly by Universidad Central del Ecuador (UCE) funds.

ABOUT THE AUTHORS

Jaime Salvador-Meneses is the current Managing Director at the Central University of Ecuador, with expertise in Machine Learning, Data science, Data Clustering, and Classification [6].

Zoila Ruiz-Chavez is part of the Faculty of Engineering at the Central University of Ecuador, and is involved in other papers related to agent-based modeling and GIS [5, 6].

Jose Garcia-Rodriguez is currently a professor at the University of Alicante within the Department of Informatics and Computing. He has authored more than 250 publications, and primary research topics include Computer Vision, Machine Learning, and Pattern Recognition [1].

The three authors have worked together for 11 publications. They have co-authored papers on categorical big data process and ML methods to improve categorical data classification, which helped build their foundation of the kNN methodology used for the current paper we are analyzing.

DATASETS USED

CIDS: Census income data set

WBC: Wisconsin breast cancer (original)

SUMMARY

WBC and CIDS were two datasets used for the research. WBC-original consisted of categorical variables, and CIDS consisted of both categorical and numeric variables.

The paper proposes a variation of the kNN algorithm. This algorithm focuses on compressing the categorical data. They applied bit-level compression before applying kNN classification. In this method, the dataset is held in memory, thereby reducing the memory strain that the kNN suffers from. They addressed the issue of the limitation of kNN.

The paper preprocesses the dataset to determine the number of bits needed to represent each categorical variable in the Wisconsin Breast Cancer (WBC) dataset and the Census Income (CI) Dataset. They then condense the dataset by transforming the multiple attribute values into 32-bit-level blocks. KNN is utilized to run on the 32-bit-level blocks and decompress individual observations during the distance calculations of Hamming and HEOM. Most kNN approaches involve using the full uncompressed dataset in memory. Their method allows for less memory usage. KNN uses an 80/20 data split on the train and test data, respectively, and uses a 10-fold cross-validation across the k values of 5, 10, 15, and 20.

The results showed that memory consumption decreased by 13.9% for the WBC dataset and 42.9% for the CI dataset. The classification accuracy remained the same compared to the standard application of kNN with no compression done. One thing to note is that the processing time was slightly slower using this compression and decompression method. The paper argues that the trade-off of processing time is worth it for the memory savings the approach gives. It is especially beneficial for larger datasets, as it solves kNN’s memory limitation.

KEY POINTS

Compressing the categorical data at the bit-level reduced the physical size of the dataset drastically, regardless of the dataset used. The classification accuracy percentage is also maintained.

How Compressed and Uncompressed WBC datasets have similar accuracy rates. Table by Paper [7].

How Compressed and Uncompressed CID datasets have similar accuracy rates. Table by Paper [7].

Additionally, this research focuses on avoiding dataset reduction. In traditional kNN methods, the dataset size is reduced to handle memory. It can cause loss of information, affecting the model. By compressing the dataset, the data is not discarded and retains all the information while still being relatively memory-efficient.

There is also a trade-off between speed and memory. Since this research proposes real-time decompression, there is a slight processing overhead. However, we do see improvements in memory efficiency, highlighting an important insight that there is always a trade-off between speed and accuracy during optimization.

OBSERVATIONS AND SUGGESTIONS

PEER REVIEW

We observed that the tables support the results between compressed and uncompressed datasets. They allow the audience to see the differences and similarities clearly. The research also focuses exclusively on categorical data.

The tests have been performed on UCI datasets, which are well-known and relatively small compared to other real-world datasets. Usually, real-world data is a combination of both numerical and categorical data; it would be more interesting to test on a dataset consisting of millions of rows.

Another suggestion is to update the GitHub link as it is no longer accessible.

INDUSTRY-COMMERCIAL VIABILITY

The research has the ability to make the memory usage more efficient. Companies can significantly reduce their hardware and computation costs. The algorithm efficiently packs the data, making it ideal for embedding and use in mobile applications, IoT devices, and other devices with limited hardware.

There is a balance between overhead and performance by also having an ‘on-the-fly’ decompression, combined with a local cache. However, there are some limitations. The authors mention a slight decrease in processing speed due to real-time compression. Moreover, if there are too many categorical variables, the bit-packet approach becomes less efficient. Overall, from a board perspective, this idea is ‘low-level’ optimization, which does have some commercial appeal.

CODING

There may be reproducibility issues as the GitHub and SMILE links are broken as well.

However, based on the description in the paper, we came up with our approach. We outlined our coding process in the following image.

Coding Process Outline. Image by Authors using draw.io.

From categorical attributes of the WBC dataset, we would find the max number of categories a single attribute has to calculate M, the number of bits it needs to represent that value. Based on the paper, we should find that M is equal to 4. We will assume the block size for the dataset is a 32 bit integer block based on the paper’s agreement. From these values, we can calculate that we can store 9 attributes from the dataset into 2 blocks. The dataset itself can be represented by two 1D vectors with the first vectors holding information about the first eight variables and second vectors holding info about the ninth variable. Then, we will apply Hamming and HEOM distance functions to decompress the two vectors when they are compared. We would then code to compress the original dataset. The dataset is now ready for applying kNN classification. Each test will compute distances in comparison to the training observations using the distance functions mentioned earlier. We will then sort distances in ascending order and take the most repeated class of the top k first elements. For kNN implementation specifically, we use two variations of the algorithm. One is the linear search that is a brute force linear nearest neighbor search. The other is a cover search, which involves a tree data structure for fast nearest neighbor operations in general n-point metric spaces [7]. Afterwards, we will split the dataset for training and testing using an 80/20 split. The paper specifies a 10-fold cross validation across k values 5–20 in increments of 5. To evaluate the effectiveness of the model, we will perform calculations on the accuracy and execution time.

CONNECTION TO OUR PROJECT

Our project uses 5-fold cross-validation, and the paper uses the same approach but with 10-fold cross-validation with different k values. The paper notes the kNN scalability constraints, which were covered in our Machine Learning class. It mentions how kNN depends on the selection of k and is a lazy learning method. Moreover, kNN consumes a lot of memory. An interesting concept we can apply to our project is the distance calculation. The paper found that the distance calculation for compressed categorical data increases classification time by a small amount. It is an approach we can potentially include in our project. The usage of compressing our data before applying kNN is useful, but our project dataset is not as applicable, given that our data is not in bits. Therefore, this part of the paper’s implementation will not be used.

REFERENCES

[1] Garcia, J. (n.d.). Profile. SciProfiles. https://sciprofiles.com/profile/jgr

[2] MDPI. (n.d.). Entropy journal. https://www.mdpi.com/journal/entropy

[3] MDPI. (n.d.). About MDPI. https://www.mdpi.com/about

[4] Ruiz-Chavez, Z. (n.d.). Author profile. IEEE Xplore. https://ieeexplore.ieee.org/document/8580326

[5] Ruiz-Chavez, Z. (n.d.). Scientific contributions. ResearchGate. https://www.researchgate.net/scientific-contributions/Zoila-Ruiz-Chavez-2147698102

[6] Salvador-Meneses, J. (n.d.). Profile. ResearchGate. https://www.researchgate.net/profile/Jaime-Salvador-Meneses

[7] Salvador-Meneses, J., Ruiz-Chavez, Z., & Garcia-Rodriguez, J. (2019). Compressed kNN: K-nearest neighbors with data compression. Entropy, 21(3), 234. https://doi.org/10.3390/e21030234