Handwriting recognition is a main topic of Optical Character Recognition (OCR), which has a very wide application. Hidden Markov model is a popular model for handwriting recognition because of its effectiveness and robustness. In this paper, a hidden Markov model with parameter- optimized k-means clustering is proposed for handwriting recognition. Two deep features of the images of characters are explored, thus significantly boosts the effectiveness of k-means clustering. The experiments show that this model largely increases the average accuracy of HMM with k-means clustering to 83.5% when the number of clusters is 3000.