Mechanical impedance, which changes with posture and muscle activations, characterizes how the central nervous system regulates the interaction with the environment. Traditional approaches to impedance estimation, based on averaging of movement kinetics, requires a large number of trials and may introduce bias to the estimation due to the high variability in a repeated or periodic movement. Here, we introduce a data-driven modeling technique to estimate joint impedance considering the large gait variability. The proposed method can be used to estimate impedance in both the stance and swing phases of walking. A 2-pass clustering approach is used to extract groups of unperturbed gait data and estimate candidate baselines. Then patterns of perturbed data are matched with the most similar unperturbed baseline. The kinematic and torque deviations from the baselines are regressed locally to compute joint impedance at different gait phases. Simulations using the trajectory data of a subject's gait at different speeds demonstrate a more accurate estimation of ankle stiffness and damping with the proposed clustering-based method when compared with two methods: i) using average unperturbed baselines, and ii) matching shifted and scaled average unperturbed velocity baselines. Furthermore, the proposed method requires fewer trials than methods based on average unperturbed baselines. The experimental results on human hip impedance estimation show the feasibility of clustering-based technique and verifies that it reduces the estimation variability.