To survive in today’s market, decision makers including investors and their managerial teams should continuously attempt to realize the customers’ unspoken needs and requirements by discovering their behavioral patterns. Discovering customers’ patterns puts these decision makers in a better position in which higher qualified services can be designed and provided. Association rule mining is a well-known approach to discover these patterns. Although extracted rules could express customers’ behaviors in an easy-to-understand way, the number of rules in real applications could be problematic. Moreover, the customers’ comments are not usually considered for constructing/evaluating the rules. To tackle these issues, a system framework is proposed in this paper in which all association rules are clustered using a new similarity measure. For each cluster, a new type of graph is developed known as sub-graph in this paper. Each sub-graph has unique messages that can partially contribute to designing new services. Furthermore, for the first time, the real satisfaction levels are embedded into the association rules to enrich them in an innovative way. The main interesting point is that the satisfaction levels are only assessed for the overall system, not for current services. We also illustrate how our proposed methodology works through artificial and real datasets and also demonstrate the superiority of our proposed clustering algorithm compared to other popular methods.