1. A training data generation apparatus that generates training data used for creating characteristic expression extraction rules, comprising: a training data candidate clustering unit that clusters a plurality of training data candidates assigned labels indicating annotation classes based on feature values containing respective context information, and a training data generation unit that, by referring to each cluster obtained using the clustering results, obtains the distribution of the labels of the training data candidates within the cluster, identifies training data candidates that meet a preset condition based on the obtained distribution, and generates training data using the identified training data candidates.