KAI Access merupakan aplikasi untuk mempermudah pengguna dalam mengakses layanan dan informasi terkait tiket perjalanan kereta api. KAI Access memiliki fitur ulasan beraneka ragam yang merupakan wadah bagi pengguna untuk memberikan feedback. Pada penelitian ini akan dilakukan analisis sentimen terhadap data ulasan KAI Access sejumlah 8713 data ulasan. Metode yang digunakan yaitu multinomial naïve bayes dan metode levenshtein distance. Dari kombinasi metode tersebut diharapkan dapat meningkatkan hasil klasifikasi. Seluruh data akan dilakukan pemodelan menggunakan metode K Fold Cross Validation dengan nilai k=2,3,4,5,6,7,8,9 dan 10. Berdasarkan hasil pengujian menggunakan multinomial naïve bayes diperoleh nilai tertinggi yaitu accuracy sebesar 92%, tingkat precision sebesar 60% dan tingkat recall sebesar 45%. Sedangkan kombinasi metode multinomial naïve bayes-levesnhtein distance mengalami peningkatan pada pengujian K-ke 9 yang awalnya menggunakan multinomial naïve bayes saja mendapatkan nilai accuracy 83%, precision 59% dan recall 44%, kemudian meningkat ketika menggunakan kombinasi metode levenshtein distance sebesar accuracy 84%, precision 60% dan recall 46%. Proses pengujian yang telah dilakukan dapat disimpulkan bahwa optimasi multinomial naïve bayes menggunakan levenshtein distance meningkatkan hasil accuracy, precision dan recall sebesar 1-2%.