The problems of existing ways in identifying the key parameters of quad-rotor UAVs in the frequency domain are that it is hard to guarantee the bandwidth and accuracy at the same time and the identification process is inefficient. To solve these problems, an improved identification algorithm in the frequency domain was proposed. Firstly, the system model of the quad-rotor UAVs under hovering conditions was built. Then, based on the measured data obtained from the quad-rotor UAV platform, the frequency response was obtained by the composite-window disposal. Finally, a kind of pattern search algorithm, K-means clustering algorithm, was applied to the identification process, and the state-space model of the quad-rotor UAVs was obtained. The result showed that, the proposed method could balance the accuracy and complexity of the identification, and the frequency response of the identified model could fit the actual model of the quad-rotor UAVs well.