Explosive increase of industrial data collected from sensors has brought increasing attractions to the data-driven predictive maintenance for industrial machines in cyber-physical systems (CPSs). Since machinery faults are always caused by performance deterioration of components, learning the deteriorating mode from observed sensor data facilitates the prognostics of impeding faults and predicting the remaining useful life (RUL). In modern CPSs, several key performance indicators (KPIs) are monitored to detect the corresponding fine-grained deteriorating modes of industrial machines. However, the overall deterioration estimation and RUL prediction based on these KPIs with various patterns have been a great challenge, especially without labels of deteriorating index or uninterpretable of root causes. In this paper, we proposed K-PdM, a cluster-based hidden Markov model for the machinery deterioration estimation and RUL prediction based on multiple KPIs. The method uncovers the fine-grained deteriorating modes of machines through each unlabeled KPI data and learns a mapping between each deteriorating KPI index and RULs. Accordingly, an overall deterioration estimation and RUL prediction of machine are able to be achieved based on the combination of each KPI's deterioration estimation. Moreover, a set of interpretable semantic rules are setup to analyze the root cause of performance deterioration among KPIs. An experimental application is proposed to demonstrate its applicability based on the PHM08 data sets. The obtained results show their effectiveness to predict the RULs of machines.