数据挖掘是从大量数据中挖掘有趣模式和知识的过程。数据源包括数据库、数据仓库、Web、其他信息存储库或动态地流入系统的数据。
数据仓库是一个从多个数据源收集的信息存储库，存放在一致的模式下，并且通常驻留在单个站点上。通常，数据仓库用称做数据立方体（data cube）的多维数据结构建模。
数据特征化（data characterization）是目标类数据的一般特性或特征的汇总。
数据区分（data discrimination）是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。
频繁模式（frequent pattern）是在数据中频繁出现的模式。存在多种类型的频繁模式，包括频繁项集、频繁子序列（又称序列模式）和频繁子结构。
频繁项集一般是指频繁地在事务数据集中一起出现的商品的集合。如小卖部中被许多顾客频繁地一起购买的牛奶和面包。频繁出现的子序列，如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式就是一个（频繁）序列模式。子结构可能涉及不同的结构形式（例如，图、树或格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁）结构模式。
分类（classification）是这样的过程，它找出描述和区分数据类或概念的模型（或函数），以便能够使用模型预测类标号未知的对象的类标号。
导出模型是基于对训练数据集（即，类标号已知的数据对象）的分析。该模型用来预测类标号未知的对象的类标号。导出的模型可以用多种形式表示，如分类规则（即IF-THEN规则）、决策树、数学公式或神经网络。
决策树是一种类似于流程图的树结构，其中每个结点代表在一个属性值上的测试，每个分支代表测试的一个结果，而树叶代表类或类分布。容易把决策树转换成分类规则。
神经网络是一组类似于神经元的处理单元，单元之间加权连接。
分类预测类别（离散的、无序的）标号，而回归建立连续值函数模型。也就是说，回归用来预测缺失的或难以获得的数值数据值。
相关分析（relevance analysis）可能需要在分类和回归之前进行，它试图识别与分类和回归过程显著相关的属性。
数据集中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些数据对象是离群点(outlier)。
数据挖掘吸纳了诸如统计学、机器学习、模式识别、数据库和数据仓库、信息检索、可视化、算法、高性能计算和许多应用领域的大量技术。
和数据有关的一些笔记
属性（attribute）是一个数据字段，表示数据对象的一个特征。
用来描述一个给定对象的一组属性称做属性向量（或特征向量）。涉及一(两)个属性（或变量）的数据分布称做单(双)变量分布。
①标称属性（nominal attribute）的值是一些符号或事物的名称。每个值代表某种类别、编码或状态，因此标称属性又被看做是分类的（categorical）。在计算机科学中，这些值也被看做是枚举的（enumeration）。
②二元属性（binary attribute）是一种标称属性，只有两个类别或状态：0或1，其中0通常表示该属性不出现，而1表示出现。二元属性又称布尔属性，如果两种状态对应于true和false的话。
一个二元属性是对称的，如果它的两种状态具有同等价值并且携带相同的权重；即关于哪个结果应该用0或1编码并无偏好。
一个二元属性是非对称的，如果其状态的结果不是同样重要的。
③序数属性（ordinal attribute）是一种属性，其可能的值之间具有有意义的序或秩评定（ranking），但是相继值之间的差是未知的。如成绩A+、A、A一、B+等。
④数值属性（numeric attribute）是定量的，即它是可度量的量，用整数或实数值表示。数值属性可以是区间标度的或比率标度的。
区间标度（interval-scaled）属性用相等的单位尺度度量。区间属性的值有序，可以为正、0或负。因此，除了值的秩评定之外，这种属性允许我们比较和定量评估值之间的差。例如，temperature就是区间标度的。
比率标度（ratio-scaled）属性是具有固有零点的数值属性。也就是说，如果度量是比率标度的，则我们可以说一个值是另一个的倍数（或比率）。此外，这些值是有序的，因此我们可以计算值之间的差，也能计算均值、中位数和众数。
⑤离散属性与连续属性。机器学习领域开发的分类算法通常把属性分成离散的或连续的。每种类型都可以用不同的方法处理。离散属性具有有限或无限可数个值，可以用或不用整数表示。如果属性不是离散的，则它是连续的。
数据的一些统计描述：
①中心趋势度量：均值、中位数和众数。
它度量数据分布的中部或中心位置。直观地说，给定一个属性，它的值大部分落在何处。
尽管均值是描述数据集的最有用的单个量，但是它并非总是度量数据中心的最佳方法。主要问题是，均值对极端值（例如，离群点）很敏感。为了抵消少数极端值的影响，我们可以使用截尾均值（trimmed mean），即丢弃高低极端值后的均值。
对于倾斜（非对称）数据，数据中心的更好度量是中位数（median）。中位数是有序数据值的中间值。它是把数据较高的一半与较低的一半分开的值。
当观测的数量很大时，中位数的计算开销很大。我们可以用插值计算整个数据集的中位数的近似值。
众数是另一种中心趋势度量。数据集的众数（mode）是集合中出现最频繁的值。因此，可以对定性和定量属性确定众数。可能最高频率对应多个不同值，导致多个众数。具有一个、两个、三个众数的数据集合分别称为单峰的（unimodal）、双峰的（bimodal）和三峰的（trimodal）。如果每个数据值仅出现一次，则它没有众数。
在大部分实际应用中，数据都是不对称的。它们可能是正倾斜的，其中众数出现在小于中位数的值上；或者是负倾斜的，其中众数出现在大于中位数的值上。
②度量数据散布：极差、四分位数、方差、标准差和四分位数极差、五数概括、盒图与离群点
分位数（quantile）是取自数据分布的每隔一定间隔上的点，把数据划分成基本上大小相等的连贯集合。
第1个和第3个四分位数之间的距离是散布的一种简单度量，它给出被数据的中间一半所覆盖的范围。该距离称为
因为Q1、中位数和Q3不包含数据的端点（例如尾）信息，分布形状的更完整的概括可以通过同时也提供最高和最低数据值得到。这称做五数概括。分布的五数概括（five-number summary）由中位数（Q2）、四分位数Q1和Q3、最小和最大观测值组成，按次序Minimum，Q1，Median，Q3，Maximum写出。
盒图（boxplot）是一种流行的分布的直观表示。盒图体现了五数概括：
盒的端点一般在四分位数上，使得盒的长度是四分位数极差IQR。
中位数用盒内的线标记。
盒外的两条线（称做胡须）延伸到最小（Minimum）和最大（Maximum）观测值。
当处理数量适中的观测值时，值得个别地绘出可能的离群点。在盒图中这样做：仅当最高和最低观测值超过四分位数不到1.5×lQR时，胡须扩展到它们。否则，胡须在出现在四分位数的1.5×IQR之内的最极端的观测值处终止，剩下的情况个别地绘出。盒图可以用来比较若干个可比较的数据集。
对于部门1，我们看到销售商品单价的中位数是80美元，Q1是60美元，Q3是100美元。注意，该部门的两个边远的观测值被个别地绘出，因为它们的值175和202都超过IQR的1.5倍，这里IQR=40。
盒图可以在$O(n log n)$
度量数据的相似性与相异性
①数据矩阵与相异性矩阵
数据矩阵：存放n个对象的p个属性。$$left[egin{array}{ccccc}{x_{11}} & {cdots} & {x_{1 f}} & {cdots} & {x_{1 p}} \ {cdots} & {cdots} & {cdots} & {cdots} & {cdots} \ {x_{i 1}} & {cdots} & {x_{i f}} & {cdots} & {x_{i p}} \ {cdots} & {cdots} & {cdots} & {cdots} & {cdots} \ {x_{n 1}} & {cdots} & {x_{n f}} & {cdots} & {x_{n p}}end{array} ight]$$
相异性矩阵：存放n个对象两两之间的邻近度。$$left[egin{array}{ccccc}{0} \ {d(2,1)} & {0} \ {d(3,1)} & {d(3,2)} & {0} \ {vdots} & {vdots} & {vdots} \ {d(n, 1)} & {d(n, 2)} & {cdots} & {cdots} & {0}end{array} ight]$$
$d(i,j)$是对象i和对象j之间的相异性或“差别”的度量。对象$i$和$j$彼此高度相似或“接近”时，其值接近于0；而越不同，该值越大。
数据矩阵经常被称为二模（two-mode）矩阵。相异性矩阵只包含一类实体，因此被称为单模（one-mode）矩阵。许多聚类和最近邻算法都在相异性矩阵上运行。
相似性度量可以表示成相异性度量的函数。$operatorname{sim}(i, j)=1-d(i, j)$
②标称属性的邻近性度量
标称属性可以取两个或多个状态，如颜色可以有5种状态：红、黄、绿、粉红和蓝。
设一个标称属性的状态数目是M。这些状态可以用字母、符号或者一组整数（如1，2，…，M）表示。
两个对象i和i之间的相异性可以根据不匹配率来计算：$$d(i, j)=frac{p-m}{p}$$
或者相似性为：$$operatorname{sim}(i, j)=1-d(i, j)=frac{m}{p}$$
其中，m是匹配的数目（即i和i取值相同状态的属性数），而p是刻画对象的属性总数。
例子：
假设只有对象标识符和属性$test-1$是可用的，其中$test-1$是标称的，计算相异性矩阵：我们令p=1，使得当对象$i$和$j$匹配时，$d(i,j)$=0；当对象不同时，$d(i,j)$=1。于是，我们得到相异性矩阵$$left[egin{array}{llll}{0} & {} & {} \ {1} & {0} & {} \ {1} & {1} & {0} \ {0} & {1} & {1} & {0}end{array} ight]$$
可以看出除了对象1和4之外，所有对象都互不相似。
③二元属性的邻近性度量
通过列联表来计算两个二元属性之间的相异性：
由给定的二元数据计算相异性矩阵。如果所有的二元都被看做具有相同的权重，则我们得到一个两行两列的列联表：
其中，$q$是对象$i$和$i$都取1的属性数；
$r$是在对象$i$中取1、在对象$j$中取0的属性数；
$s$是在对象$i$中取0、在对象$j$中取1的属性数；
$t$是对象$i$和$j$都取0的属性数。
属性的总数是$p$，其中$p=g+r+s+t$。
基于对称二元属性的相异性称做对称的二元相异性。如果对象$i$和$j$都用对称的二元属性刻画，则$i$和$j$的相异性为$$d(i, j)=frac{r+s}{q+r+s+t}$$
对于非对称的二元属性，两个状态不是同等重要的。给定两个非对称的二元属性，两个都取值1的情况（正匹配）被认为比两个都取值0的情况（负匹配）更有意义。因此，这样的二元属性经常被认为是“一元的”（只有一种状态）。基于这种属性的相异性被称为非对称的二元相异性，其中负匹配数t被认为是不重要的，因此在计算时被忽略$$d(i, j)=frac{r+s}{q+r+s}$$
而对应的非对称的二元相似性可以表示为$operatorname{sim}(i, j)=frac{q}{q+r+s}=1-d(i, j)$，$operatorname{sim}(i, j)$被称做$Jaccard$系数，
例子：
name是对象标识符，gender是对称属性，其余的属性都是非对称二元的。
对于非对称属性，值Y（yes）和P（positive）被设置为1，值N（no或negative）被设置为0。
$Jack$、$Mary$和$Jim$两两之间的距离如下：$$egin{aligned} d( ext { Jack, }, ext { Jim }) &=frac{1+1}{1+1+1}=0.67 \ d( ext { Jack, Mary }) &=frac{0+1}{2+0+1}=0.33 \ d( ext { Jim }, ext { Mary }) &=frac{1+2}{1+1+2}=0.75 end{aligned}$$
因为具有最高的相异性，所以$Jim$和$Mary$不大可能患类似的疾病。而$Jack$和$Mary$最可能患类似的疾病。
④数值属性的相异性：闵可夫斯基距离
计算数值属性刻画的对象的相异性的距离度量如下：
用p个属性来表示n个样本的数据矩阵：$$left[egin{array}{ccc}{x_{11}} & {cdots} & {x_{1 p}} \ {vdots} & {} & {vdots} \ {x_{n 1}} & {cdots} & {x_{n p}}end{array} ight]$$
欧几里得距离的计算公式为：$$d(i, j)=sqrt{left(x_{i 1}-x_{j 1} ight)^{2}+left(x_{i 2}-x_{j 2} ight)^{2}+cdots+left(x_{i p}-x_{j p} ight)^{2}}$$
$i=left(x_{i 1}, x_{i 2}, cdots, x_{i p} ight)$和$j=left(x_{j 1}, x_{j 2}, cdots, x_{j p} ight)$是两个被p个数值属性描述的对象，欧几里得距离即这两个对象的直线距离。
曼哈顿距离的计算公式为：$$d(i, j)=left|x_{i+}-x_{j 1} ight|+left|x_{2}-x_{j 2} ight|+cdots+left|x_{i p}-x_{i p} ight|$$
曼哈顿距离又称城市块距离，表示城市两点之间的街区距离。如图：
图中红线代表曼哈顿距离，绿线代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。
闵可夫斯基距离是以上两个距离的推广的计算公式为：$$d(i, j)=sqrt[q]{left|left(x_{i 1}-x_{j 1} | ight)^{q}+left(left|x_{i 2}-x_{j 2} ight| ight)^{q}+cdots+left(left|x_{i p}-x_{j p} ight| ight)^{q} ight.}$$
q为正整数，q=1时为曼哈顿距离；q=2时为欧几里得距离。
上确界距离（又称切比雪夫(Chebyshev)距离）是h→oo时闵可夫斯基距离的推广。$$d(i, j)=lim _{h ightarrow infty}left(sum_{f=1}^{p}left|x_{i f}-x_{i f} ight|^{h} ight)^{frac{1}{h}}=max _{f}left|x_{i f}-x_{i f} ight|$$
⑤混合类型属性的相异性
如何计算混合属性类型的对象之间的相异性？将不同的属性组合在单个相异性矩阵中，把所有有意义的属性转换到共同的区间[0.0，1.0]上
假设数据集包含$p$个混合类型的属性，对象$i$和$j$之间的相异性$d(i,j)$定义为：$$d(i, j)=frac{sum_{f=1}^{p} delta_{i j}^{(f)} d_{i j}^{(f)}}{sum_{f=1}^{p} delta_{i j}^{(f)}}$$
例子：
根据数值属性的规则，我们令${max _h}{x_h} = 64,{min _h}{x_h} = 22$。二者之差用来规格化相异性矩阵的值。结果，$test-3$的相异性矩阵为：$$left[egin{array}{llll}{0} & {} & {} & {} \ {0.55} & {0} & {} & {} \ {0.45} & {1.00} & {0} & {} \ {0.40} & {0.14} & {0.86} & {0}end{array}
ight]$$
可以得到：$d(3,1)=frac{1(1)+1(0.5)+1(0.45)}{3}=0.65$。由三个混合类型的属性所描述的数据得到的结果相异性矩阵如下：$$left[egin{array}{llll}{0} & {} & {} & {} \ {0.85} & {0} & {} & {} \ {0.65} & {0.83} & {0} & {} \ {0.13} & {0.71} & {0.79} & {0}end{array}
ight]$$
基于对象1和对象4在属性test-1和test-2上的值，我们可以直观地猜测出它们两个最相似。这一猜测通过相异性矩阵得到了印证，因为$d(4,1)$是任何两个不同对象的最小值。类似地，相异性矩阵表明对象2和对象4最不相似。
⑥余弦相似性
词频向量的引入：文档用数以千计的属性表示，每个记录文档中一个特定词（如关键词）或短语的频度。这样，每个文档都被一个所谓的词频向量（term-frequency vector）表示。而且，词频向量通常很长，并且是稀疏的（即，它们有许多0值）。我们想要探索两个文档共有的词和词频，就需要忽略0匹配的数据。但是因为数据的稀疏性，传统的距离度量效果不好，便引入了余弦相似性。
余弦相似性：余弦相似性是一种度量，它可以用来比较文档，或针对给定的查询词向量对文档排序。令$x$和$y$是两个待比较的向量，使用余弦度量作为相似性函数。$$operatorname{sim}(x, y)=frac{x cdot y}{|x||y|}$$
余弦值0意味两个向量呈90°夹角（正交），没有匹配。余弦值越接近于1，夹角越小，向量之间的匹配越大。
当属性是二值属性时，余弦相似性函数可以用共享特征或属性解释。$$operatorname{sim}(x, y)=frac{x cdot y}{x cdot x+y cdot y-x cdot y}$$
这是$x$和$y$所共有的属性个数与x或y所具有的属性个数之间的比率。这个函数被称为$Tanimoto$系数或$Tanimoto$距离，它经常用在信息检索和生物学分类中。
例子：
$x=(5,0,3,0,2,0,0,2,0,0)$和$y=(3,0,2,0,1,1,0,1,0,1)$，计算这两个向量之间的余弦相似性。$$egin{array}{l}{x cdot y=5 imes 3+0 imes 0+3 imes 2+0 imes 0+2 imes 1+0 imes 1+0 imes 0+2 imes 1+0 imes 0+0 imes 1=25} \ {|x|=sqrt{5^{2}+0^{2}+3^{2}+0^{2}+2^{2}+0^{2}+0^{2}+2^{2}+0^{2}+0^{2}}=6.48} \ {|y|=sqrt{3^{2}+0^{2}+2^{2}+0^{2}+1^{2}+1^{2}+0^{2}+1^{2}+0^{2}+1^{2}}=4.12} \ {operatorname{sim}(x, y)=0.94}end{array}$$
所以，这两个文档被认为是高度相似的。