In this paper we introduce a generalization of association rules: change profiles. We analyze their properties, describe their relationship to other structures in pattern discovery and sketch their possible applications. We study how the frequent patterns can be clustered based on their change profiles and propose methods for approximating the frequencies of the patterns from the approximate change profiles and bounding the intervals where the frequencies of the patterns are guaranteed to be. We evaluate empirically the methods for estimating the frequencies and the stability of their frequency estimates under different kinds of noise.