Sensors are the key element to enable smart electronics and will play an important role in the emerging big data era. In this work, we reported an experimental study and a data-analytical characterization method to enhance the precision of discriminating chemically and structurally similar gases. Graphene sensors were fabricated by conventional photolithography and measured with feature analysis against different chemicals. A new hidden Markov model assisted with frequency spectral analysis, and the Gaussian mixture model (K-GMM-HMM) is developed to discriminate similar gases. The results indicated that the new method achieved a high prediction accuracy of 94%, 27% higher than the maximum value obtained by the conventional methods or other feature transient analysis methods. This study indicated that graphene gas sensors with the new K-GMM-HMM analysis are very attractive for chemical discrimination used in future smart electronics.