Accurate prediction of air quality is essential for public health and environmental management in Taiwan. This study proposes a spatial-temporal modeling approach to predict next-day Air Quality Index (AQI) in Taiwan. Counties were first clustered based on pollutant data distributions, using statistical measures including mean, median, skewness, and kurtosis, to capture regions with similar air quality patterns. Spatial correlation analysis using Moran’s I confirmed significant positive spatial autocorrelation of AQI values across Taiwan. Predictive models—including Long Short-Term Memory (LSTM), Random Forest, XGBoost, Spatio-Temporal Dynamic Graph Convolutional Network (STDGCN), and a combined Geographically Weighted Regression with LSTM (GWR+LSTM) model—were evaluated. Results indicate that STDGCN achieved the highest predictive performance, followed by XGBoost, Random Forest, GWR+LSTM, and LSTM. The results also show that O3 also consistently influences AQI besides the PM pollutant. These findings highlight the importance of incorporating both spatial dependencies and pollutant distribution characteristics in modeling air quality, offering an effective tool for forecasting and environmental policy planning.