[关闭]
@mynameiszhangxu 2015-01-06T07:39:13.000000Z 字数 5678 阅读 2499

数据挖掘算法认知与实践

数据挖掘

鸢尾花数据集

数据集包含了50个样本，都属于鸢尾属下的三个亚属，分别是山鸢尾、变色鸢尾和维吉尼亚鸢尾（英语：Virginia Iris）。四个特征被用作样本的定量分析，它们分别是花萼和花瓣的长度和宽度。
鸢尾花数据集

Kmeans聚类算法

算法内容

Kmeans作为数据挖掘十大经典算法，对其进行必要的了解对数据挖掘的学习有重要意义。
作为最经典的基于划分的聚类方法，其基本思想极为简单：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
具体做法如下（假设将样本集分为 n 类）:

  1. 适当的选择 n 个类的初始中心；

  2. 在第k次迭代中，对任意一个样本，求其到 n 各中心的距离，将该样本归到距离最短的中心所在的类;

  3. 利用均值等方法更新该类的中心值

  4. 对于所有的 n 个聚类中心，如果利用 步骤2和3的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。

测试（以安德森鸢尾花数据集为例）

在传入分类数时，设定值为 3
KM.setNumClusters(3);
代码如下

  1. import java.io.File;
  3. import weka.clusterers.SimpleKMeans;
  4. import weka.core.DistanceFunction;
  5. import weka.core.EuclideanDistance;
  6. import weka.core.Instances;
  7. import weka.core.converters.ArffLoader;
  9. public class kmwan {
  10.     /**
  11.      * @param args
  12.      */
  13.     public static void main(String[] args) {
  14.        // TODO Auto-generated method stub
  15.        Instances ins = null;
  16.        Instances tempIns = null;
  18.        SimpleKMeans KM = null;
  19.        DistanceFunction disFun = null;
  20.        try{
  21.            /*
  22.             * 1.读入样本
  23.             */
  24.            File file= new File("E:/__tools__/weka/Weka-3-6/data/iris.arff");
  25.            ArffLoader loader = new ArffLoader();
  26.            loader.setFile(file);
  27.            ins = loader.getDataSet();
  29.            /*
  30.             * 2.初始化聚类器
  31.             */
  32.            KM = new SimpleKMeans();       
  33.            //设置聚类要得到的类别数量
  34.            KM.setNumClusters(3);
  36.            /*
  37.             * 3.使用聚类算法对样本进行聚类
  38.             */
  39.            KM.buildClusterer(ins);
  41.            /*
  42.             * 4.打印聚类结果
  43.             */
  44.            tempIns = KM.getClusterCentroids();
  45.            System.out.println("CentroIds: " + tempIns);
  48.        }catch(Exception e){
  49.            e.printStackTrace();
  50.        }
  51.     }
  53. }

此时 挖掘结果为

  1. 5.936,2.77,4.26,1.326,Iris-versicolor
  2. 5.006,3.418,1.464,0.244,Iris-setosa
  3. 6.588,2.974,5.552,2.026,Iris-virginica

可以看出 Kmeans 方法在类别数量为 3 的时候 ，很确切的通过线性聚类的方法，将数据集中的数据分为了三类。
当我们将类别数的值定为4的时候KM.setNumClusters(4);
结果显示为如下数据：

  1. 6.329167,2.979167,4.6,1.4625,Iris-versicolor
  2. 5.573077,2.576923,3.946154,1.2,Iris-versicolor
  3. 6.588,2.974,5.552,2.026,Iris-virginica
  4. 5.006,3.418,1.464,0.244,Iris-setosa

从中我们可以简单的发现：类别为“versicolor”的鸢尾花可能在整个种群中占更多的数量。这就是我们通过数据挖掘获得的情报。
当我们将类别数的值定为4的时候KM.setNumClusters(2);
数据显示如下：

  1. 6.262,2.872,4.906,1.676,Iris-versicolor
  2. 5.006,3.418,1.464,0.244,Iris-setosa

这时候算法将其分成了两个类别“versicolor”和“setosa”，说明只能用两种类型的鸢尾花表示整个族群的话，“virginica”这个种类将被会其他两种代表，也就是说这个种类在整个族群中不如其他两种具有代表性。这也是我们通过简单的数据挖掘发现的情报。

ChiMerge 算法

算法内容

ChiMerge 是监督的、自底向上的(即基于合并的)数据离散化方法。它依赖于卡方分析：具有最小卡方值的相邻区间合并在一起，直到满足确定的停止准则。
基本思想：对于精确的离散化，相对类频率在一个区间内应当完全一致。因此，如果两个相邻的区间具有非常类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低卡方值表明它们具有相似的类分布。
方法如下：
一、初始化
根据要离散的属性对实例进行排序：每个实例属于一个区间；
二、合并区间，又包括两步骤
(1) 计算每一对相邻区间的卡方值
(2) 将卡方值最小的一对区间合并
卡方计算公式：
卡方计算公式

参数说明

m=2（每次比较的区间数是2个）
k=类别数量
Aij=第i区间第j类的实例的数量
Ri=第i区间的实例数量
Ri代表的内容
Cj=第j类的实例数量
Ci代表的内容
N=总的实例数量
N代表的内容
Eij= Aij的期望频率

测试（以安德森鸢尾花数据集为例）

取鸢尾花数据集作为待离散化的数据集合，使用ChiMerge算法，对四个数值属性分别进行离散化，令停机准则为max_interval=6；主要有两个步骤：

