2.4 高维数据
2.4.1 高维数据的形态
数据挖掘技术在许多领域已经得到了广泛的应用，在这些应用中，由于现实的世界是复杂的世界，所有现实世界中获得的数据也越来越复杂，其突出表现之一就是，数据的属性很多或维数很高，其维数甚至高达上千乃至上万维。对这类数据进行挖掘就是高维数据挖掘问题。下面列举一些常见的高维数据类型［2，63～68］。
1.基因表达数据
基因表达数据最初是用来解决基因芯片问题的，如酵母基因芯片实验可产生6223种基因在79种条件下的表达数据。如果用行向量表示基因对象，列向量代表条件，则基因表达数据就可以用矩阵描述，即DNA微阵列数据。后来，该数据被应用到生物学领域，成为该学科的一项突破性技术微阵列（microarray）。实际应用中，微阵列可以用来对单个细胞样本中的基因进行定量研究，计算一个基因在特定条件下的mRNA的相对丰度。
2.文本和Web数据
在信息检索领域中常用的文档，如果一个特征词向量对应一个文档，则用特征词向量属性描述某个特征词在该文档中出现的频率或对该文档的贡献。为了方便搜索引擎的使用，常常提供成千上万个特征词，描述该文本的属性也可以包括很多，因此，这种表示文档的特征词向量是一种高维数据。
对于Web数据，如果把Web服务器中的每一个Web页都看作一个对象，用属性如用户是否访问该网页或在该网页停留的时间等来描述对象，由于服务器可以有很多Web页，且其描述对象的属性也很多，那么，这种Web数据的描述是一种高维数据。
3.图像数据
在图像识别中，需处理的数据通常是m×n大小的灰度图像。如果把每幅图像看作图像空间中的一个点，那么该空间的维数将是m×n维。例如，当m=n=25时，维数就可达625维。
4.购物篮数据
零售商业中客户所购商品的交易数据统称为购物篮数据，其包括所有客户购买商品的种类、数量以及购买的次数。在交易数据库中，如果将客户的每次购物行为作为对象，购买的具体商品作为属性，那么，可以用对象属性的关系描述客户的购买情况。通常，为了描述问题的方便，交易记录中用“1”表示有客户购买了某种商品或一个其他有意义的数值，如商品的件数或价值等，用“0”或计为空表示客户没有购买这种商品。超市中购物的客户人数可以成千上万，购买的商品同样是多种多样的，这种购物篮数据实际上是一种高维数据。
5.时间序列数据
在实际应用中，如果在相同的时间间隔或相同的采集频率得到一组随时间变化而变化的数据，这就是时间序列数据。这类数据的典型特征是，该数据是，关于时间的函数，如自动化生产过程中的实时数据、历史数据，证券期货（包括股票）的交易数据等。
如果相同的时间间隔用时间序列t1，t2，…，tn来表示，事件在这段时间序列内的取值用x1，x2，…，xn来表示，那么，事件可以表示为X=x1，x2，…，xn，即时间序列数据就成了一个n维的向量。在实际中，时间序列的长度很长，因而时间序列数据是一种高维数据。
另外，在信息安全等的应用中，数据也普遍存在高维和大规模的特点。
2.4.2 高维数据的特点
杨凤召［6］和陈黎飞［69］总结了高维数据的特点，可概括为以下三个方面。
1.稀疏性
假设一个d维的数据集D存在于一个超立方体单元a［0，1］d中，数据在空间中的分布均匀，并且各个维数据之间是相互独立的。在一个边长为S的超级立方体范围内，一个点在这个范围内的概率为Sd（s＜1），这样，随着维数d的增大，这个概率的值会越来越小，即在一个很大的范围内很可能存在没有任何数据点的现象。例如，当d=100时，一个边长为0.95的超级立方体范围只包含0.59%的数据点。由于这个超级立方体范围可以位于数据空间的任何地方，由此得出结论，在高维空间中数据点是异常稀疏的。
2.空间现象
笔者曾做过一个实验，关于正态分布数据的密度函数，当维数大约增加到10维时，竟然只有不到1%的数据点分布在中心（期望值附近）。
3.维度效应［4］
Bellman提出了“维度效应”这一术语，其最初的含义是指，不可能在一个离散的多维网格上用蛮力搜索去优化一个有着很多变量的函数。原因是，网格的数目会随着维数即变量的数目呈指数级增长。例如，在维度小于16维（d＜16）时，聚类方法中使用的索引会有效地发挥作用，但当维数d＞20时，它们的性能就会降到顺序搜索的水平。随着时间的推移，“维度效应”这一术语用来泛指在数据分析中遇到的由于变量（属性）过多而引起的所有问题。
“维度效应”在高维数据聚类中引起的这些问题主要表现在三个方面。
（1）距离函数难以定义。聚类分析中聚类的判断依据是数据对象之间差异度的相对大小，差异度值小的对象聚为一类，差异度值大的对象则各为一类。在低维空间中，经常使用距离标准如欧氏距离等来度量差异度，而在高维空间中，由于相似性没有传递性，这种基于距离函数的差异度计算的方法将失效，必须考虑新的度量数据对象相似性或者差异度的度量方法。
（2）距离趋零现象。在高维情况下，按距离计算的类的均值会很接近，对于给定的数据点，距离其最远和最近的数据点间的距离会随着维度的增加渐趋于零，这称之为“差距趋零现象”［70］。数据挖掘方法由于无法明确区分类的中心而无法进行。
（3）计算复杂度高。由于高维数据维数很高，传统聚类方法的计算复杂度会相应地增加，甚至导致效率低到不可接受的状态，这使得数据挖掘方法的应用有着极大的局限性。
一般来讲，处理高维数据进行聚类分析的常用方法是降维（维度约简），将高维数据空间通过某种方式转化为低维的可处理的空间，并且聚类结果能够扩展或映射到整个高维空间。下面主要从聚类的角度阐述“维度约简”相关内容。