梦翔儿学数据挖掘课时,做的一些题与答案,参考数目是韩家玮的数据挖掘教材.

1. 说明：为什么要进行数据预处理？数据预处理包括那些内容？

答：现实世界的数据库极易受噪声、丢失数据和不一致数据的侵扰，数据库往往是内容庞大，原始数据往往是不完整的，仅包含聚集数据，含躁声的，不一致的，来自异构数据源、低质量的。针对这样的数据进行处理，这也会导致低质量的挖掘结果。

数据预处理包括：数据清理、数据集成和数据变换、数据归约（泛化、离散化、概念分层处理等）

2. 请简要说明维归约的几种常用方法。

答：维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。如果原数据可以由压缩数据重新构造而不丢失任何信息，则该数据归约是无损的，如果我们只能构造原数据的看近似表示，则该数据归约是有损的。流行的有效的有损的维归约方法有小波变换和主成分分析。

（1）小波变换 离散小波变换（DWT），是一种线性信号处理技术，当用于数据向量X时，将它变换成的数值上不同的小波系数向量X’。两个向量具有相同的长度，当这种技术用于数据归约时，每个元组看作是一个n维数据向量，描述n个数据库属性在元组上的n个测量值。小波变换可以用于多维数据。详见书P49-50页。

（2）主要成分分析（PCA）：搜索K个最能代表数据的n维正交向量，其中K<<n。这样，原来的数据投影到一个小得多的空间，导致维度归约。其特点是计算开销低，可用于有序和无序的属性，并可以处理稀疏和倾斜数据。详见书：P51

3. 用Apriori算法，找出数据库D中最小支持数为2的3-频繁项目集。

数据库D

解：Apriori计算过程如下：

（1）扫描D，对每个侯选计数,C₁：

(2) 比较侯选支持度计数与最小支持度计数，因为支持度都大于2，所以得到,L₁

(3) 由L₁产生侯选C₂，并对每个侯选计数，得到：

(4) 比较侯选支持计数与最小支持度计数得到L₂：

(5) 由L₂产生侯选C₃

(6) 比较侯选支持度计数与最小支持度计数得，3频繁项集结果：

4. 给出数据库D的FP-树的构造过程，最小支持数为3。

数据库D

解：书P157

(1)先计算频繁项集：

(2) 比较侯选支持度计数与最小支持度计数，大于3的得到,L₁

（3）按递减支持度排序，得到L序列：

(4)扫描D来建树：

①T100按L中次序处理得到：T100:c, f, a, m,p

②T200按L中次序处理得到：T200:c, f, a,b, m

③T300按L中次序处理得到：T300: f, b

④T400按L中次序处理得到：T400:c,b,p

⑤T500按L中次序处理得到：T500:c, f, a, m,p

也就是最后得到的结果是：

5. 根据Y样本集合，利用朴素贝叶斯分类方法，确定测试样本X={A1=1, A2=2, A3=2}

Y样本集合为：

(1) 在类标号属性C具有两个不同值，即{1,2}

设C₁对就于类1，C₂对就于类2。

希望分类的元组X=｛A1=1，A2=2，A3=2｝。

(2) 需要最大化P(X|C_i)，i=1，2。每个类的先验概率P(C_i)可以根据训练元组计算：

P(C=1)=4/7=0.571

P(C=2)=3/7=0.429

(3) 为了计算P(X|C_i)，i=1，2，计算下面的条件概率

   P（A1=1|C=1）=2/4=0.5

   P（A1=1|C=2）=1/3=0.333

   P（A2=2|C=1）=1/4=0.25

   P（A2=2|C=2）=2/3=0.667

   P（A3=2|C=1）=1/4=0.25

   P（A3=2|C=2）=2/3=0.667

(4) 使用上面的概率得到：

   P（X|C=1）= P（A1=1|C=1）* P（A2=2|C=1）* P（A3=2|C=1）=0.5*0.25*0.25=0.03125

   P（X|C=2）= P（A1=1|C=2）* P（A2=2|C=2）* P（A3=2|C=2）=0.333*0.667*0.667=0.1481

(5) 为了发现最大化P(X|C_i)P(C_i)的类，计算

   P（X|C=1）P（C=1）=0.3125*0.571=0.0178

   P（X|C=2）P（C=2）=0.1481*0.429=0.0635

(6) 结论：对于元组X，朴素贝叶斯分类器预测元组X的类为C=2

6. 用K-均值方法将下面数据集（用8个(x，y)表示空间点）聚类为3个簇。

A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9)

注释：各点的距离函数可用欧几里德距离或曼哈坦距离。

