WLAN location estimation based on 802.11 signal strength is becoming increasingly prevalent in today?s pervasive computing applications. As an alternative to the well-established deterministic approaches, probabilistic location determination techniques show good performance and thus become increasingly popular. For these techniques to achieve a high level of accuracy, however, adequate training samples should be collected offline for calibration. As a result, a great amount of manual effort is incurred. In this paper, we aim to solve the problem by reducing both the sampling time and the number of locations sampled in constructing the radio map. A learning algorithm is proposed to build location estimation systems based on a small fraction of the calibration data that traditional techniques require and a collection of user traces that can be cheaply obtained. Our experiments show that unlabeled user traces can be used to compensate for the effects of reducing calibration effort and can even improve the system performance. Consequently, manual effort can be significantly reduced while a high level of accuracy is still achieved.