The paper explores the domain of lossy compression, specifically incorporating data mining techniques in the process of image encoding. Clustering is employed to group similar pixels in the image and henceforth use cluster labels in compressing the image. The proposed approach replaces the Discrete Cosine Transform phase of Conventional JPEG with a combination of clustering and Run Length Encoding so as to handle redundant data in the image effectively. Simulation with respect to benchmark data indicates improved compression (42.5%) in relation to existing solutions. Image quality metrices such as PSNR, structural similarity have also been tested and it is observed that the proposed approach achieves significant compression ratio with negligible loss in visual quality. © 2021 John Wiley & Sons, Ltd.