用欧几里德距离求得：

******************************************************

A1，C2，B1为一组，其中心值为(3.7,9)

第1个分组内容为:

2,10

5,8

4,9

A2,C1为一组，其中心值为（7，17）

第2个分组内容为:

2,5

1,2

B2，A3，B3为一组，其中心值为（11.7,15.7）

第3个分组内容为:

8,4

7,5

6,4

******************************************************

使用Java完成的算法

KAverage.java

======

import java.io.BufferedReader;   
import java.io.FileNotFoundException;   
import java.io.FileReader;   
import java.io.IOException;   
  
public class KAverage {   
    private int sampleCount = 0;   
    private int dimensionCount = 0;   
    private int centerCount = 0;   
    private double[][] sampleValues;   
    private double[][] centers;   
    private double[][] tmpCenters;   
    private String dataFile = "";   
  
    /**  
     * 通过构造器传人数据文件  
     */  
    public KAverage(String dataFile) throws NumberInvalieException {   
        this.dataFile = dataFile;   
    }   
  
    /**  
     * 第一行为s;d;c含义分别为样例的数目，每个样例特征的维数，聚类中心个数 文件格式为d[,d]...;d[,d]... 如：1,2;2,3;1,5  
     * 每一维之间用,隔开，每个样例间用;隔开。结尾没有';' 可以有多行  
     */  
  
    private int initData(String fileName) {   
        String line;   
        String samplesValue[];   
        String dimensionsValue[] = new String[dimensionCount];   
        BufferedReader in;   
        try {   
            in = new BufferedReader(new FileReader(fileName));   
        } catch (FileNotFoundException e) {   
            e.printStackTrace();   
            return -1;   
        }   
        /*  
         * 预处理样本，允许后面几维为0时，不写入文件  
         */  
        for (int i = 0; i < sampleCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                sampleValues[i][j] = 0;   
            }   
        }   
  
