This paper presents a novel method to reduce the recalibration costs of a radio map by automatically updating the radio map. The appearance frequencies of access points (APs) detected from user feedback data are mainly used for the update. The proposed method appeared superior to previous methods, especially in its ability to update newly installed APs in the radio map. According to the experiment conducted for the radio map of 233 Seoul subway stops, the proposed method was effective for updating APs with weak as well as strong signal strengths.