The increasing demand of indoor location based service (LBS) has promoted the development of localization techniques. As an important alternative, fingerprinting localization technique can achieve higher localization accuracy than traditional trilateration and triangulation algorithms. However, it is computational expensive to construct the fingerprint database in the offline phase, which limits its applications. In this paper, we propose an efficient indoor positioning system that uses a new empirical propagation model, called regional propagation model (RPM), which is based on the cluster based propagation model theory. The system first collects the sparse fingerprints at some certain reference points (RPs) in the whole testing scenario. Then affinity propagation clustering algorithm operates on the sparse fingerprints to automatically divide the whole scenario into several clusters or sub-regions. The parameters of RPM are obtained in the next step and are further used to recover the entire fingerprint database. Finally, the location estimation is obtained through the weighted k-nearest neighbor algorithm (WkNN) in the online localization phase. We also theoretically analyze the localization accuracy of the proposed algorithm. The numerical results demonstrate that the proposed propagation model can predict the received signal strength (RSS) values more accurately than other models. Furthermore, experiments also show that the proposed positioning system achieves higher localization accuracy than other existing systems while cutting workload of fingerprint calibration by more than 50% in the offline phase.