Public transportation has been regarded as one of the most sustainable forms of transport, because of which local governments have put efforts in increasing the mode share of public transportation. Recently, not only level of service but also user satisfaction has been focused on for the assessment of transport policy; however, several points have been overlooked in previous research, such as attribute-based satisfaction, the relationship between level of service and satisfaction, and user expectation. This paper deals with these issues while assuming the heterogeneity of satisfaction, which is an indicator of perception. Out-of-vehicle times, particularly headway and access time, were selected in the analysis because they can affect travel behavior of current and potential public transportation customers. In this analysis, pattern-recognition models were applied, and public transportation users were segmented in terms of perception. The results suggest several notable recommendations for public transport policies and investigations.