Health has always been one of the most important concerns of human. The goal in this research is to know what factors cause and affect patient satisfaction in the relationship between a physician and patient. Since this relationship is a form of healthcare service, the SERVQUAL service quality assessment method has been used as a framework. However the questions have been reviewed based on the previous literature and the experts’ views, leading to a questionnaire designed for the healthcare domain. Data collection has been performed using the questionnaires on subjects selected amongst clients of Rhinoplasty Centers in Tehran. To analyze the data, three machine-learning approaches have been implemented namely Decision Tree, Support Vector Machine and Artificial Neural Networks. A number of possible factors affecting the patient-physician relationship have been used as input and patient satisfaction has been taken as output. Comparing the results of these three methods, Artificial Neural Networks method is shown to have better performance, which has therefore been used for prioritizing the effective factors in this relationship. The results indicate that reaching the information which the patient expects their physician to give is the most effective characteristic in patient satisfaction. The rank of gained features were compared with similar researches. The outcome was very similar and approved the results.