5.4基于约束的聚类和在线聚类

基于约束的聚类和在线聚类主讲人：李侃聚类分析基于约束的聚类①个体对象的约束②聚类参数选择的约束③距离或相似度函数的约束④用户对各个簇的性质指定约束⑤基于“部分”监督的半监督聚类聚类分析基于约束的聚类含有障碍物的对象聚类思考：如何不游泳而使用河对面的自动取款机。聚类分析基于约束的聚类含有障碍物的对象聚类障碍物问题的实质是对距离函数产生约束。划分的聚类方法是解决障碍物问题的一种较好的选择，因为它最小化对象和它们的簇中心之间的距离。如果选择K-means方法，在障碍物存在的情况下，簇中心可能是不可达的。聚类分析基于约束的聚类用户约束的聚类分析一家快递公司的快递送达服务满足约束：（1）每站至少服务100个高价值客户；（2）每站至少服务5000个普通客户。思考：如何确定共服务n个客户的k个服务点的位置，使客户和服务站之间的路程最小。聚类分析基于约束的聚类用户约束的聚类分析这本质上，可以认为这是一个受约束的最优化问题。用数学规划方法解决这个问题的代价是巨大的，比如要联立数百万的方程。聚类分析基于约束的聚类用户约束的聚类分析一种有效的方法是采用一种微聚类的思想通过把数据集划分为k组寻找一个初始“解”，每组满足用户指定的约束。再把对象从一个簇转移到另一个簇来迭代的改进这个解，同时还要满足那些约束。聚类分析基于约束的聚类半监督聚类分析半监督聚类方法基于约束的半监督聚类基于距离的半监督聚类聚类分析在线聚类针对数据随时间会发生变化的数据集，研究者提出在线聚类算法处理这类问题。在线学习产生的问题聚类结果常常表现出对于准则函数中参数变化过于敏感，特别是当这些方法用于在线学习时，可能会出现聚类结构不稳定的问题，簇的波动或者漂移。如果数据内部结构不稳定而且新获得的信息会造成较大的结构重组，那么问题就会变得比较复杂，因而就不能把问题只归因于特定的聚类描述。（稳定性/可塑性两难问题）聚类分析在线聚类“竞争学习”“竞争学习”只对与新到样本最相似的一个聚类中心进行调整。因此与该样本无关的其它类的性质得以保留。竞争学习源自神经网络，在线聚类方法是多种思想结合的产物。聚类分析聚类与降维聚类按照某个特定标准(如距离准则)把一个数据集分成不同的簇，使得同一簇内的数据相似性尽可能大，同时不在同一个簇中的数据差异性尽可能大。降维一种对高维特征数据预处理方法，它是用维数更低的子空间来表示原来高维的特征空间。聚类分析聚类与降维降维是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的。方法特征选择技术特征变换技术聚类分析聚类与降维特征选择技术特征选择技术又称属性子集选择或者特征子集选择，对它最简单的理解就是从高维数据中选择出若干最“有用”的维度进行聚类计算。选择属性子集的过程可以一般用有监督的方法，如找出与所求问题最相关的属性集同时，它也可以使用无监督的方法，如熵分析等。聚类分析聚类与降维特征变换技术特征变换技术把数据转换到一个较小的空间，同时保持对象间原始的相对距离。它们通过创建属性的线性组合等方式来汇总数据，可能发现数据中的隐藏结构。这种技术没有真正的从分析中剔除任何原始属性聚类分析聚类与降维特征变换技术主成分分析（principalcomponentanalysis，PCA）主成分分析的两种实现方式：特征值分解奇异值分解聚类分析聚类与降维特征值分解如果一个向量v是方阵A的特征向量，则有：其中，称为特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。特征值分解：将一个矩阵分解成：其中，Q是这个矩阵A的特征向量组成的矩阵，E是一个对角阵，每一个对角线上的元素就是一个特征值。特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。聚类分析聚类与降维奇异值分解奇异值分解实质上是将上述分解从方阵推广到任意矩阵的一种分解方法：PCA的数学表示为：奇异值分解的数学表示为：这两个公式可以分别变换为：和