        int i = 0;   
        double tmpValue = 0.0;   
        try {   
            line = in.readLine();   
            String params[] = line.split(";");   
            if (params.length != 3) {// 必须为3个参数，否则错误   
                return -1;   
            }   
            /**  
             * 获取参数  
             */  
            this.sampleCount = Integer.parseInt(params[0]);   
            this.dimensionCount = Integer.parseInt(params[1]);   
            this.centerCount = Integer.parseInt(params[2]);   
            if (sampleCount <= 0 || dimensionCount <= 0 || centerCount <= 0) {   
                throw new NumberInvalieException(line);   
            }   
            if (sampleCount < centerCount) {   
                throw new NumberInvalieException(line);   
            }   
  
            sampleValues = new double[sampleCount][dimensionCount + 1];   
            centers = new double[centerCount][dimensionCount];   
            tmpCenters = new double[centerCount][dimensionCount];   
  
            while ((line = in.readLine()) != null) {   
                samplesValue = line.split(";");   
                for (int j = 0; j < samplesValue.length; j++) {   
                    dimensionsValue = samplesValue[j].split(",");   
                    for (int k = 0; k < dimensionsValue.length; k++) {   
                        tmpValue = Double.parseDouble(dimensionsValue[k]);   
                        sampleValues[i][k] = tmpValue;   
                    }   
                    i++;   
                }   
            }   
  
        } catch (IOException e) {   
            e.printStackTrace();   
            return -2;   
        } catch (Exception e) {   
            e.printStackTrace();   
            return -3;   
        }   
        return 1;   
    }   
  
    /**  
     * 返回样本中第s1个和第s2个间的欧式距离  
     */  
    @SuppressWarnings("unused")
 private double getDistance(final int s1, final int s2) throws NumberInvalieException {   
        double distance = 0.0;   
        if (s1 < 0 || s1 >= sampleCount || s2 < 0 || s2 >= sampleCount) {   
            throw new NumberInvalieException(dataFile);   
        }   
        for (int i = 0; i < dimensionCount; i++) {   
            distance += (sampleValues[s1][i] - sampleValues[s2][i])   
                    * (sampleValues[s1][i] - sampleValues[s2][i]);   
        }   
        return distance;   
    }   
  
    /**  
     * 返回给定两个向量间的欧式距离  
     */  
    private double getDistance(double s1[], double s2[]) {   
        double distance = 0.0;   
        for (int i = 0; i < dimensionCount; i++) {   
            distance += (s1[i] - s2[i]) * (s1[i] - s2[i]); 
            //System.out.println(distance);
        }  

        return distance;   
    }   
  
    /**  
     * 更新样本中第s个样本的最近中心  
     */  
    private int getNearestCenter(int s) {   
        int center = 0;   
        double minDistance = Double.MAX_VALUE;   
        double distance = 0.0;   
        for (int i = 0; i < centerCount; i++) {   
            distance = getDistance(sampleValues[s], centers[i]);   
            if (distance < minDistance) {   
                minDistance = distance;   
                center = i;   
            }   
        }   
        sampleValues[s][dimensionCount] = center;
       //System.out.println(center);
        return center;   
    }   
  
    /**  
     * 更新所有中心  
     */  
    private void updateCenters() {   
        double center[] = new double[dimensionCount];   
        for (int i = 0; i < dimensionCount; i++) {   
            center[i] = 0;   
        }   
        int count = 0;   
        for (int i = 0; i < centerCount; i++) {   
            count = 0;   
            for (int j = 0; j < sampleCount; j++) {   
                if (sampleValues[j][dimensionCount] == i) {   
                    count++;   
                    for (int k = 0; k < dimensionCount; k++) {   
                        center[k] += sampleValues[j][k]; 
                    }   
                }   
            }   
            for (int j = 0; j < dimensionCount; j++) {   
                centers[i][j] = center[j] / count;
                System.out.println("i="+(i+1)+"centers="+centers[i][j]);
            }
        }   
    }   
  
    /**  
     * 判断算法是否终止  
     */  
    private boolean toBeContinued() {   
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                if (tmpCenters[i][j] != centers[i][j]) {   
                    return true;   
                }   
            }   
        }   
        return false;   
    }   
  
    /**  
     * 关键方法，调用其他方法，处理数据  
     */  
    public void doCaculate() {   
        initData(dataFile);   
  
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                centers[i][j] = sampleValues[i][j];   
            }   
        }   
        for (int i = 0; i < centerCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                tmpCenters[i][j] = 0;   
            }   
        }   
  
        while (toBeContinued()) {   
            for (int i = 0; i < sampleCount; i++) {   
                getNearestCenter(i);   
            }   
            for (int i = 0; i < centerCount; i++) {   
                for (int j = 0; j < dimensionCount; j++) {   
                    tmpCenters[i][j] = centers[i][j];   
                }   
            }   
            updateCenters();   
            System.out   
                    .println("******************************************************");   
            showResultData();   
        }   
    }   
  
    /*  
     * 显示数据  
     */  
    private void showSampleData() {   
        for (int i = 0; i < sampleCount; i++) {   
            for (int j = 0; j < dimensionCount; j++) {   
                if (j == 0) {   
                    System.out.print(sampleValues[i][j]);   
                } else {   
                    System.out.print("," + sampleValues[i][j]);   
                }   
            }   
            System.out.println();   
        }   
    }   
  
    /*  
     * 分组显示结果  
     */  
    private void showResultData() {   
        for (int i = 0; i < centerCount; i++) {   
            System.out.println("第" + (i + 1) + "个分组内容为:");   
            for (int j = 0; j < sampleCount; j++) {   
                if (sampleValues[j][dimensionCount] == i) {   
                    for (int k = 0; k <= dimensionCount; k++) {   
                        if (k == 0) {   
                            System.out.print(sampleValues[j][k]);   
                        } else {   
                            System.out.print("," + sampleValues[j][k]);   
                        }   
                    }   
                    System.out.println();   
                }   
            }   
        }   
    }   
  
    public static void main(String[] args) {   
        /*  
         *也可以通过命令行得到参数  
         */  
        String fileName = "D:\\sample.txt";   
        if(args.length > 0){   
            fileName = args[0];   
        }   
           
        try {   
            KAverage ka = new KAverage(fileName);   
            ka.doCaculate();   
            System.out   
                    .println("***************************<<result>>**************************");   
            ka.showResultData();   
        } catch (Exception e) {   
            e.printStackTrace();   
        }   
    }   
}

=======

NumberInvalieException.java

=======

/*  
 * 根据自己的需要定义一些异常，使得系统性更强  
 */  
public class NumberInvalieException extends Exception {   
    private String cause;   
       
    public NumberInvalieException(String cause){   
        if(cause == null || "".equals(cause)){   
            this.cause = "unknow";   
        }else{   
            this.cause = cause;   
        }   
    }   
    @Override  
    public String toString() {   
        return "Number Invalie!Cause by " + cause;   
    }   
}  

=========

数据集sample.txt

------
8;2;3
2,10;2,5;8,4;5,8;7,5;6,4;1,2;4,9;

==========

部分内容参考自教材与网络.