A 3M K-means algorithm for fast and practicably identifying COVID-19 close contacts

School of Information, Renmin University of China, Beijing, 100872, China

^* Corresponding author: fengzihuan@ruc.edu.cn.

Abstract

Given that the risk of the COVID-19 epidemic still exists and the flow of patients is difficult to monitor, identifying the people who have had close contact with the confirmed cases is important in anti-epidemic tasks whether in areas where the epidemic is developing rapidly or in areas where the epidemic has been phase-controlled. This article discusses how to locate people who have been in close contact with confirmed cases quickly and determine the risk of infection. From the perspective of the government, this work proposes a multi-snapshot multi-stage minority K-means (3M K-means) algorithm. This algorithm reduces the amount of data and considerably improves the speed of clustering by quickly ignoring the excluded risk classes and points in the process in the early stages, whereas traditional algorithms involve with O(N2) computational complexity which needs several days, impracticably for the COVID-19 urgent situations. The 3M algorithm greatly cuts down the computational time, thereof making the rapid warning of close contacts practicable. The methods are simple, yet efficient and practicable for the COVID-19 urgent situations The use of this algorithm can help control the COVID-19 epidemic, achieve significant cost savings, and provide the psychological guarantee of people for work resumption.