聚类分析及算法
聚类分析
聚类的目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别的个体之间的距离尽可能的大。是分类的逆向方法，是一种无监督的分类。 一般包括层次分析和非层次分析。层次分析可以得到概念间的逻辑关系，非层次分析可以得到概念的同义词聚类。 主要集中在基于距离的聚类分析（如基于K均值，K-MEDOIDS等）。
聚类算法
层次聚类算法
结果是一棵生成树。每次都合并两个距离最近的资源Ci,Cj，将其合并为一个资源Ck，Ck就是这两个资源的根，然后将Ck再放入资源库中继续进行资源之间的距离计算，然后再合并距离最近的资源，如此重复，直到只剩下一个资源为止。 典型算法是CURE算法。该算法不用单个质心或对象作为一个聚类的代表，而是选择数据空间中固定数目的具有代表性的点。（如何选择？？）
划分聚类算法
是一种基于原型的聚类方法，本质是先随机地选择几个对象作为原型，然后将将其他对象分配到这几个原型代表的类中，结束后，采用迭代方式的重定位（用一个函数计算所有对象到均值的方差之和）技术，来将对象在不同的划分间移动来改进划分，当类间差异最大而类内差异最小时，算法终止。 代表算法是K-means。
标签聚类的基本过程
目标资源集-获取tag集合-tag的预处理-特征提取-聚类处理--聚类和输出。 对标签特征的提取可以采用不同的方法，如可利用标签标注相关资源的频率，标签的共现，标签对的共现，标签的上下文等；聚类算法可采用前面所述的聚类算法中的一种或组合。 根据特征提取方法的不同有以下几种不同的标签聚类算法。
基于共现信息的标签聚类
共现分析
理论基础之一是心理学的邻近联系法则：曾经在一起感受过的对象往往在想象中也联系在一起，以至于想起他们中的某一个的时候，其他的对象也会以曾经同时出现时的顺序被想起，即只有存在语义关联的词汇才能被作者在相邻的位置记录下来。
标签共现分析
标签的共现：若标签Ti和Tj标注了同一个资源，则称Ti和Tj共现。例如，很多人同时使用“文学”和“小说”标注同一个网络资源，就说明这两个标签具有语义关系。计算共现的次数是评价两个标签之间的相似性的一种最简单的方式。（标签相似度的计算方法才考P102）
基于共现信息的标签聚类算法模型
基础是标签共现矩阵。 步骤：
首先构建共现矩阵
首先需要有标签与资源的关系表，格式如P103；
构建标注矩阵Cmn，矩阵大小是Cmn,其中的Cij表示使用第j个标签标注第i个资源的频度。
构建关联矩阵Amn，在标注矩阵的基础上加入了标签的权重因素。Aij=Cij*log(m/U(ti))其中U(ti)表示使用标签ti标注的资源数。
构建共现矩阵Smm，也就是相似度矩阵。在Amn中的每一个标签都相当于矩阵中的一个列向量，标签之间的相似度的计算就可以转化为标签向量在空间中的距离计算。就使用余弦来计算两个向量的相似性。
聚类，方法结合了层次聚类和划分聚类。
聚类
1. 首先将T中的每一个标签Ti看做是一个具有单个成员的簇Ci={Ti} 2. 任选其中一个成员簇Ci作为聚类的起点 3. 在其余未聚类的样本中，找到与Ci距离满足条件的Tj（可以是距离最近也可以是不
超过阈值的点），将Tj归入Ci形成一个新的簇Ck=Ci∪Tj；
4. 重复步骤三，直至与Ci距离最近的点也不满足条件时，认为已经聚完了一类。 5. 选择一个未聚类的单个成员簇，重复步骤3和4，开始新的一轮聚类，直至所有的
单个成员簇都参与了聚类。
算法分析
不需要比较所有簇之间的相似度，执行速度快，适合大量文件的集合，实用高。 不需要事先确定K的值。
基于标签相关性的标签聚类
相关标签：豆瓣网中标签“诗歌”，“杂文”，“编程”可以分别用（诗词，诗，现代诗歌，楚辞，唐诗，诗集，文学，随笔），（随笔，社会，文化，文学，思想，人文）和（程序设计，计算机，算法，软件开发，计算机语言）这样一些相关标签进行描述，可以看出，“诗歌”和“杂文”中都有“文学”和“随笔”相关标签，而“编程”与他们都没有相同的相关标签。 所以，我们可以检索与某一个标签相关的标签，抽取与检索词同时出现的标签作为描述项，采用传统空间向量模型表示，计算标签之间的相关度，从而进行标签聚类。
标签向量空间表示
某一个标签的向量空间表示为：V(d)=(t1,w1(d);t2,w2(d);…ti,wi(d),….tn,wn(d)),其中，ti表示第i个相关的标签，wi(d)表示ti在向量中的权重，其计算方法采用传统的TF-IDF权重计算方式。
Wt,i(d)=(1+logfi,j)*log(N/ni+0.01)
其中，logfi,j表示ti在向量中出现的频率（即TF），N表示标签总数量，ni表示ti在相关标签向量中出现的次数(即IDF)。 TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与文本挖掘的常用加权技术。
TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
TF: 词频（term frequency，TF）指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被正规化，以防止它偏向长的文件。（同一个词语在长文件里可能会比短文件有更高的词频，而不管该词语重要与否。）对于在某一特定文件里的词语 ti 来说，它的重要性可表示为：
ni,j 是该词在文件dj中的出现次数，而分母则是在文件dj中所有字词的出现次数之和。
IDF: 逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到
然后采用余弦相似度来计算标签的相似度。
聚类算法
采用凝聚式层次聚类算法进行聚类。
没有算法分析。
基于关联规则的tag资源聚类
关联规则
支持度：同时包含数据项的概率，支持度说明了这条规则在所有事务中有多大的代表性，支持度越大，关联规则越重要，应用越广泛。 置信度：是对关联规则的准确度的衡量。 期望置信度：包含项集Y的概率。描述了在没有任何条件影响时，项集Y在所有事务中出现的概率。 作用度：是可信度与期望置信度之间的比值。作用度描述了项集X的出现对项集Y有多大影响。 强规则：称满足最小支持度和置信度要求的规则成为强规则。 频繁项集：支持度大于最小支持度的项集。
基于关联规则的Tag资源聚类算法模型
数据采集和表示
用每个资源的tag频率作为该tag资源向量空间的特征项表示。
构建初始聚类
如果一个标签tag在不低于某个特定比例的tag资源中进行标注，则称tag是一个频繁项，这个特定比例就是最小支持度。首先我们要找到所有满足频繁项条件的tag集合，然后根据这个集合构造一个初始簇，这个初始簇是由所有包含某一个频繁项tag的资源组成。如下图所示： 簇 C(t1) C(t2) C(t3) C(t4) 簇资源集 U1,u3,u8,u9,u11,u12 U6,u8,u11,u12 U1,u6,u10 U2,u4,u5,u7,u8,u9,u10,u11,u12,u14 构造簇规则集
簇频繁项：首先是一个频繁项，并且在不低于指定比例的簇资源中出现的tag。如，对于簇C(t1)而言，t2在它的簇资源中出现的比利是3/7，大于最小支持度，所以t2就是该簇的一个簇频繁项。 构造每个簇的簇规则集，需要挑选每个簇的簇频繁项，这个簇频繁项还要满足置信度，
然后每个簇频繁项都对应于该簇的一条规则。 由此构造出来的初始簇规则集如下图所示： 簇 C(t1) C(t2) C(t3) C(t4) 簇规则集 T1.sup=1.0,t1.conf=1.0 t2.sup=0.43,t2.conf=0.75 T4.sup=0.71,t4.conf=0.5 T1.sup=0.75,t1.conf=0.43 t2.sup=1.0,t2.conf=1.0 T4.sup=0.75,t4.conf=0.3 T1.sup=0.67,t1.conf=0.29 t3.sup=1.0,t3.conf=1.0 T1.sup=0.5,t1.conf=0.75 t4.sup=1.0,t4.conf=1.0 根据簇规则集重新聚类