Parkinson's Disease (PD) is a neurodegenerative disease which involves both motor and non-motor symptoms. Non-motor mental symptoms are very common among patients with PD since the earliest stage. In this context, gait analysis allows to detect quantitative gait variables to distinguish patients affected by non-motor mental symptoms from patients without these symptoms. A cohort of 68 PD subjects (divided in two groups) was acquired through gait analysis (single and double task) and spatial temporal parameters were analysed; first with a statistical analysis and then with a machine learning (ML) approach. Single-task variables showed that 9 out of 16 spatial temporal features were statistically significant for the univariate statistical analysis (p-value< 0.05). Indeed, a statistically significant difference was found in stance phase (p-value=0.032), swing phase (p-value=0.042) and cycle length (p-value=0.03) of the dual task. The ML results confirmed the statistical analysis, in particular, the Decision Tree classifier showed the highest accuracy (80.9%) and also the highest scores in terms of specificity and precision. Our findings indicate that patients with non-motor mental symptoms display a worse gait pattern, mainly dominated by increased slowness and dynamic instability.