周末和何女神一起读书，她最近学数据挖掘，所以我就陪读，这里记录一下读书心得。
首先，这本书应该是数据挖掘领域的经典，可以找到网上的数据挖掘导论PDF
作者是Michingan State U的Associate Professor Pang-Ning Tan、University of Minnesota的Vipin Kumar
好，马上开始正题：
书本内容与组织
第一章，绪论
第二章，讨论数据基本类型、质量、预处理及相似性和相异性度量
第三章，关于数据数据探查
第四、五章，关于分类
第六、七章，讨论关联分析
第八、九章，讨论聚类分析
第十章，讨论数据挖掘的异常检测
第二章 数据
1.1 属性Attri,对象的性质和特征。测量标度是属性的数值、符号甚至关联规则（函数）。主要是将物理世界的连续量，量化离散成适当的、计算机可以处理的数据。
1.2 数据集的特性：维度高、稀疏性、适当分辨率
2.1 数据记录的方式：矩阵、稀疏矩阵、基于图形的数据、有序数据、时序数据、空间数据
2.2 数据质量，受到测量误差和收集错误影响，包括噪声、精度、离群点、遗漏值、重复值以及不一致值。数据集之于应用也会受到时效性、相关性的。
2.3 数据预处理：聚集、抽样、维归约、特征子集选择、特征创建、离散化和二元化、变量变换
聚集动机：减少内存和处理时间、使用高层的数据视图起到了范围和标度转换的作用
抽样：抽取有代表性有效的数据样本，方法有单随机（无放回和有放回）抽样和分层抽样，为了确定适合大小的样本容量，还可以进行自适应或者渐进的抽样。
维归约：就是降维，将旧属性合并成新属性，避免维度灾难。可以用线性代数方法，将高维空间投影到低维空间，比如PCA找出主成分并利用正交特性捕捉数据最大变差，SVD也相似。
特征子集选择：嵌入方法，嵌入到算法模型，算法来决定特征属性。与嵌入相反的过滤方法，使算法与特征选择相关度小。包装方法来找到最佳属性子集。或者直接使用特征加权。
特征创建：1.特征提取 2.映射到新空间（傅里叶变换） 3.构造特征
二元化：将属性转换成二元属性
离散化：非监督离散化和监督离散化，基于信息熵的方法较佳
$$ e_i =- \sum_{j=1}^k p_{ij}log_2p_{ij} $$
定义$m_{ij}$是区间i中类j的值的个数，则$p_{ij}=m_{ij}/m_i$是第i个区间种类j的概率
区间的熵是区间纯度的度量，如果区间只有1个值，则熵为0，不影响总熵。如果一个区间中值类出现频率相等（区间不纯，含信息多），则熵最大。决策树的属性选取与此有相似的思想。
变量变换：1.简单函数：将不具有高斯分布的数据变换成高斯分布或者压缩大的数值（注意是否变换导致数据集特性的丢失，思考以下问题：如需要保序么？作用到全部值？变换对0~1之间的值有如何影响？）2.规范化：例如以0为均值，1为标准差。通常用于方便计算，并使数据集具有特定的特质
相似性和相异性：用邻近度表示相似或相异，包括相关和欧几距离，Jaccard和余弦相似度量，前两者使用时间序列稠密数据或二维点，后两者适用文档、图像等稀疏数据。一般得到邻近度后，原始数据便不再需要。
通常我们会定义一些距离，如L0、L1、$L_\infty$,它们满足非负性、对称性和三角不等式,满足此条件称为度量（metric）,由此可延伸出测度学习（Metric Learning)。其中还可以用集合差，时间之间的距离
余弦 $cos(x,y)=\frac{x}{||x||}.\frac{y}{||y||}$
相关性 $corr(x,y)=\frac{covariance(x,y)}{standard\_deviation(x)*standard\_deviation(y)} =\frac{s_xy}{s_xs_y}$
Bregman散度：给定严格凸函数$\phi$,则该函数生成的Bregman散度D(x,y)通过下面公式给出：
$$D(x,y)=\phi(x)-\phi(y)-<\Delta\phi(y),(x-y)>$$
其中$\Delta\phi(y)$计算$\phi$的梯度，$<\Delta\phi(y),(x-y)>$是$\Delta\phi(y)$和(x-y)的内积。
2.4 邻近度计算问题
1.距离度量的标准化和相关性（假定属性相同类型）
$$mahalanobis(x,y)=(x-y)\sum^{-1}(x-y)^T$$
其中$\sum^{-1}$是数据协方差矩阵的逆，第ij个元素是第i个和第j个属性的协方差。这个是为了减少不同尺度变量的影响，虽然计算量大，但对于属性相关的对象是值得的。
2.组合异种属性的相似度
3.使用权值
$$similarity(x,y)=\frac{\sum_{k=1}^nw_k\delta_ks_k(x,y)}{\sum_{k=1}^n}\delta_k$$
其中$\delta=0$，如果第k个属性是非对成熟性，并且两个对象在该属性上的值都是0，或者其中一个对象的第k个属性具有遗漏值。$\delta=1$，则两个对象之间的相似度有以上定义，以上的公式包含了组合异种属性和使用权值的效果。
2.5 关于如何选取正确的邻近性度量
选取与数据类型相适应的：稠密和连续的数据，通常使用距离度量。稀疏数据常常包含非对称数据，通常使用忽略0-0匹配的相似性度量。因为对象相似依赖于共同具有的性质，而不是缺失的性质，若考虑稀疏数据缺失的性质，则它们都高度相似。所以余弦、Jaccard和广义Jaccard度量更适合。
对于比较时间序列，如果量值重要，则用欧几距离。假若序列形状重要，则考虑相关度（使用考虑量和级的差异的内置规范化）。
