算法名称：FLOC：flexibleoverlapped clustering

文章名称：Yang J, Wang W, Wang H, Yu P. -Clusters: capturing subspace correlation in a large dataset. Proceedings of the 18th IEEE international conference on data engineering.California,USA, 2002, 517～528

摘要：

近年来，聚类由于其在实践中重要性而被大家活跃的研究。其中大多数聚类模型都是集中在分组一群具有相似值的个体也就是子空间聚类并假定每一个个体在每个维度上都有相关的值。这些已经存在的聚类模型并不够充分找到物体之间的内聚性。一群物体仍有可能在一组条件子集上有较强的内聚性即使他们在每一维上都取不同的值甚至没有值。这在包括生物信息学的很多领域上都有广泛的应用，比如数据有偏差且不充足的协同过滤分析领域上。在生物信息学里，双聚类模型已经被提出来捕捉一组子集在一个条件子集上的聚合性。在本文里引入了一个更广泛的称之为-聚类的模型来捕捉一组物体在一个条件子集上的内聚性且允许有缺失值。一个基于移动的算法（FLOC）被设计出来用以高效的产生一个接近最优的聚类结果。-聚类模型把双聚类模型当作一个特例，在-聚类上FLOC算法运行的远优于双聚类算法。我们证明了-聚类模型以及FLOC算法在大量实际和合成数据集上的正确性和有效性。

论文概要内容：

   论文中首先提出了一个观点：一些样本点尽管就整体来说是不相似的，但在其子空间上仍有可能是高度相似的，并提出了-聚类的概念，并指出了其与空间子聚类的区别是-聚类模型中允许出现缺失值，随后给出了-聚类和-聚类体积的定义，以及关于物体，条件和-聚类的基（base）的定义，并据其引入了元素残差的概念，注意的是对于缺失值其残差定义为0，最后给出了-聚类的残差的概念和行方差的概念。由于-聚类允许出现缺失值，所以克服了随机干扰效应（random interference）。

   接下来论文给出了动作（action）的概念，动作的定义是建立在一个双聚类和一个行或列上的，对于一个指定的双聚类和指定的行或列，动作被定义成行或列关于双聚类的成员变化，也就是如果双聚类有行或列,就删除它；否则就增加它到双聚类中。为了判断每一个动作的好与坏，在论文中结合算法的目的也就是说找到双聚类的残差小于指定值且双聚类的容量（volume）要大，引入了相应动作的收益（gain）概念。其定义为双聚类执行动作前后残差之差。

FLOC算法描述：

初始化：随机生成初始双聚类的集合。

迭代：对所有的行和列寻找使得双聚类最优的动作，然后执行该动作，并判断该动作是否使得的双聚类集的总体残差有没有下降，如果下降重复第二阶段，否则结束程序。

      随后论文分析了算法的性能，并描述了如何有效生成初始双聚类，并分析了动作的执行顺序对算法的性能，同时提出了三种动作执行顺序，分别是顺序执行，随机执行和加权执行。最后通过实际数据集和合成数据集对算法的性能进行了验证，并给出了实验结果。注意的是在比较实验结果的时候除了残差外本文还提出了二个比较优劣的标准，分别回收率（recall）和精度（precision）。假定是数据集中真实双聚类的集合，是双聚类算法找到的双聚类的集合，那么回收率就定义为，精度就定义为。

      在论文中还提出了几个改进程序性能的策略，一是通过选择合适的参数来控制初始双聚类的大小以期望和实际的双聚类大小基本上一致。二是改进各个最优动作执行的顺序，基本版本算法采用的是顺序执行，本文还提出了二种改进策略：随机策略和加权随机策略。随机策略就是各个动作的执行是按照随机生成的行列顺序来执行动作，所有的行列以等概率的优先权来执行；加权随机策略是在随机顺序策略的基础上考虑了动作收益，动作收益大的行列优先执行的概率大，收益小的优先执行概率小。

论文结论：实验数据表明双聚类算法优于传统的聚类算法。

实现论文算法后的实验结果：

1，实现的FLOC算法在时间性能上和原论文相比由较大出入。

2，控制初始双聚类算法的参数对程序的结果影响较大

3，动作收益这个概念的定义没有考虑双聚类的大小，导致找到的双聚类在列的数目上没有办法控制。

后续论文对其改进：

     论文名称：Yang J, Wang W, Wang H, Yu P.Enhanced biclustering on expression data. Proceedings of the third IEEEconference on bioinformatics and bioengineering. Bethesda, USA, 2003, 321～327.

      改进地方：

1，  在这篇论文中在前面论文的基础上改进了动作收益的定义，考虑了双聚类的大小和双聚类的最大阈值。

2，  准确的定义了加权随机策略的实现机制，也就是如何根据动作收益计算该动作优先执行的概率。