基于约束的聚类和在线聚类
聚类分析
基于约束的聚类
①个体对象的约束
②聚类参数选择的约束
③距离或相似度函数的约束
④用户对各个簇的性质指定约束
⑤基于“部分”监督的半监督聚类
聚类分析
基于约束的聚类
含有障碍物的对象聚类
思考：如何不游泳而使用河对面的自动取款机。
聚类分析
基于约束的聚类
含有障碍物的对象聚类
障碍物问题的实质是对距离函数产生约束。
划分的聚类方法是解决障碍物问题的一种较好的选择，因为它
最小化对象和它们的簇中心之间的距离。
如果选择K-means方法，在障碍物存在的情况下，簇中心可能
是不可达的。
聚类分析
基于约束的聚类
用户约束的聚类分析
一家快递公司的快递送达服务满足约束：
（1）每站至少服务100个高价值客户；
（2）每站至少服务5000个普通客户。
思考：
如何确定共服务n个客户的k个服务点的位置，使客户和
服务站之间的路程最小。
聚类分析
基于约束的聚类
用户约束的聚类分析
这本质上，可以认为这是一个受约束的最优化问题。
用数学规划方法解决这个问题的代价是巨大的，比如要联立数百万的方程。
聚类分析
基于约束的聚类
用户约束的聚类分析
一种有效的方法是采用一种微聚类的思想
Ø 通过把数据集划分为k组寻找一个初始“解”，每组满足用户指定的
约束。
Ø 再把对象从一个簇转移到另一个簇来迭代的改进这个解，同时还要满
足那些约束。
聚类分析
基于约束的聚类
半监督聚类分析
半监督聚类方法
基于约束的半监督聚类
基于距离的半监督聚类
聚类分析
在线聚类
针对数据随时间会发生变化的数据集，研究者提出在线聚类算法处理这类问题。
在线学习产生的问题
聚类结果常常表现出对于准则函数中参数变化过于敏感，特别是当这些方法用于
在线学习时，可能会出现聚类结构不稳定的问题，簇的波动或者漂移。
如果数据内部结构不稳定而且新获得的信息会造成较大的结构重组，那么问题就
会变得比较复杂，因而就不能把问题只归因于特定的聚类描述。（稳定性/可塑性
两难问题）
聚类分析
在线聚类
“竞争学习”
“竞争学习” 只对与新到样本最相似的一个聚类中心进行调整。
因此与该样本无关的其它类的性质得以保留。
竞争学习源自神经网络，在线聚类方法是多种思想结合的产物。
The End