第一步，整理数据
读入鸢尾花数据集，构造可以在其上使用ChiMerge的数据结构，即, 形如 [('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]),...]的列表，每一个元素是一个元组，元组的第一项是字符串，表示区间左端点，元组的第二项是一个列表，表示在此区间各个类别的实例数目；
第二步，离散化
使用ChiMerge方法对具有最小卡方值的相邻区间进行合并，直到满足最大区间数(max_interval)为6
程序最终返回区间的分裂点

  1. from time import ctime
  3. def read(file):
  4.     '''read raw date from a file '''
  5.     Instances=[]
  6.     fp=open(file,'r')
  7.     for line in fp:
  8.         line=line.strip('\n') #discard '\n'
  9.         if line!='':
  10.             Instances.append(line.split(','))
  11.     fp.close()
  12.     return(Instances)
  15. def split(Instances,i):
  16.     ''' Split the 4 attibutes, collect the data of the ith attributs, i=0,1,2,3
  17.         Return a list like [['0.2', 'Iris-setosa'], ['0.2', 'Iris-setosa'],...]'''
  18.     log=[]
  19.     for r in Instances:
  20.         log.append([r[i],r[4]])
  21.     return(log)
  24. def count(log):
  25.     '''Count the number of the same record
  26.        Return a list like [['4.3', 'Iris-setosa', 1], ['4.4', 'Iris-setosa', 3],...]'''
  27.     log_cnt=[]
  28.     log.sort(key=lambda log:log[0])
  29.     i=0
  30.     while(i<len(log)):
  31.         cnt=log.count(log[i])#count the number of the same record
  32.         record=log[i][:]
  33.         record.append(cnt) # the return value of append is None
  34.         log_cnt.append(record)
  35.         i+=cnt#count the next diferent item 
  36.     return(log_cnt)
  39. def build(log_cnt):
  40.     '''Build a structure (a list of truples) that ChiMerge algorithm works properly on it '''
  41.     log_dic={}
  42.     for record in log_cnt:
  43.         if record[0] not in log_dic.keys():
  44.             log_dic[record[0]]=[0,0,0]
  45.         if record[1]=='Iris-setosa':
  46.             log_dic[record[0]][0]=record[2]
  47.         elif record[1]=='Iris-versicolor':
  48.             log_dic[record[0]][1]=record[2]
  49.         elif record[1]=='Iris-virginica':
  50.             log_dic[record[0]][2]=record[2]
  51.         else:
  52.             raise TypeError("Data Exception")
  53.     log_truple=sorted(log_dic.items())
  54.     return(log_truple)
  56. def collect(Instances,i):
  57.     ''' collect data for discretization '''
  58.     log=split(Instances,i)
  59.     log_cnt=count(log)
  60.     log_tuple=build(log_cnt)
  61.     return(log_tuple)
  64. def combine(a,b):
  65.     '''  a=('4.4', [3, 1, 0]), b=('4.5', [1, 0, 2])
  66.          combine(a,b)=('4.4', [4, 1, 2])  '''
  67.     c=a[:] # c[0]=a[0]
  68.     for i in range(len(a[1])):
  69.         c[1][i]+=b[1][i]
  70.     return(c)
  73. def chi2(A):
  74.     ''' Compute the Chi-Square value '''   
  75.     m=len(A);
  76.     k=len(A[0])
  77.     R=[]
  78.     for i in range(m):
  79.         sum=0
  80.         for j in range(k):
  81.             sum+=A[i][j]
  82.         R.append(sum)
  83.     C=[]
  84.     for j in range(k):
  85.         sum=0
  86.         for i in range(m):
  87.             sum+=A[i][j]
  88.         C.append(sum)
  89.     N=0
  90.     for ele in C:
  91.         N+=ele
  92.     res=0
  93.     for i in range(m):
  94.         for j in range(k):
  95.             Eij=R[i]*C[j]/N
  96.             if Eij!=0:
  97.                 res=res+(A[i][j]-Eij)**2/Eij
  98.     return res
  101. def ChiMerge(log_tuple,max_interval):
  102.     ''' ChiMerge algorithm  '''
  103.     ''' Return split points '''    
  104.     num_interval=len(log_tuple)
  105.     while(num_interval>max_interval):               
  106.         num_pair=num_interval-1
  107.         chi_values=[]
  108.         for i in range(num_pair):
  109.             arr=[log_tuple[i][1],log_tuple[i+1][1]]
  110.             chi_values.append(chi2(arr))
  111.         min_chi=min(chi_values) # get the minimum chi value 
  112.         for i in range(num_pair-1,-1,-1): # treat from the last one
  113.             if chi_values[i]==min_chi:
  114.                 log_tuple[i]=combine(log_tuple[i],log_tuple[i+1]) # combine the two adjacent intervals
  115.                 log_tuple[i+1]='Merged'
  116.         while('Merged' in log_tuple): # remove the merged record
  117.             log_tuple.remove('Merged')
  118.         num_interval=len(log_tuple)
  119.     split_points=[record[0] for record in log_tuple]
  120.     return(split_points)
  123. def discrete(path):
  124.     ''' ChiMerege discretization of the Iris plants database '''
  125.     Instances=read(path)
  126.     max_interval=6
  127.     num_log=4
  128.     for i in range(num_log):
  129.         log_tuple=collect(Instances,i) # collect data for discretization
  130.         split_points=ChiMerge(log_tuple,max_interval) # discretize data using ChiMerge algorithm 
  131.         print(split_points)
  134. if __name__=='__main__':
  135.     print('Start: ' + ctime())
  136.     discrete('c:\\Python33\\iris.data')
  137.     print('End: ' + ctime())

获得的数据如下：

  1. ['4.3', '4.9', '5.0', '5.5', '5.8', '7.1']
  2. ['2.0', '2.3', '2.5', '2.9', '3.0', '3.4']
  3. ['1.0', '3.0', '4.5', '4.8', '5.0', '5.2']
  4. ['0.1', '1.0', '1.4', '1.7', '1.8', '1.9']
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注