Open (mass tolerant) search of tandem mass spectra shows great potential in the comprehensive detection of post-translational modifications in shotgun proteomics. However, this search strategy has not been widely used by the community, and one bottleneck of it is the lack of appropriate algorithms for automated and reliable post-processing of the coarse and error-prone search results. Here we present PTMiner, a software tool for confident filtering and localization of modifications (mass shifts) identified by open search. After mass-shift-grouped FDR control of peptide-spectrum matches (PSMs), PTMiner uses an empirical Bayesian method to localize modifications through iterative learning of the prior probabilities of each type of modification occurring on different amino acids. In the validation experiments on a large data set of simulated spectra, PTMiner effectively controlled the FDRs of individual modification groups, and achieved a total spectral identification rate four times higher than the classic FDR estimation method. At 1% real false localization rate (FLR), PTMiner localized 93.06% of the modifications, far higher than two used open search engines and the extended Ascore localization algorithm. We then used PTMiner to analyze the draft map of human proteome containing 25 million spectra from 30 tissues, and confidently identified over 1.7 million modified PSMs at 1% FDR and 1% FLR, which provided a system-wide view of both known and unknown modifications in the human proteome.