Unsupervised learning methods(Si

2022-01-05  本文已影响0人  Natsu想当科学家

1:Similarity matching


就其意义而言,欧氏距离越小,两个用户相似度就越大,欧氏距离越大,两个用户相似度就越小。
在日常使用中,一般习惯于将相似度与1类比,相似度在数值上反映为0<=Similarity(X,y)<=1,越接近1,相似度越高;
那么我们在使用欧几里得距离时,可以通过 1/(1+Distance(X,Y))来贯彻上一理念。


2:数据有不同类型,如何进行数据的规范化进而计算距离:

样本属性可能有的类型有:数值型,命名型,布尔型……在计算样本之间的距离时,需要将不同类型属性分开计算,最后统一相加,得到两个样本之间的距离。下面将介绍不同类型的属性的数据计算方法。


也叫离差标准化,是对原始数据的线性变换,使结果落到[0,1]区间,转换函数如下:


image.png

其中Vi 表示在第i条记录在A这个属性上的取值,MINA表示A这个属性上的最小值,new_maxA表示我们希望映射到的区间的右边界,其他同理。

这种方法有一个缺陷就是当有新数据加入时,可能导致max和min的变化,需要重新定义。




3:计算距离:

图中蓝色和黄色的线代表曼哈顿距离,绿色的线代表欧几里得距离即欧式距离
计算公式:

image.png

Jaccard距离用来度量两个集合之间的差异性,它是Jaccard的相似系数的补集,被定义为1减去Jaccard相似系数。


Jaccard Distance

总的变换距离(the total variation distance),记为 Δ(P, Q),是上述等式的一半。
显然:


image.png

对于概率分布 P = {pi}i∈[n], Q = {qi}i∈[n],两者之间的Hellinger distance 定义为:


image.png

根据定义,Hellinger distance 是一种满足三角不等式(triangle inequality)的度量。根号下2是为了确保对于所有的概率分布,都有 h(P, Q) <= 1。


上表表示对与不同的样本i,j,统计它们布尔型同时为1的属性个数,同时为0的属性个数,分别为1和0的属性个数,它们的距离计算方式如下所示:


image.png

这个公式的含义其实就是两个样本之间,取值不同的属性的数量与所有属性的数量的比值。

4:Clustering

Use'Similarity' measure to group data items.
主要思想:首先人为决定将要将数据集分为k个簇,然后根据簇内部相似性要尽可能大,簇之间相似性要尽可能小的思想,将样本分到不同的簇当中去。

中心思想:
层次聚类,是一种很直观的算法。顾名思义就是要一层一层地进行聚类,可以从下而上地把小的cluster合并聚集,也可以从上而下地将大的cluster进行分割。似乎一般用得比较多的是从下而上地聚集,因此这里我就只介绍这一种。
所谓从下而上地合并cluster,具体而言,就是每次找到距离最短的两个cluster,然后进行合并成一个大的cluster,直到全部合并为一个cluster。整个过程就是建立一个树结构,类似于下图。

Hierarchical Clustering

那 么,如何判断两个cluster之间的距离呢?一开始每个数据点独自作为一个类,它们的距离就是这两个点之间的距离。而对于包含不止一个数据点的 cluster,就可以选择多种方法了。最常用的,就是average-linkage,即计算两个cluster各自数据点的两两距离的平均值。类似的 还有single-linkage/complete-linkage,选择两个cluster中距离最短/最长的一对数据点的距离作为类的距离。

公式

image.png

Hierarchical Clustering特点:
1)Start with each node as its own Cluster

  1. Merge Cluster based on Similarity
  2. Iterate until there is only 1 Cluster

4.2: Clustering around Centroids(围绕中心点聚类)

  1. 选定 K 个中心Uk的初值。这个过程通常是针对具体的问题有一些启发式的选取方法,或者大多数情况下采用随机选取的办法。因为前面说过 k-means 并不能保证全局最优,而是否能收敛到全局最优解其实和初值的选取有很大的关系,所以有时候我们会多次选取初值跑 k-means ,并取其中最好的一次结果。
    2)将每个数据点归类到离它最近的那个中心点所代表的 cluster 中。
    3)用公式


    image.png

    计算出每个 cluster 的新的中心点。
    4)重复第二步,一直到迭代了最大的步数或者前后的J的值相差小于一个阈值为止。

Find Points and Calculate centroids

K-medoid method 相对k-means 来说比较不受离群点的干扰。

上一篇 下一篇

猜你喜欢

热点阅读