To classify proteins into functional families based on their primary sequences, existing classification algorithms such as the k-NN, HMM and SVM-based algorithms are often used. For most of these algorithms to perform their tasks, protein sequences need to be properly aligned first. Since the alignment process is error-prone, protein classification may not be performed very accurately. In addition to the request for accurate alignment, many existing approaches require additional techniques to decompose a protein multi-class classification problem into a number of binary problems. This may slow the learning process when the number of classes being handled is large. For these reasons, we propose an effective data mining technique in this paper. This technique has been applied in real protein sequence classification tasks. Experimental results show that it can effectively classify unaligned protein sequences into corresponding functional families and the patterns it discovered during the training process have been found to be biologically meaningful. They can lead to better understanding of protein functions and can also allow functionally significant structural features of different protein families to be better characterized.