《数据挖掘概念与技术》（第二版） 习题5.1（d）答案

证明：apriori 的一种变形将事务数据库D中的事务划分成n个不重叠的部分,那么在D中是频繁的任何项集至少在D的一个部分中是频繁的。

 

证明：采用反证法。

      假设D中的每个部分均不含有频繁项集

      令F为D中一个频繁项集，D为为数据库中一系列的事务，C为D中事务的总数，A为D中包含F项集的事务的总数，min_sup为最小支持度。

     因为F是频繁项集，即有A=C*min_sup

     我们将D划分成n个不重叠的部分，分别为d₁,d₂,d₃,…..d_n，因此有D=d₁d₂d₃…d_n

     设d₁,d₂,d₃,…d_n中的事务总数分别为c₁,c₂,c₃,…c_n

     设a₁,a₂,a₃,…a_n为d₁,d₂,d₃,...d_n中分别包含项集F的事务数量，因此有A=a₁+a₂+a₃+…+a_n

     由A=C*min_sup得（a₁+a₂+a₃+…+a_n）=（c₁+c₂+c₃+…+c_n）*min_sup。由假设条件可知，F在D中的每一部分都是非频繁的，也就意味着

     a₁<c₁*min_sup;

     a₂<c₂*min_sup;

     a₃<c₃*min_sup;

             …

     a_n<c_n*min_sup

        将上述不等式相加得到（a₁+a₂+a₃+…+a_n）<（c₁+c₂+c₃+…+c_n）*min_sup，或者简记为A<C*min_sup，也就是说F为非频繁项集，这与假设条件相反，故假设不成立，故有D中的任一频繁项集至少在D的一个部分中是频繁的。