数据挖掘如何从挖掘事实（fact）成长为挖掘洞见（insight）？
渐进采样法，在英文论文里一般叫progressive sampling，它的思路很简单： 第一步：随便设置一个样本量 n ，采样； 第二步：从样本处聚类出一个结果； 第三步：在原样本中增加 0.1n 大小的新样本（也可以是其他值），即 n=1.1n ，再采样； 第四步：从新样本中聚类出一个结果，计算新结果和旧结果间的差异 \epsilon （差异度的计算方法自选，比如计算新旧聚类中心的欧式距离最大值等）； 第五步：反复进行第三步和第四步，直至新旧结果间的差异落入你可忍受的阈值内。 直观来看，当你的样本量不断变大时， \epsilon 会越来越小越来越小，和下面那张图一样。 统计学习理论法的思想是 PAC（概率近似正确）。 针对大小为 N 的待聚类数据 D ，和聚类中心集合 V=\{v_1,v_2,...,v_k\} ，先确定一个评价聚类好坏的函数 R(D,V)=\frac{1}{N}\sum_{x\in D}r(x,V) ， 其中 r(x,V) 代表聚类中心集合 V 对某条数据 x 的适应程度或不适应程度，整个聚类过程可以抽象为：在最大化或最小化 R(D,V) 比如 K-means 聚类，它的本质，是在优化下面这个函数，并使其最小化 R(D,V)=\frac{1}{N}\sum_{x\in D}\left(\min_{v\in V}||x-v||^2\right) 好了，让我们进入正题。 假设 D 异常大，需要用采样来减少规模，设随机采样的样本为 S，我们希望 \Pr(|R(D,V)-R(S,V)|\ge \epsilon)\le \delta ，（1） 其中 \epsilon 是我们设置的最大错误阈值， \delta 是超出 \epsilon 的最大概率。那么，多大的样本才能满足这个公式呢？ 首先我们来熟悉一个公式，即Hoeffding不等式：假设一个随机变量 x\in[0,1] ，它的期望是 E(x) ，它在样本 S 中的均值是 E_S(x) ，那么有 \Pr(|E(x)-E_S(x)|\ge\epsilon)\ge 2\exp(-2n\epsilon^2) 。（2） 这个不等式的证明很容易搜到，比较复杂，这里暂不展开。 我们假设所有的r(x,V)都进行过归一化处理了，即其大于等于0，小于等于1。 1.2.1 只考虑一个 V 根据Hoeffding不等式，如果我们只考虑一个V ，（1）成立的条件便是 2\exp(-2n\epsilon^2)\le\delta  ， 即 n\ge \frac{1}{2\epsilon^2}\ln\frac{2}{\delta} 。 1.2.2 考虑有限个 V 如果我们考虑解空间内的 V ，且假设解空间 \mathcal V 是有限的，那么，考虑到 \begin{split} &\Pr\left(\sup_{V\in\mathcal V} |R(D,V)-R(S,V)|\ge \epsilon\right)\\ &\le \sum_{V\in \mathcal V}\Pr\left(|R(D,V)-R(S,V)|\ge \epsilon\right)\\ &\le 2|\mathcal V|\exp(-2n\epsilon^2) \end{split} ， （1）成立的条件便是 n\ge \frac{1}{2\epsilon^2}\ln\frac{2|\mathcal V|}{\delta} 。 1.2.3 考虑无限个 V 现在来考虑最复杂的情况，即解空间 \mathcal V 是无限的。 针对这种情况，我们总可以假设任意一个聚类中心 v 的解空间 \textbf{v} 是有边界的，然后将\textbf{v}等分切割为 M 份，将每一个等分子空间的中心组合为一个新的\textbf{v}'。 以下面这个图为例，如果类中心是二维的，我们可以用一个正方形把它的可能值域\textbf{v}套起来，可以把它划分成一个4乘4的棋盘，棋盘的每一格就是一个等分子空间，绿色的点就是每个子空间的中心，所有绿色的点就能组成\textbf{v}'。 如果聚类中心只从\textbf{v}'中选，那么对应的聚类中心集合 \mathcal V' 就是有限的，而且有 |\mathcal V'|=C_{M}^{k} ， 就能计算出针对 \mathcal V' ，满足（1）的样本规模。 然后，我们切割\textbf{v}' 的时候，要确保每个子空间内的任意一点到该子空间中心的距离小于 \epsilon' 。 这样就能通过（1）和 \epsilon' 确保 \mathcal V 中每个 V 在样本大小为 n 时的有效性了。 这部分详细可参照论文： 聚类一般都是用定量的方法，即使是引入定性思想，也是通过一个模糊数学的方法将定性因素转为定量计算。 通俗地说，就是特征越多越好，因为特征越多，数据的稀疏性越好，类与类之间的差别就能拉地更大，下面我们我们用一张图来举个例子： 你看，特征越多，类与类之间的差异性越能表现出来。