下载掌阅APP，畅读海量书库
立即打开
数据挖掘中的数据集是由数据对象构成的集合。数据对象有多种称谓，比如记录、模式、样本、案例等。数据对象有多个属性描述其基本特征。了解常见数据类型有助于描述数据内部特征、规律和趋势等信息，满足模型构建的要求。
属性是数据对象的性质或特性，属性又可称为特征。每一个数据对象用一组属性描述，数据集用结构化数据表表示，其中列是存放在表中的对象的属性，行代表一个对象实例，表中单元格是实例对应属性的属性值。图2-1使用鸢尾花数据集（http://archive.ics.uci.edu/ml/datasets/Iris）来解释对象与属性的基本概念。
图2-1 鸢尾花数据集
属性的度量是样本数据采集中，对样本具体属性记录其测量标度值。例如，天气状况｛晴天，多云，阵雨，阴天，小雪｝；温度（摄氏）｛24.4,12.2,70.8,69.3｝；商品的销售数量｛300,223,126,408,625｝等。
需要注意的是，属性的测量值与属性的值的意义并不是完全对等的，比如数学上24.4是12.2的两倍，但作为摄氏温度值24.4并不代表比12.2温暖两倍。天气属性值中“晴天”和“多云”也可以用不同的数字来表示，它们没有前后次序关系，也不能进行加减运算，只能测试相等或不等才有意义。在数据挖掘中知道属性的类型可以避免使用错误的统计操作。
可以通过以下4种基本操作来确定属性的类型。
（1）相异性：=和≠。
（2）序：≤、≥、＜和＞。
（3）加减法：+和-。
（4）乘除法：*和/。
按照上面属性测量值可使用的基本操作，可将属性大致分为标称、序数、二元、区间、比率5种类型，如表2-1所示。
表2-1 属性的基本类型
二元属性根据两种状态是否具有同等价值并且携带相同的权重可以分为对称的和非对称的两类。如果两种状态哪一个用0或1编码并无偏好，属于对称的二元属性。如果一个状态出现的概率要远低于另一个状态出现的概率，代表重要的事件发生，那么属于非对称二元属性，如病理化验的阳性和阴性。
数据集的类型是从集合整体上分析数据的类型。本书从数据对象之间的结构关系角度进行划分，比较常见的有记录数据、有序数据、图形数据。
记录数据是最常见的数据集类型，例如一张普通的 Excel 表格文件或一张关系数据库中的表。数据集是一个二维表格，其中表中行代表记录，列代表属性。记录之间没有明显的联系，包括位置关系和相互依赖关系等。数据集中的数据对象可以完全相互独立地使用，可以从数据集里随机抽取一部分数据对象进行挖掘建模，另一部分数据对象用于测试评估。
数据对象之间存在时间或空间上的顺序关系称为有序数据。有序数据有两种类型：时序数据和序列数据。
（1）时序数据一般是由硬件设备或系统监控软件连续采集形成的数据。如股票价格波动信息，医疗仪器监视病人的心跳、血压、呼吸数值，环境传感器连续记录的温度、湿度数值等，在数据挖掘任务中需要考虑这些数值在时间上的前后关系。
时序数据包含了两类属性：一类是表示时间或地理空间的上下文属性，如时间戳或地理坐标；另一类是在上下文属性每个参照点上对应的行为属性，如采集到的温度、湿度等。需要说明的是，两类属性数据需要相互关联起来使用才有意义。
（2）序列数据与时序数据类似，但不包含时间信息。例如，自动化诊断系统会产生包含可用来描述故障信息的离散数据序列；用户上网购物会产生鼠标点击网页的超链接、登录系统、付款结账等操作指令序列，这些信息可以用来挖掘用户的上网习惯。
如果数据对象之间存在显式或隐式的联系，相互之间有一定的复杂依赖关系，构成图形或网状结构，我们把这种数据集称为图形数据。
考虑互联网中网页与网页之间存在超链接，可以把网页看作图中的节点，把它们之间的连接看作图中的边，搜索引擎就是利用网络爬虫不断沿着网页中的超链接进行搜索。类似的还有社交信息，社交软件用户可以看作节点，用户之间的联系看作边。
数据挖掘工作始终是以数据为中心开展的，分类、聚类、回归、关联分析以及可视化等工作的顺利进行完全是建立在良好的输入数据基础之上的。软件开发行业有句格言：“Garbage-In-Garbage-Out”，这句话同样适用于数据科学。事实上，我们采集到的原始数据通常来自多个异种数据源，数据在准确性、完整性和一致性等方面存在多种多样的问题，这些数据并不适合直接进行挖掘。在进行挖掘算法执行之前，它们需要进行一些诸如移植、清洗、切片、转换等预处理工作。
人工输入错误或仪器设备测量精度及数据收集过程机制缺陷等方面原因都会造成采集的数据存在质量问题，主要包括测量误差、数据收集错误、噪声、离群点（outlier）、缺失值、不一致值、重复数据等问题。数据清理阶段的主要任务就是通过填写缺失值、光滑噪声数据、删除离群点和解决属性的不一致性等手段来清理数据。
数据的收集过程很难做到数据全部完整。例如：数据库中表格的列值不会全部强制性不为空类型；问卷调查对象不想回答某些选项或是不知道如何回答；设备异常；对数据改变没有日志记载。处理缺失值的方法有以下3种。
（1）忽略元组：也就是将含有缺失属性值的对象（元组，记录）直接删除，从而得到一个完备的信息表。在缺失属性对象相对于整个数据集所占比例较小时这种方法比较适用，特别是在分类任务中缺少类别标号属性时常采用。如果数据集中有较高比例的数据对象存在缺失值问题，这种方法失效。在样本资源比较少的挖掘任务中，删除宝贵的数据对象会严重影响挖掘结果的正确性。
（2）数据补齐：使用一定的值对缺失属性进行填充补齐，从而使信息表完备化。数据补齐的具体实行方法较多。
人工填写： 需要用户非常了解数据相关信息，并且数据量大时，这种方法效率太低。
特殊值填充： 将所有空值使用一个特殊值如“unknown”进行填充，这种方法有可能导致严重的数据偏离。
平均值填充： 如果属性是数值型的，使用所有对象属性的平均值来填充，对于倾斜分布情况也可以采用中位数来填充；如果属性是非数值型的，可以采用出现频率最高的值来填充。
使用最有可能的值填充： 采用基于推断的方法填充空缺值。例如，可以使用包含空值对象周围与其相似的对象值对其进行填充，可以建立回归模型，对缺失属性值进行估计，也可以使用贝叶斯模型推理或决策树归纳确定。
（3）不处理：有很多数据挖掘方法在属性值缺失方面具有良好的鲁棒性，可直接在包含空值的数据上进行数据挖掘。这类方法包括贝叶斯网络和人工神经网络等。
2．噪声数据
噪声（Noise）是一个测量变量中的随机错误或偏差。造成这种误差有多方面的原因，例如，数据收集工具的问题，数据输入、传输错误，技术限制等。噪声可以对数值进行平滑处理而消除。主要使用的技术有回归、分箱、孤立点分析。
分箱（Binning）：通过考察相邻数据来确定最终值，实际上就是按照属性值划分的子区间，如果一个属性值处于某个子区间范围内，就称为把该属性值放进这个子区间所代表的“箱子”内。用“箱的深度”表示不同的箱里有相同个数的数据。用“箱的宽度”来表示每个箱值的取值区间为常数。由于分箱方法考虑相邻的值，因此是一种局部平滑方法。
假设有3、22、8、22、9、11、32、93、12等9个数，分为3箱。
箱1:3、22、8
箱2:22、9、11
箱3:32、93、12
分别用三种不同的分箱法求出平滑存储数据的值：
按箱平均值求得平滑数据值——箱1:11,11,11
按箱中值求得平滑数据值——箱2:9,9,9
按箱边界值求得平滑数据值——箱3:32,32,32
孤立点分析： 孤立点是在某种意义上具有不同于数据集中其他大部分数据对象特征的数据对象，或是相对于该属性值不寻常的属性值。可以通过聚类来检测离群点，落在簇之外的数据对象被视为孤立点。
数据对于数据挖掘任务来说是非常重要的，用户永远希望尽最大可能获得更多的挖掘目标数据。例如，在一些监督学习任务中，分类器的准确性与训练数据的数量有非常大的关联。
数据集成就是将若干个分散的数据源中的数据，逻辑地或物理地集成到一个统一的数据集合中。这些数据源包括关系数据库、数据仓库和一般文件。数据集成的核心任务是要将互相关联的分布式异构数据源集成到一起，使用户能够以透明的方式访问这些数据源。集成是指维护数据源整体上的数据一致性、提高信息共享利用的效率；透明的方式是指用户无须关心如何实现对异构数据源数据的访问，只关心以何种方式访问何种数据。
数据集成涉及若干问题需要去解决。
来自不同数据源的相同实体但名称可能完全不同，如何才能正确识别它们？例如， cust_number 与 customer_id 分别来自不同的数据库，但是表示的意思完全一样。这里，我们可以使用属性的元数据来分析它们。属性的元数据一般包括属性名称、含义、数据类型、取值范围、数据值编码及缺失值表示符号等。使用属性元数据进行数据清理工作，可避免发生模式集成错误。
如果一个属性可以由其他属性或它们的组合导出，那么这个属性可能是冗余的。解决属性冗余问题，需要对属性间的相关性进行检测。对于数值属性，通过计算两个属性之间的相关系数来估计它们的相关度。假设两个属性分别为A和B，计算公式如下：
其中，N是元组的个数；a
i
和b
i
为第i个元组中A和B对应的值；
和
为它们的平均值；σ
A
,σ
B
为 A 和 B 的标准差。如果r
A,B
取值在-1与1之间，且如果r
A,B
＞0，表示它们正相关，值越大相关性越大；相反，如果r
A,B
＜0，表示负相关。
对于离散数据，我们可以使用卡方检验来做类似计算，根据计算置信水平来判断两个属性独立假设是否成立。
元组自身的冗余也会构成数据冗余。数据库设计者有时为了某些性能需求，使用较低级的范式要求，造成不同关系表中同一个元组不是使用外键关联，而是以副本形式重复存储。这样，还存在更新遗漏的风险，造成副本内容不一致。
属性值的表示、规格单位、编码不同，也会造成现实世界相同的实体，在不同的数据源中属性值不相同。例如，单位分别以千克和克表示的重量数值；性别中男性用 M和 male 表示。属性名称相同，但表示的意思不相同。例如，总费用属性可能有包含运费和不包含运费区分。
来自不同数据源的属性间的语义和数据结构等方面的差异，给数据集成带来了很大困难。需要小心应对，避免最终集成数据集中出现冗余和不一致问题。
在对数据分析前，通常需要先将数据规范化（Normalization），也称为标准化。不同性质属性数据直接相加不能正确反映出不同作用的正确结果。数据规范化主要包括数据同趋化处理和无量纲化处理两个方面，可以使属性值按比例落入到一个特定区间，如[-1,1]或[0,1]。
数据规范化一方面可以简化计算，提升模型的收敛速度；另一方面在涉及一些距离计算的算法时，防止较大初始值域的属性与具有较小初始值域的属性相比权重过大，可以有效提高结果精度。本节介绍三种规范化方法。
也称离差标准化，是对原始数据的线性变换，假定 min,max 分别为属性 A 的最小值和最大值。转换函数如下：
将 x 转换到区间[new_min,new_max]中，结果为x＇。这种方法有一个缺陷就是当有新的数据加入时，可能导致 max,min 值的变化，需要重新定义。另外，如果要做0-1规范化，上述式子可以简化为：
也叫标准差标准化，经过处理的数据符合标准正态分布，即均值为0，标准差为1。属性A的均值
和标准差σ
A
规范化，转化函数为：
当属性 A 的实际最大值和最小值未知，或有超出取值范围的孤立点时，该方法适用。
通过移动数据的小数点位置来进行标准化。小数点的移动位数取决于属性 A 的最大绝对值。x规范后的值x＇计算方法：
其中，j 是使
的最小整数。例如，-84＜x＜231，取 j=3,-84规范化后值为-0.084,231规范化后为0.231。
需要注意的是，z-score 规范化和按小数定标规范化在计算过程中有参数值，需要保存起来，为后续数据进行统一标准化时使用。
当我们在数据仓库上进行数据挖掘时，可能会面临着在海量高维数据上进行复杂的数据分析和挖掘，算法因运行时间超出我们的忍受范围而失效。在这种情况下，可以使用原数据集的一个特征、样本子集来完成挖掘。
数据约简（Data Reduction）技术是指在尽可能保持原始数据集完整性的前堤下，最大限度地精简数据量。数据约简技术可以用来得到数据集的约简表示，它虽然小，但仍大致保持原数据的完整性。这样，在约简后的数据集上挖掘将更有效，并产生相同（或几乎相同）的分析结果。下面介绍几种常用数据约简策略。
用于数据挖掘的原始数据集属性数目可能有几十个，甚至更多。这其中包含了一些冗余或对于挖掘任务并不相关的属性。例如，数据对象的 ID 号通常对于挖掘任务无法提供有用的信息；生日属性和年龄属性相互关联存在冗余，因为可以通过生日日期推算出年龄。冗余和与挖掘任务不相关的特征对挖掘任务本身是有害的，它们对挖掘算法起到干扰作用，会降低挖掘任务的准确率或导致发现很差的模式。此外不相关和冗余的属性增加了数据量，可能会减慢挖掘过程。
属性子集选择是指从已有的m个属性中选择其中n个属性，使得系统的特定指标最优化。它是从原始特征中选择出一些最有效特征以降低数据集维度的过程，是提高学习算法性能的一个重要手段。
尽管使用常识和领域知识可以快速消除一部分不相关和冗余属性，但是选择最佳特征子集需要一个系统的方法。假设数据对象有n个属性，那么会有2 n 个属性子集，求最优属性子集本质上是在2 n 个解构成的空间中搜索最优解。
（1）当 n 较小时，可以采用全局搜索策略，用给定的属性子集评价指标评价每个属性子集，从中选出最优特征子集。
（2）当 n 较大时，全局搜索行不通，可以采用启发式搜索策略、概率搜索策略等选择次优属性子集。
有三类属性子集选择方法：嵌入（embedded approach）、过滤（Filter Approach）和包装器（Wrapper Approach）。
（1）嵌入：将属性选择任务插入到数据挖掘过程当中，挖掘算法本身包含了属性选择任务，如决策树归纳方法。
（2）过滤：属性选择过程独立于挖掘算法。这种方法速度快，但是选出的属性子集的分类性能弱于包装器方法。
（3）包装器：属性选择与分类算法绑定，它在筛选属性的过程中直接用所选的特征子集来训练分类器，并根据在测试集上的性能表现来评价属性子集的优劣。算法计算效率较慢，属性子集分类性能好。
过滤方法与包装器方法的流程基本相同，如图2-2所示。其不同在于属性子集的评估方法，包装器使用目标数据挖掘算法作为子集评估方法。
图2-2 属性子集选择流程图
属性子集选择过程包括四个组成部分：子集评估、搜索策略、停止搜索标准和验证过程。属性子集评估有两种标准：一种是用于单独衡量每个属性分类能力的评价标准，另一种为对属性子集整体分类性能做评价的标准。停止搜索标准一般是设置算法执行时间、循环评价次数及性能指标阈值等作为算法停止条件。
主成分分析（Principal Component Analysis,PCA）是一种广泛用于不同领域的无监督线性数据转换技术。PCA 的目标是在高维数据中找到最大方差的方向，并将数据映射到一个维度小得多的新子空间上。借助于正交变换，将其分量相关的原随机向量转化成其分量不相关的新随机向量。在代数上表现为将原随机向量的协方差阵变换成对角形阵，在几何上表现为将原坐标系变换成新的正交坐标系，使之指向样本点散布最开的几个正交方向。
PCA 通过创建一个替换的、更小的变量集来组合属性的基本要素，去掉了一些不相关的信息和噪声，数据得到精简的同时又尽可能多地保存了原数据集的有用信息。PCA的应用条件是要求属性间存在较大的相关性，当相关性较小时，应用主成分分析没有意义。PCA的基本操作步骤如下。
（1）首先对所有属性数据规范化，每个属性都落入相同的区间，消去量纲对算法的影响。
（2）计算样本数据的协方差矩阵。
（3）求出协方差矩阵的特征值及相应正交化单位特征向量。前m个较大的特征值就是前m个主成分对应的方差。主成分的方差贡献优选法反映信息量的大小。
（4）通过计算累计贡献率来选择主成分。主成分向量构成了一组正交基，输入数据可以由它们的线性组成表示。
（5）对主成分按重要性排序。主成分是新空间下的坐标轴，提供了关于方差的重要信息。
（6）选择重要性最高的若干个主成分，同时将剩下的较弱主成分舍弃，这样就完成了约简数据的规模。
离散小波变换（DWT）是从离散傅里叶变换（DFT）发展而来的。傅里叶变换是信号由时域到频域的转化工具，将信号的波形分解成不同频率的正弦波或余弦波的叠加，信号分析工作转为傅里叶变换函数权系数的计算。离散小波变换是一种更好的有损压缩，相对于傅里叶变换提供了对原始数据更准确的近似。
将具有n个属性的数据对象，使用n维数据向量X=（x 1, x 2 ,…,x n ）表示。离散小波变换用于数据向量 X，可以将X转换成相同长度的小波系数向量X＇。通过设定适当阈值，过滤掉小于阈值的小波系数，向量X＇可以仅存放一部分最强的小波系数，向量中其余部分用0值替换，完成近似的数据压缩。在小波空间下对稀疏的向量X＇进行操作计算可以获得较快的速度，在过滤掉数据中噪声的同时，保留了数据的主要特征。最后对处理后的小波系数向量X＇进行离散小波变换逆运算，可以构造原数据的近似。
有些数据挖掘算法，要求数据属性是标称类别，当数据中包含数值属性时，为了使用这些算法，需要将数值属性转换成标称属性。通过采取各种方法将数值属性的值域划分成一些小的区间，并将这连续的小区间与离散的值关联起来，每个区间可看作一个类别。例如，对某个问题中的年龄属性，一种可能的划分类别的操作是：[0…11]→儿童， [12…17]→青少年，[18…44]→青年，[45…69]→中年，[69…∞]→老年。这种将连续变量划分成不同类别的过程通常称为离散化（Discretization）。
有效的离散化能够减少算法的时间和空间开销，提高系统对样本的聚类能力，增强系统抗数据噪声的能力及提高算法的学习精度。离散化后的数据更易于理解、使用和解释。很多不适用于连续型数据的算法得以适用。
连续属性离散化的问题本质是：决定选择多少个分割点和确定分割点位置。任务可分为两个步骤完成。首先将连续属性排序，并通过指定n-1个分割点把它们分成n个区间。然后，将一个区间中的所有值映射到相同的分类值。
数据离散化的方法有多种类型，通常可以分为无监督离散化和有监督离散化。在离散化过种中使用类信息的方法是有监督的，而不使用类信息的方法是无监督的。
无监督离散化方法中最简单的方法是等宽分箱法和等频分箱法。等宽分箱法将排好序的数据从最小值到最大值均匀划分成n等份，每份的间距是相等的。假设A和B分别是属性值的最小值和最大值，那么划分间距为 w=（B-A）/n，每个类别的划分边界为 A+w, A+2w, A+3w, …, A+（n-1）w。这种方法的缺点是对异常点比较敏感，倾向于不均匀地把实例分布到各个箱中。等频分箱法将数据总记录数均匀分为 n 等份，每份包含的数据个数相同。如果 n=10，那么每一份中将包含大约10%的数据对象。这两种方法都需要人工确定划分区间的个数。等频法可能将具有不相同类标号的相同属性值分入不同的箱中，以满足箱中数据固定个数的条件。
以上两种算法容易实现，适用较广，但是有些情况下存有弊端。比如，假设对某一工资属性进行划分，用等宽分箱法划分为5区间，最高工资为50000，则所有工资低于10000的人都被划分到同一区间。等频分箱法可能正好相反，所有工资高于50000的人都会被划分到50000这一区间中。这两种算法都忽略了样本数据所属的类别信息，划分区间的边界不太可能落在最合理的地方。
ChiMerge是一种监督的、基于X 2 检验的数据离散化方法。其基本思想：对于精确的离散化，相对类频率在一个区间内应当完全一致。因此，如果两个相邻的区间具有非常类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低X 2 值表明它们具有相似的类分布。
ChiMerge算法离散化数据操作流程包含三个基本步骤：
（1）将所有样本数据按给定数值属性A的值升序排序。
（2）把数值属性A的每个不同值看作一个区间。
（3）对每对相邻的区间进行X 2 检验。将最小X 2 值的相邻区间合并成一个区间。重复执行X 2 检验并且自底向上合并区间，直到X 2 检验达到设定的阈值。
许多数据挖掘任务需要计算数据对象之间的相似性或相异性，如聚类、最近邻分类、异常检测等。为了本节内容表述方便，假设两个数据对象
和
，我们用
表示它们的相似度，用
表示它们间的相异度或距离。
相似度指两个对象相似程度的数据度量，对象越相似数值越大，有Sim（X,Y）=Sim（Y,X），且
。相异度指两个对象差异程度的数值度量，距离可以作为相异度的同义词，两个数据所在的空间距离越大，表示数据越相异，有
，且
。相似性和相异性计算方法是一致的，通常是用两个对象之间的一个或多个属性距离来表示，它们可以相互转换。除了取值范围外，它们之间名称上的区分更多是源自习惯上的称谓。如两篇文章我们常称它们相似度是多少，而空间数据对象则称它们之间的距离是多少。我们使用术语邻近度来表示对象间的相似性或相异性。
数据对象之间的邻近度计算与数据对象属性类型密切相关。掌握简单属性之间的邻近度是计算复杂对象之间邻近度的基础。本节分别以标称和数值类型属性介绍邻近性度量方法。
记录数据具有最简单的结构，是数据挖掘中最常见的数据对象。数值属性与标称属性相似度的计算方式明显不同，我们先介绍具有多维数值属性对象的邻近性度量方法。
序数属性值是有序序列，如 size 属性值｛mini,small,medium,large｝。邻近度的计算可以将这些属性值用数值代替，如｛mini=0,small=1,medium=2,large=3｝，那么计算两个对象的相异度，可以用对应属性值差值的绝对值表示。
数据集中的数据对象可以看作某空间下的点。在一般意义下，空间可看作是点的全集，即数据集中的点看作是从空间中抽样而成的。在欧式空间下，这样定义点有益于聚类。特别地，在欧式空间下的点就是实数向量，向量的长度就是空间的维度数，而向量的分量通常称为点的坐标（coordinate）。
在一个空间下进行聚类或某些分类任务时，需要在该空间中找到一个距离测度，即给出该空间下任意两点之间的距离。距离测度是一个函数 d（x,y），以空间中的两个点作为参数，函数值是一个实数值，该函数必须满足下列准则：
（1）Dist（x,y）≥0（距离非负）；
（2）当且仅当x=y时，Dist（x,y）=0（只要点到自身的距离为0，其他的距离都大于0）；
（3）Dist（x,y）= Dist（y, x）（距离具有对称性）；
（4）Dist（x,y）≤Dist（x,z） + Dist（z,y）（三角不等式）。
只有满足上述性质的距离测度才可以称为度量。在度量方法中，数据对象的属性以连续或离散数值的方式描述，数据对象可以看作是度量空间（距离空间）中的点，数据对象之间的距离可以看作相似性的度量。
假设每个对象有m个属性，可以把一个对象视为m维空间的一个点，n个对象就是m 维空间中的 n 个点。从直观上看，属于同一类的对象在空间中应该互相靠近，而不同类的对象之间的距离要大得多，因此可用距离来衡量对象之间的相似程度。距离越小，对象间的相似性就越大。常用的距离形式有：曼哈顿距离、欧几里德距离、切比雪夫距离、闵可夫斯基距离、杰卡德距离等。
曼哈顿距离之所以称为“曼哈顿距离”，是因为在两个点之间行进时必须要沿着网格线前进，就如同沿着城市（如曼哈顿）的街道行进一样。对于一个具有正南正北、正东正西方向规则布局的城市街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，是将多个维度上的距离进行求和的结果。其距离公式：
欧几里德距离也称为欧氏距离，是最为熟知的距离测度，也就是我们常说的“距离”。在m维欧氏空间中，每个点是一个m维实数向量，该空间中的传统距离测度为L 2 范式，定义如下：
也就是说，首先计算每一维上的距离，然后求它们的平方和，最后求算术平方根。
另一个有趣的距离测度是L
∞
范式，也就是当r趋向无穷大时L
r
范式的极限值。当r增大时，只有那个具有最大距离的维度才真正起作用，因此，通常L
∞
范式定义为在所有维度下
中的最大值。
以数学的观点来看，切比雪夫距离是由一致范数（Uniform Norm）（或称为上确界范数）所衍生的度量，也是超凸度量（Injective Metric Space）的一种。它产生两个数据对象的最大属性值差。
闵可夫斯基距离又称为闵氏距离，是欧几里德距离、曼哈顿距离和切比雪夫距离的推广。闵氏距离对应L p 范数，其中p是一个变参数，根据参数的不同，闵氏距离可以表示不同类型的距离。当p=1时，就是曼哈顿距离；当p=2时，就是欧氏距离；当p→∞时，就是切比雪夫距离。
例2.1
考虑二维欧氏空间（通常所说的平面）上的两个点（2,5）和（5,9）。它们的 L
2
范式距离为
,L
1
范式距离为
，而L
∞
范式距离为
。
附注1：当L 2 范式距离较小时，表示x与y在一个类型区域，反之，则不在一个类型区域。这里有一个门限的选择问题，若选择过大，则全部样本被视作一个唯一类型；若选取过小，则可能造成每个样本都单独构成一个类型。必须正确选择门限值以保证正确分类。
附注2：模式特征坐标单位的选取也会强烈地影响聚类结果。例如，在二维欧氏空间中，一维是长度，另一维是压力。当长度由厘米变为米，在L 2 中长度特征的比重会下降，同样，若把比重单位由毫米汞柱高度变成厘米汞柱高度，L 2 中压力特征的影响也会下降。
附注3：使用欧氏距离度量时，还要注意样本测量值的选取，应该能有效反映类别属性特征（各类属性的代表应均衡）。例如，取5个样本，其中有4个反映对分类有意义的特征A，只有1个对分类有意义的特征B，欧氏距离的计算结果，则主要体现特征A。
杰卡德距离（Jaccard Distance）用于衡量两个集合的差异性，它是杰卡德相似度的补集，被定义为1减去杰卡德相似度。杰卡德相似度用来度量两个集合之间的相似性，它被定义为两个集合交集的元素个数除以并集的元素个数，即集合 A 和 B 的相似度sim（A, B）为：
多维二元数据，其某位数据为1表示元素集合中的某个元素出现，为0表示不出现。例如，超市的一张交易清单中用1或0来表示是否包含某件商品，一篇文章中用0或1来表示词语是否出现。多维二元数据情况下，集合 A、B 的相似度可以进一步写成：
集合A、B的杰卡德距离d J （A, B）为：
数值数据是有大小顺序的，距离公式非常适合计算不同维度数值数据的邻近度。但是，离散的标称属性数据间并不存在大小顺序关系，不能直接用距离来计算相似度或相异度。
标称属性取值是代表事物状态的若干值，只包含了相异性信息。标称类型可以通过编码方案转换成二元数据类型，然后使用数值计算方法来计算邻近度。如果一个标称类型数据有 M 个不同的状态值，那么将该标称数据转换成 M 个二元属性值，每一个标称状态值对应一个二元属性，这些二元属性中有一个值为1，剩余的全为0。这样，标称属性相似度计算就可通过编码方式转化为多个二元属性的相似度计算。
简单二元属性的状态值为布尔值，可以用数字0和1分别来表示。比如在某图书管理系统中描述图书对象的借出情况，可以用0表示在馆，用1表示借出。
考虑数据对象只有一个属性的情况下：如果两个标称属性值匹配，则相似度为1，否则为0；相异度的值刚好相反，如果标称属性匹配，则相异度为0，否则为1。
一般地，二元属性相似度可以通过对属性匹配值求和来计算。即首先分别求解对应单个属性间的相似度，然后对所有相似度数值进行直接累加：
其中，d 代表对象的属性总数。更为直接地理解，相似度可用“取值相同的同位属性数/属性总位数”标识对于包含多个二元属性的数据对象相似度计算。
设
，
，两个对象共有7个属性取值相同，3个取值不同，那么相似度可以标识为3/10=0.3。
这种方法非常简单，缺点是没有考虑不同属性的概率差异。上面所说的二元属性的两个状态具有同等价值和相同的权重，称为对称二元属性。对于非对称二元属性，我们只关心两者都取1的情况，而认为两者都取0的属性并不意味着两者更相似。
例如，在根据病情对病人聚类时，如果两个人都患有肺癌，我们认为两个人增强了相似度，但如果两个人都没患肺癌，并不觉得这加强了两人的相似性。即同为0值的负匹配对相似度计算不起作用，而同为患肺癌结果包含了明显的统计信息。
这种情况下，即非对称二元相似度计算，可以改用“取值同为1的属性数/（单个元素的属性位数－同取0的位数）”来标识相似度。
前面所述的计算方法均为有关相同数据类型之间的相似度或相异度计算。现实世界中，多维数据对象属性的类型、分布、值域以及权重都可能存在不同。这些问题需要采取适当措施进行处理。
当数据对象属性具有不同的域值时，即属性变量的大小变化范围不同、量纲不同、测量单位不同。如果不对属性值进行标准化处理，那么在使用欧几里德距离计算相似度时，将会受到属性值大的属性影响。例如，第一个变量的数量级是1000，而第二个变量的数量级是10，如v 1 =（2000,20）,v 2 = （5000,60），那么如果只有二维的点，欧氏距离为：
由上面可以很容易看出，当两个变量都变成数量级为10的时候，第一个变量存在一个权重：10，因而如果不使用相同尺度的时候，不同尺度的变量就会在计算的过程中自动地生成相应的权重。因而，如果两个变量在现实中的权重是相同的，就必须要先进行规范化，化成相同的尺度，以减去由尺度造成的误差。
另外，除值域不同外，属性之间可能存在相关性、数据呈非均匀分布，如正态分布等。解决这些问题的方法是使用欧几里德距离的扩展——马氏距离：
其中∑ -1 是数据协方差矩阵的逆。马氏距离有很多优点，马氏距离不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据（原始数据与均值之差）计算出的两点之间的马氏距离相同。马氏距离还可以排除变量之间相关性的干扰。
前面所述多维数据对象邻近度计算都是基于数据对象中所有属性具有相同的数据类型，但是，现实当中从数据库取出的数据类型可能是标称、数值、二元、序数等数据类型的组合。计算这种组合属性对象相似度最简单的方法是分别计算每个属性之间的相似度，然后取它们的平均值。但是，对于取值非对称属性，分别计算相似度累加取均值方法失效。例如，两个对象的二元非对称属性都取0值，并不能表示它们的相似性，可以在计算相似度时忽略，当二元非对称属性值为1时才加入相似度计算。
异种对象X,Y的相似度计算算法如下。
步骤1：将第k个属性标准化到区间[0,1]，计算相似度S k （X,Y）。
步骤2：创建一个指示变量δ k ，用来标示两个对象在第 k 个属性上是否同时取值为0，如果同时为0,δ k =0，否则δ k =1。
步骤3：使用如下公式计算对象X,Y的相似度：
前面所述所有相似度的计算，都是将对象的所有属性同等对待，没有区分不同属性的重要程度。当现实问题中属性的重要程度存在较大差异时，可以借助于领域专业知识，给它们赋予不同的权值，以期望获得更好的性能。相似度计算公式增加权值项后形式如下：
文档是由大量词语构成的，如果把特定词语出现的频率看作一个单独属性，那么文档可以由数千个词频属性构成的向量表示。词频向量通常很长，并且是稀疏的，因为它包括了大量的零值属性。统计两个文档中共同没有的词，即公共零值属性对计算它们间的相似度并没有多大帮助。对于文档这种特殊结构数据，使用基于距离计算邻近度的方法，会受到大量零值的影响，评估效果并不好。文档相似度需要关注两个文档同时出现的词语，以及这些词语出现的次数，忽略零匹配的数值数据度量。
余弦相似度，又称为余弦相似性，适合用来计算文档间的相似度。其原理是把两个文本文档以词频向量表示，通过计算两个向量的夹角余弦值来评估它们的相似度。
如果余弦值越接近于1，夹角越小，代表向量之间的匹配越大。而如果两个向量的余弦值为0，表示它们正交，没有匹配。
例2.2 假设有两个文档，新闻a和新闻b，将它们的内容经过分词、词频统计处理后得到如下两个向量：
文档a:（1,1,2,1,1,1,0,0,0）
文档b:（1,1,1,0,1,3,1,6,1）
使用余弦相似度来计算两个文档的相似度过程如下：
新闻a和新闻b对应的向量分别是x（x
1
,x
2
,…,x
100
）和y（y
1
,y
2
,…,y
100
），则新闻a和新闻b夹角θ的余弦
。
（1）计算向量a、b的点积：
（2）计算向量a、b的欧几里德范数，即||a||、||b||：
（3）计算相似度：
当两条新闻向量夹角等于0时，这两条新闻完全重复（用这个办法可以删除爬虫所收集网页中的重复网页）；当夹角接近于0时，两条新闻相似（可以用作文本分类）；夹角越大，两条新闻越不相关。
到现在为止，实现了基于属性的原始出现频率计算文档间的相似度。考虑一种情况，当两个文档之间如果有一个不常见的词语成功匹配，这应该要比它们匹配一个非常常见的词更能说明相似性。例如，我们设计一个垃圾邮件过滤系统，“免费”“特惠”“推广”这样的词语要比“你”“但是”“那里”等更能表征问题。所以，我们需要一个重要性调整系数来衡量一个词是不是常见词。用统计学语言表达，就是在词频的基础上，要对每个词语分配一个“重要性”权重。
词频—逆文档频率（Term Frequency-Inverse Document Frequency,TF-IDF）是一种用于资讯检索与资讯探勘的常用加权技术。基于统计学方法来评估词语对文档的重要性。字词的重要性随着它在文档中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
其中，词频（Term Frequency,TF）指的是某一个给定的词语在该文档中出现的次数。由于同一个词语在长文档里可能会比短文档有更高的词频，为了防止它偏向较长的文档，通常会采用词频除以文档总词数来归一化。
逆文档频率（Inverse Document Frequency, IDF）的主要思想是：出现频率较少的词才能够表达文档的主题。如果包含词语 w 的文档越少，IDF 值越大，则说明词条具有很好的类别区分能力。为了避免分母为0值，分母做加1处理。
最终TF-IDF的计算式为：
TF-IDF=词频（TF）×逆文档频率（IDF）
TF-IDF 算法用来对文档进行特征提取，选出可以表征文档特性的关键词。假设文档X由d个关键词的词频组成的向量h（x）表示，两篇文档X,Y的相似度可表示为：
需要说明的是，因为余弦值的范围是[-1,+1]，相似度计算时一般通过
把最终值归一化到[0,1]之间。
离散序列数据不同于多维数据，序列中的各个元素存在前后位置关系，如一个字符串、IP 地址、基因序列等。当两个离散序列数据对象长度相等，即序列中的元素可以一一对应的时候，相似度计算可以采用欧几里德距离、闵可夫斯基距离等计算。但是当序列长度不同时，需要新的计算方法。本节将介绍编辑距离和最长公共子序列两个常用的动态规划算法。
编辑距离（Edit Distance）是指将序列
变换为序列
所用的最少编辑操作次数
。编辑操作类型包括字符的替换、插入和删除，三种类型可以根据实际应用问题指定相同或不同的操作代价。一般来说，编辑距离越小，两个串的相似度越大。
例如，两个字符序列：abeedc 和 cbedac。我们可以有多种编辑方法将第一个序列转换成第二个序列。最简单的方法是将第一个序列先后经过将a替换成c，删除一个e，插入a，这三次编辑操作可完成将前者转换成后者。
假设序列
的前 i 个元素子序列为
的前 j 个元素子序列为
,Edit（i,j）表示它们之间的编辑距离，根据两个子序列末尾元素的不同，选择不同的编辑操作。编辑距离计算递推式如下：
当
为空时，编辑代价为将
中的所有元素删除：
当
为空时，编辑代价为j次插入操作：
图2-3 编辑距离计算矩阵和回溯路径
编辑距离具有下面几个性质：
（1）两个字符串的最小编辑距离是两个字符串的长度差；
（2）两个字符串的最大编辑距离是两字符串中较长字符串的长度；
（3）只有两个相等字符串的编辑距离才会为0;
（4）编辑距离满足三角不等式，即d（x,z）≤d（x,y）+d（y,z）；
例：有两个序列S 1 和S 2 ，分别为XGYXYXYX和XYXYXYTX。编辑距离计算矩阵如图2-3所示，最终计算结果为2，箭头标出了回溯路径。
最长公共子序列（Longest Common Subsequence,LCS）的定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。子序列要求左右两元素在母序列中为相邻元素，且前后顺序一致。
最长公共子串（要求连续）和最长公共子序列是不同的。如序列 adbfucijdlmen 和abf2ec3xdue，其中，bf 既是它们的公共子串同时也是它们的公共子序列，但是 abf 和cde 是它们的公共子序列但不是公共子串。很明显，两个序列的公共子序列越长，则表明这两个序列之间的相似度越高。
设序列X={x 1 ,x 2 ,…,x m }和Y={y 1 ,y 2 ,…,y n }的最长公共子序列为Z={z 1 ,z 2 ,…,z k }，则有如下特性：
（1）若x m =y n ，则z k =x m =y n ，且z k-1 是x m-1 和y n-1 的最长公共子序列。
（2）若x m ≠y n 且z k ≠x m ，则Z是x m-1 和Y的最长公共子序列。
（3）若x m ≠y n 且z k ≠y n ，则Z是X和y n-1 的最长公共子序列。
由此可见，2个序列的最长公共子序列包含了这2个序列前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质，可以使用动态规划算法求解。由最优子结构性质可建立递推关系如下：
当两个序列X,Y中任意一个为空集时，它们的最长公共子序列为零。即有LCSS（i,0）=0和LCSS（0,j）=0，这两个式子可以作为求解算法的边界条件。
相异度或相似度计算是数据挖掘应用中的重要问题。这是因为很多数据挖掘算法将距离度量方法作为关键子程序调用。距离度量方法深受数据类型、数据维度及数据分布的影响，并且距离度量方法直接影响数据挖掘的最终成效。