精华内容
下载资源
问答
  • k-means

    2011-12-29 17:36:45
    今天把自己写的一个机器学习算法库中的K-means算法整理了一下,因为这个算法较其他的相比相对独立,可以单独贴出来,不会引用太多的其他类(不过还是有点引用,不过引用些简单的功能,看类名就知道什么意思了)。...
    K-means聚类的java实现
    今天把自己写的一个机器学习算法库中的K-means算法整理了一下,因为这个算法较其他的相比相对独立,可以单独贴出来,不会引用太多的其他类(不过还是有点引用,不过引用些简单的功能,看类名就知道什么意思了)。
    基本功能和规则为:
    1.当然是进行k-means算法,对数据集(这里使用二维数组来表示数据集,行数为数据总数,列数为数据维度)进行N维聚类
    2.可以指定收敛的阀值(convergenceDis默认为0.0001)
    3.为避免局部最小,可以指定重复运行次数,通过设定replicates的数值来指定,默认为0,即只重复一次聚类过程
    4.测试数据格式为每一行代表一个输入,用空格分隔输入的各个维度,为了计算结果不出太大意外,建议对原始数据进行归一化
    首先上骨架代码:
    View Code


    Matrix
    package org.tadoo.ml;

    import java.io.PrintStream;

    import org.tadoo.ml.exception.MatrixComputeException;

    /**
    * 矩阵结构
    *
    * <p>time:2011-3-23</p>
    * @author T. QIN
    */
    public class Matrix
    {
    private int rowNum;

    private int colNum;

    private double value[][];

    /**
    * 构造器方法
    *
    * @param rows 行数
    * @param cols 列数
    * @see:
    * @author: T. QIN
    */
    public Matrix(int rows, int cols)
    {
    this.rowNum = rows;
    this.colNum = cols;
    this.value = new double[rows][cols];
    }

    /**
    * 构造器方法
    *
    * @param rows 行数
    * @param cols 列数
    * @param isInitialMemory 是否初始化权值矩阵
    * @see:
    * @author: T. QIN
    */
    public Matrix(int rows, int cols, boolean isInitialMemory)
    {
    this.rowNum = rows;
    this.colNum = cols;
    if (isInitialMemory)
    {
    this.value = new double[rows][cols];
    }
    }

    /**
    * 替换矩阵值
    *
    * @param v
    * @throws MatrixComputeException
    * @see:
    */
    public void changeWholeValue(double v[][]) throws MatrixComputeException
    {
    if (v.length != this.rowNum && v[0].length != this.colNum)
    {
    throw new MatrixComputeException("矩阵大小不拟合");
    }
    this.value = v;
    }

    public void print(PrintStream ps)
    {
    if (ps == null)
    {
    ps = System.out;
    }
    for (int i = 0; i < rowNum; i++)
    {
    for (int j = 0; j < colNum; j++)
    {
    ps.print(value[i][j] + "\t");
    }
    ps.println();
    }
    }

    /**
    * overwrite
    *
    * @return
    * @see:
    */
    public String toString()
    {
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < rowNum; i++)
    {
    for (int j = 0; j < colNum; j++)
    {
    sb.append(value[i][j] + "\t");
    }
    sb.append("\n");
    }
    return sb.toString();
    }

    /**
    * rowNum的 get() 方法
    * @return int rowNum.
    */
    public int getRowNum()
    {
    return rowNum;
    }

    /**
    * rowNum的 set() 方法
    * @param rowNum The rowNum to set.
    */
    public void setRowNum(int rowNum)
    {
    this.rowNum = rowNum;
    }

    /**
    * colNum的 get() 方法
    * @return int colNum.
    */
    public int getColNum()
    {
    return colNum;
    }

    /**
    * colNum的 set() 方法
    * @param colNum The colNum to set.
    */
    public void setColNum(int colNum)
    {
    this.colNum = colNum;
    }

    /**
    * value的 get() 方法
    * @return double[][] value.
    */
    public double[][] getValue()
    {
    return value;
    }

    /**
    * value的 set() 方法
    * @param value The value to set.
    */
    public void setValue(double[][] value)
    {
    this.value = value;
    }

    }
    复制代码
    MatrixComputeException

    按 Ctrl+C 复制代码
    DataUtil

    按 Ctrl+C 复制代码
    然后是测试:
    View Code
    package org.tadoo.ml.test;

    import junit.framework.TestCase;

    import org.tadoo.ml.Matrix;
    import org.tadoo.ml.cluster.kmeans.KmeansCluster;
    import org.tadoo.ml.util.DataUtil;
    import org.tadoo.ml.util.Utils;

    /**
    * 测试K-means聚类器
    *
    * <p>time:2011-6-2</p>
    * @author T. QIN
    */
    public class TestKmeansCluster extends TestCase
    {
    Matrix dataSet = null;

    double[][] ds = null;

    protected void setUp()
    {
    dataSet = Utils.uniformFileInputIntoFeatures("D:\\test.s.txt");
    ds = DataUtil.load("D:\\data1.txt");
    }

    /**
    * 测试用K-means选取中心节点
    *
    * @see:
    */
    public void testKmeansCenters()
    {
    KmeansCluster kmc = new KmeansCluster(dataSet.getValue(), 2);
    kmc.train();
    System.out.println(kmc.getTotalSumOfdistances());
    System.out.println(kmc.getIter());
    double[][] centers = kmc.getCenters();
    for (int i = 0; i < centers.length; i++)
    {
    for (int j = 0; j < centers[i].length; j++)
    {
    System.out.print(centers[i][j] + "\t");
    }
    System.out.println();
    }
    }

    public void testKmeansReplicate(){
    KmeansCluster kmc = new KmeansCluster(dataSet.getValue(), 11);
    kmc.setReplicates(12);
    kmc.train();
    KmeansCluster.KMCResult[] kmcr = kmc.getKmcresults();
    for (int i = 0; i < kmcr.length; i++)
    {
    System.out.println("iters:"+kmcr[i].iters+"\tSum:"+kmcr[i].sum);
    }
    }
    }

    http://www.cnblogs.com/tadoo/archive/2011/06/02/2068591.html
    因为是初学者,写的很冗长,不过多少能算出结果来了。
    展开全文
  • K-means聚类的java实现

    2011-06-02 15:47:00
    今天把自己写的一个机器学习算法库中的K-means算法整理了一下,因为这个算法较其他的相比相对独立,可以单独贴出来,不会引用太多的其他类(不过还是有点引用,不过引用些简单的功能,看类名就知道什么意思了)。...

          今天把自己写的一个机器学习算法库中的K-means算法整理了一下,因为这个算法较其他的相比相对独立,可以单独贴出来,不会引用太多的其他类(不过还是有点引用,不过引用些简单的功能,看类名就知道什么意思了)。

    基本功能和规则为:

    1.当然是进行k-means算法,对数据集(这里使用二维数组来表示数据集,行数为数据总数,列数为数据维度)进行N维聚类

    2.可以指定收敛的阀值(convergenceDis默认为0.0001)

    3.为避免局部最小,可以指定重复运行次数,通过设定replicates的数值来指定,默认为0,即只重复一次聚类过程

    4.测试数据格式为每一行代表一个输入,用空格分隔输入的各个维度,为了计算结果不出太大意外,建议对原始数据进行归一化

    首先上骨架代码:

    ContractedBlock.gifExpandedBlockStart.gifView Code
    package org.tadoo.ml.cluster.kmeans;

    import java.util.Random;

    import org.tadoo.ml.exception.ClusterException;
    import org.tadoo.ml.util.ArrayCompute;
    import org.tadoo.ml.util.Utils;

    /**
    * 使用K-means方法进行聚类
    *
    * <p>time:2011-6-1</p>
    *
    @author T. QIN
    */
    public class KmeansCluster
    {
    private double[][] dataSet = null;

    private int k = 0;

    private double[][] centers = null;

    private double totalSumOfdistances = 0;

    private boolean convergence = false;

    private int iter;

    private double convergenceDis = 0.0001;

    private int replicates = 0;

    private KMCResult[] kmcresults = null;

    public KmeansCluster(double[][] x, int k) throws ClusterException
    {
    if (x == null || x.length == 0)
    {
    throw new ClusterException("输入数据不可为空。");
    }
    this.dataSet = x;
    this.k = k;
    this.centers = new double[k][dataSet[0].length];
    }

    private void initKCenters()
    {
    Random r
    = new Random();
    int rn = r.nextInt(dataSet.length);
    for (int i = 0; i < this.k; i++)//初始化k个中心
    {
    for (int j = 0; j < dataSet[0].length; j++)
    {
    centers[i][j]
    = dataSet[rn][j];
    }
    rn
    = r.nextInt(dataSet.length);
    }
    }

    public void train()
    {
    if (replicates > 1)
    {
    kmcresults
    = new KMCResult[replicates];
    for (int i = 0; i < replicates; i++)
    {
    beginTrain();
    kmcresults[i]
    = new KMCResult();
    kmcresults[i].centers
    = this.centers;
    kmcresults[i].sum
    = this.totalSumOfdistances;
    kmcresults[i].iters
    = this.iter;
    this.centers = new double[k][dataSet[0].length];
    }
    }
    else
    {
    beginTrain();
    }
    }

    private void beginTrain()
    {
    int rows = dataSet.length;
    int cols = dataSet[0].length;
    int[] c = new int[rows];//保存每个数据属于哪个中心
    int vote = 0;//如果某一中心收敛,则投票数可加一
    iter = 0;
    initKCenters();
    convergence
    = false;
    while (!convergence)
    {
    double minDistance = Double.MAX_VALUE;
    double currentDis = 0.0;
    int count = 0;
    int changedCenterNumber = 0;
    double[] temp = new double[cols];
    totalSumOfdistances
    = 0;
    for (int i = 0; i < rows; i++)
    {
    for (int j = 0; j < this.k; j++)
    {
    currentDis
    = Utils.distance(dataSet[i], centers[j]);
    if (currentDis < minDistance)
    {
    minDistance
    = currentDis;
    c[i]
    = j;
    }
    }
    totalSumOfdistances
    += minDistance;
    minDistance
    = Double.MAX_VALUE;
    }
    for (int i = 0; i < this.k; i++)
    {
    for (int j = 0; j < c.length; j++)
    {
    if (c[j] == i)
    {
    temp
    = Utils.add(temp, dataSet[j]);
    count
    ++;
    }
    }
    if (count != 0)
    {
    temp
    = ArrayCompute.devideC(temp, count);
    if (isCenterConvergence(centers[i], temp))
    {
    vote
    ++;
    }
    centers[i]
    = temp;
    changedCenterNumber
    ++;
    }
    count
    = 0;

    temp
    = new double[cols];
    }
    iter
    ++;
    if (vote == changedCenterNumber)
    {
    convergence
    = true;
    }
    vote
    = 0;
    changedCenterNumber
    = 0;
    }
    }

    /**
    * 判断某中心是否收敛
    *
    *
    @param center
    *
    @param pCenter
    *
    @return
    *
    @see:
    */
    private boolean isCenterConvergence(double[] center, double[] pCenter)
    {
    boolean result = true;
    double[] distance = ArrayCompute.minus(center, pCenter);
    for (int i = 0; i < distance.length; i++)
    {
    if (Math.abs(distance[i]) > convergenceDis)
    {
    result
    = false;
    }
    }
    return result;
    }

    /**
    * dataSet的 get() 方法
    *
    @return double[][] dataSet.
    */
    public double[][] getDataSet()
    {
    return dataSet;
    }

    /**
    * dataSet的 set() 方法
    *
    @param dataSet The dataSet to set.
    */
    public void setDataSet(double[][] dataSet)
    {
    this.dataSet = dataSet;
    }

    /**
    * k的 get() 方法
    *
    @return int k.
    */
    public int getK()
    {
    return k;
    }

    /**
    * k的 set() 方法
    *
    @param k The k to set.
    */
    public void setK(int k)
    {
    this.k = k;
    }

    /**
    * centers的 get() 方法
    *
    @return double[][] centers.
    */
    public double[][] getCenters()
    {
    return centers;
    }

    /**
    * centers的 set() 方法
    *
    @param centers The centers to set.
    */
    public void setCenters(double[][] centers)
    {
    this.centers = centers;
    }

    /**
    * totalSumOfdistances的 get() 方法
    *
    @return double totalSumOfdistances.
    */
    public double getTotalSumOfdistances()
    {
    return totalSumOfdistances;
    }

    /**
    * totalSumOfdistances的 set() 方法
    *
    @param totalSumOfdistances The totalSumOfdistances to set.
    */
    public void setTotalSumOfdistances(double totalSumOfdistances)
    {
    this.totalSumOfdistances = totalSumOfdistances;
    }

    /**
    * iter的 get() 方法
    *
    @return int iter.
    */
    public int getIter()
    {
    return iter;
    }

    /**
    * convergenceDis的 get() 方法
    *
    @return double convergenceDis.
    */
    public double getConvergenceDis()
    {
    return convergenceDis;
    }

    /**
    * convergenceDis的 set() 方法
    *
    @param convergenceDis The convergenceDis to set.
    */
    public void setConvergenceDis(double convergenceDis)
    {
    this.convergenceDis = convergenceDis;
    }

    /**
    * replicates的 get() 方法
    *
    @return int replicates.
    */
    public int getReplicates()
    {
    return replicates;
    }

    /**
    * replicates的 set() 方法
    *
    @param replicates The replicates to set.
    */
    public void setReplicates(int replicates)
    {
    this.replicates = replicates;
    }



    /**
    * kmcresults的 get() 方法
    *
    @return KMCResult[] kmcresults.
    */
    public KMCResult[] getKmcresults()
    {
    return kmcresults;
    }

    /**
    * kmcresults的 set() 方法
    *
    @param kmcresults The kmcresults to set.
    */
    public void setKmcresults(KMCResult[] kmcresults)
    {
    this.kmcresults = kmcresults;
    }



    /**
    * 聚类运行的结果
    *
    * <p>time:2011-6-2</p>
    *
    @author T. QIN
    */
    public class KMCResult
    {
    public double[][] centers;

    public double sum;

    public int iters;
    }
    }
    然后相关类:
    ContractedBlock.gifExpandedBlockStart.gifView Code
    package org.tadoo.ml.exception;

    /**
    * 聚类异常
    *
    * <p>time:2011-5-25</p>
    *
    @author T. QIN
    */
    public class ClusterException extends RuntimeException
    {
    public ClusterException()
    {
    super();
    }

    public ClusterException(String s)
    {
    super(s);
    }
    }
    ContractedBlock.gifExpandedBlockStart.gifView Code
    package org.tadoo.ml.util;

    /**
    * 简单数组计算
    *
    * <p>time:2011-5-27</p>
    *
    @author T. QIN
    */
    public class ArrayCompute
    {
    /**
    * 数组相加
    *
    *
    @param x1
    *
    @param x2
    *
    @return
    *
    @see:
    */
    public static double[] add(final double[] x1, final double[] x2)
    {
    if (x1.length != x2.length)
    {
    System.err.print(
    "向量长度不等不能相加!");
    System.exit(
    0);
    }
    double[] result = new double[x1.length];
    for (int i = 0; i < result.length; i++)
    {
    result[i]
    = x1[i] + x2[i];
    }
    return result;
    }

    /**
    * 数组相减
    *
    *
    @param x1
    *
    @param x2
    *
    @return
    *
    @see:
    */
    public static double[] minus(final double[] x1, final double[] x2)
    {
    if (x1.length != x2.length)
    {
    System.err.print(
    "向量长度不等不能相减!");
    System.exit(
    0);
    }
    double[] result = new double[x1.length];
    for (int i = 0; i < result.length; i++)
    {
    result[i]
    = x1[i] - x2[i];
    }
    return result;
    }

    /**
    * 数组乘以一个常数
    *
    *
    @param x1
    *
    @param c
    *
    @return
    *
    @see:
    */
    public static double[] multiplyC(final double[] x1, final double c)
    {
    double[] ret = new double[x1.length];
    for (int i = 0; i < x1.length; i++)
    {
    ret[i]
    = x1[i] * c;
    }
    return ret;
    }

    /**
    * 数组除以一个常数
    *
    *
    @param x1
    *
    @param c
    *
    @return
    *
    @see:
    */
    public static double[] devideC(final double[] x1, final double c)
    {
    double[] ret = new double[x1.length];
    for (int i = 0; i < x1.length; i++)
    {
    ret[i]
    = x1[i] / c;
    }
    return ret;
    }
    }
    ContractedBlock.gifExpandedBlockStart.gifView Code
    package org.tadoo.ml.util;

    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.StringTokenizer;

    import org.tadoo.ml.Matrix;

    /**
    *
    *
    * <p>time:2011-3-23</p>
    *
    @author T. QIN
    */
    /**
    *
    *
    * <p>time:2011-3-28</p>
    *
    @author T. QIN
    */
    public class Utils
    {

    /**
    * 计算两个点之间的欧几里德距离
    *
    *
    @param x1
    *
    @param x2
    *
    @return
    *
    @see:
    */
    public static double distance(double[] x1, double[] x2)
    {
    double r = 0.0;
    for (int i = 0; i < x1.length; i++)
    {
    r
    += Math.pow(x1[i] - x2[i], 2);
    }
    return Math.sqrt(r);
    }

    /**
    * 数组相加
    *
    *
    @param x1
    *
    @param x2
    *
    @return
    *
    @see:
    */
    public static double[] add(final double[] x1, final double[] x2)
    {
    if (x1.length != x2.length)
    {
    System.err.print(
    "向量长度不等不能相加!");
    System.exit(
    0);
    }
    double[] result = new double[x1.length];
    for (int i = 0; i < result.length; i++)
    {
    result[i]
    = x1[i] + x2[i];
    }
    return result;
    }
    }
    ContractedBlock.gifExpandedBlockStart.gifMatrix
    package org.tadoo.ml;

    import java.io.PrintStream;

    import org.tadoo.ml.exception.MatrixComputeException;

    /**
    * 矩阵结构
    *
    * <p>time:2011-3-23</p>
    *
    @author T. QIN
    */
    public class Matrix
    {
    private int rowNum;

    private int colNum;

    private double value[][];

    /**
    * 构造器方法
    *
    *
    @param rows 行数
    *
    @param cols 列数
    *
    @see:
    *
    @author: T. QIN
    */
    public Matrix(int rows, int cols)
    {
    this.rowNum = rows;
    this.colNum = cols;
    this.value = new double[rows][cols];
    }

    /**
    * 构造器方法
    *
    *
    @param rows 行数
    *
    @param cols 列数
    *
    @param isInitialMemory 是否初始化权值矩阵
    *
    @see:
    *
    @author: T. QIN
    */
    public Matrix(int rows, int cols, boolean isInitialMemory)
    {
    this.rowNum = rows;
    this.colNum = cols;
    if (isInitialMemory)
    {
    this.value = new double[rows][cols];
    }
    }

    /**
    * 替换矩阵值
    *
    *
    @param v
    *
    @throws MatrixComputeException
    *
    @see:
    */
    public void changeWholeValue(double v[][]) throws MatrixComputeException
    {
    if (v.length != this.rowNum && v[0].length != this.colNum)
    {
    throw new MatrixComputeException("矩阵大小不拟合");
    }
    this.value = v;
    }

    public void print(PrintStream ps)
    {
    if (ps == null)
    {
    ps
    = System.out;
    }
    for (int i = 0; i < rowNum; i++)
    {
    for (int j = 0; j < colNum; j++)
    {
    ps.print(value[i][j]
    + "\t");
    }
    ps.println();
    }
    }

    /**
    * overwrite
    *
    *
    @return
    *
    @see:
    */
    public String toString()
    {
    StringBuffer sb
    = new StringBuffer();
    for (int i = 0; i < rowNum; i++)
    {
    for (int j = 0; j < colNum; j++)
    {
    sb.append(value[i][j]
    + "\t");
    }
    sb.append(
    "\n");
    }
    return sb.toString();
    }

    /**
    * rowNum的 get() 方法
    *
    @return int rowNum.
    */
    public int getRowNum()
    {
    return rowNum;
    }

    /**
    * rowNum的 set() 方法
    *
    @param rowNum The rowNum to set.
    */
    public void setRowNum(int rowNum)
    {
    this.rowNum = rowNum;
    }

    /**
    * colNum的 get() 方法
    *
    @return int colNum.
    */
    public int getColNum()
    {
    return colNum;
    }

    /**
    * colNum的 set() 方法
    *
    @param colNum The colNum to set.
    */
    public void setColNum(int colNum)
    {
    this.colNum = colNum;
    }

    /**
    * value的 get() 方法
    *
    @return double[][] value.
    */
    public double[][] getValue()
    {
    return value;
    }

    /**
    * value的 set() 方法
    *
    @param value The value to set.
    */
    public void setValue(double[][] value)
    {
    this.value = value;
    }

    }
    ContractedBlock.gifExpandedBlockStart.gifMatrixComputeException
    package org.tadoo.ml.exception;

    /**
    *
    *
    * <p>time:2011-3-23</p>
    *
    @author T. QIN
    */
    public class MatrixComputeException extends Exception
    {
    public MatrixComputeException(String s)
    {
    super(s);
    }
    }
    ContractedBlock.gifExpandedBlockStart.gifDataUtil
    package org.tadoo.ml.util;

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    /**
    * 加载文件中的数据
    *
    * <p>time:2011-5-31</p>
    *
    @author T. QIN
    */
    public class DataUtil
    {
    /**
    * 加载数据
    *
    *
    @param filePath
    *
    @return
    *
    @see:
    */
    public static double[][] load(String filePath)
    {
    BufferedReader reader
    = null;
    List
    <String[]> container = new ArrayList<String[]>();
    String line
    = null;
    double[][] result = null;
    int xs, ys = 0;
    try
    {
    reader
    = new BufferedReader(new FileReader(new File(filePath)));
    while ((line = reader.readLine()) != null)
    {
    String temp[]
    = line.trim().split("[\\s]+");
    container.add(temp);
    }
    xs
    = (((String[]) container.get(0)).length);
    ys
    = container.size(); //数据条目
    result = new double[ys][xs];
    String[] strings
    = null;
    for (int i = 0, n = container.size(); i < n; i++)
    {
    strings
    = (String[]) container.get(i);
    for (int j = 0; j < strings.length; j++)
    {
    result[i][j]
    = Double.parseDouble(strings[j]);
    }
    }
    }
    catch (FileNotFoundException e)
    {
    e.printStackTrace();
    }
    catch (IOException e)
    {
    e.printStackTrace();
    }
    return result;
    }

    //TODO:
    /**
    * 输出数据到文件,可选择某几列属性
    *
    *
    @param data
    *
    @param saveFilename
    *
    @param columns
    *
    @see:
    */
    public static void save(double[][] data, String saveFilename, int[] columns)
    {
    BufferedWriter fp_saver
    = null;
    Arrays.sort(columns);
    try
    {
    fp_saver
    = new BufferedWriter(new FileWriter(saveFilename));
    for (int i = 0; i < data.length; i++)
    {
    for (int j = 0; j < columns.length; j++)
    {
    fp_saver.write(String.valueOf(data[i][columns[j]])
    + " ");
    }
    fp_saver.write(
    "\n");
    }
    fp_saver.flush();
    }
    catch (IOException e)
    {
    e.printStackTrace();
    }
    finally
    {
    try
    {
    fp_saver.close();
    }
    catch (IOException e)
    {
    e.printStackTrace();
    }
    }
    }
    }

    然后是测试:

    ContractedBlock.gifExpandedBlockStart.gifView Code
    package org.tadoo.ml.test;

    import junit.framework.TestCase;

    import org.tadoo.ml.Matrix;
    import org.tadoo.ml.cluster.kmeans.KmeansCluster;
    import org.tadoo.ml.util.DataUtil;
    import org.tadoo.ml.util.Utils;

    /**
    * 测试K-means聚类器
    *
    * <p>time:2011-6-2</p>
    *
    @author T. QIN
    */
    public class TestKmeansCluster extends TestCase
    {
    Matrix dataSet
    = null;

    double[][] ds = null;

    protected void setUp()
    {
    dataSet
    = Utils.uniformFileInputIntoFeatures("D:\\test.s.txt");
    ds
    = DataUtil.load("D:\\data1.txt");
    }

    /**
    * 测试用K-means选取中心节点
    *
    *
    @see:
    */
    public void testKmeansCenters()
    {
    KmeansCluster kmc
    = new KmeansCluster(dataSet.getValue(), 2);
    kmc.train();
    System.out.println(kmc.getTotalSumOfdistances());
    System.out.println(kmc.getIter());
    double[][] centers = kmc.getCenters();
    for (int i = 0; i < centers.length; i++)
    {
    for (int j = 0; j < centers[i].length; j++)
    {
    System.out.print(centers[i][j]
    + "\t");
    }
    System.out.println();
    }
    }

    public void testKmeansReplicate(){
    KmeansCluster kmc
    = new KmeansCluster(dataSet.getValue(), 11);
    kmc.setReplicates(
    12);
    kmc.train();
    KmeansCluster.KMCResult[] kmcr
    = kmc.getKmcresults();
    for (int i = 0; i < kmcr.length; i++)
    {
    System.out.println(
    "iters:"+kmcr[i].iters+"\tSum:"+kmcr[i].sum);
    }
    }
    }
    因为是初学者,写的很冗长,不过多少能算出结果来了。

    转载于:https://www.cnblogs.com/tadoo/archive/2011/06/02/2068591.html

    展开全文
  • 一开始真的没懂题目什么意思,还以为要连续的子串,结果发现时序列,简直智障,知道题意之后,好久没搞LIS,有点忘了,复习一波以后,直接双向LIS,处理处两个数组L和R,然后对整个数组扫一遍对于每一个下标取m=...

    以下题目均自己搜

    F题  A序列

    一开始真的没懂题目什么意思,还以为是要连续的子串,结果发现时序列,简直智障,知道题意之后,好久没搞LIS,有点忘了,复习一波以后,直接双向LIS,处理处两个数组L和R,然后对整个数组扫一遍对于每一个下标取m=min(L[i],R[i]);用ans取2*m-1中的最大值。LIS用nlogn的算法实现,二分用的是lower_bound(),直接看代码。

    //Author: xiaowuga
    #include <bits/stdc++.h>
    #define maxx INT_MAX
    #define minn INT_MIN
    #define inf 0x3f3f3f3f
    const long long N=500003; 
    using namespace std;
    typedef long long LL;
    int dp[N];
    int L[N],R[N];
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);
        int n;
        int a[N];
        while(cin>>n){
            for(int i=0;i<n;i++){
                cin>>a[i];
            }
            memset(dp,inf,sizeof(dp));
            for(int i=0;i<n;i++){
                int pos=lower_bound(dp,dp+n,a[i])-dp;
                dp[pos]=a[i]; 
                L[i]=pos+1;
            }
           
            memset(dp,inf,sizeof(dp));
            for(int i=n-1;i>=0;i--){
                int pos=lower_bound(dp,dp+n,a[i])-dp;
                dp[pos]=a[i];
                R[i]=pos+1;
            }
             for(int i=0;i<n;i++) cout<<L[i]<<" "; cout<<endl;
              for(int i=0;i<n;i++) cout<<R[i]<<" "; cout<<endl;
            int ans=minn;
            int tmp;
            for(int i=0;i<n;i++){
                int tmp=min(L[i],R[i]);
                ans=max(tmp*2-1,ans);
            }
            cout<<ans<<endl;
        }
        return 0;
    }

     

    G题 战斗

    暴力阶乘题,因为n<10,所以暴力枚举全排列所有的出战顺序,然后模拟和电脑去打就好了,复杂度n*n!。不要真的老实的的每一次攻击的去模拟,万一两个两个怪兽都是1000的血1的攻击力,一次枚举,十个怪兽就是10000的计算计算量,而你的枚举量可能高达10!三百多万啊,绝逼超时GG,所以直接除找到每组对战的怪兽需要各自攻击对方几次才会死,然后取最小值,将hp减去攻击次数*攻击力,得到怪兽战后的状态,对于hp<=0的我们就换人。还有不要确切的计算具体要攻击多少次,因为有的时候比如你是9的hp,5的五的攻击力,9/5=1,实际上要攻击两次才会死攻击次数是hp/at+1。然后如果双方的hp变成10,10/5=2,刚好死亡攻击次数恰好是hp/at,这个时候如果用%取判断了话,是会超时的,因为%与运算是比较慢的。所以我们用一个while循环,模拟最后一次攻击,将会比算出这个具体的攻击次数速度要快。这就是我为什么一开始超时的原因,还有一个优化就是要枚举的时候都要复制一遍双方的怪兽信息,因为只有当前的怪兽有用,所以我们用一个值来存就好了,如果你用结构体,每次就有一个攻击实际上不用复制但是复制了,实际上浪费了时间,面对10!的枚举量,也会慢很多,然后就是边打边复制,这样有的时候电脑其实一只怪兽就团灭你了,但是你却多复制了其他怪兽同样浪费时间。

    最后还有一个逆天优化:就是我们每次记住上一次枚举出场的顺序,如果电脑两只怪兽就把你团灭了,那么如果你下一次枚举前两只怪兽出场顺序没有发生改变,那么电脑还是可以用两只怪兽把你团灭,无论你后面的怪兽如何出出站,压倒性的实力。这样的枚举是无用的,如果对他的战斗进行模拟,又会有大量的复制会是无用功,而且对于字典序全排列,大多数的枚举的前几位都和上一次枚举基本是一样的。这就给我们启发,使我们可以快速的跳过一下无用的枚举,将n*n!的复杂度,优化成n!,加快了近十倍的速度。大概只需要100ms就可以ac,当然后还有2^n复杂度的做法,那个就更快了,需要用到状态压缩dp,本人目前不会。

    //Author: xiaowuga
    #include <bits/stdc++.h>
    #define maxx INT_MAX
    #define minn INT_MIN
    #define inf 0x3f3f3f3f
    const long long N=11; 
    using namespace std;
    typedef long long L;
    struct M{
        int at,hp,pos;
        bool operator <(const M &m) const{
            return at<m.at;
        }
    }me[N],co[N];
    M cm[N],mm[N];
    int main() {
        int T,n;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            for(int i=0;i<n;i++) scanf("%d%d",&co[i].hp,&co[i].at);
            for(int i=0;i<n;i++) {scanf("%d%d",&me[i].hp,&me[i].at);}
            int flag=0,flag2=0;
            int c1=0,c2=0,m;
            sort(me,me+n);
            do{
                if(flag2){
                    if(c1==0) break;
                    else{
                        int ifsame=1;
                        for(int i=0;i<=c1;i++){
                            if(me[i].at!=mm[i].at) {ifsame=0;break;}
                        }
                        if(ifsame) continue;
                     }
                }
                flag2=1;
                c1=0;c2=0;
                cm[0]=co[0]; mm[0]=me[0];
                while(c1<n&&c2<n){
                    m=min(cm[c1].hp/mm[c2].at,mm[c2].hp/cm[c1].at);
                    cm[c1].hp-=m*mm[c2].at;
                    mm[c2].hp-=m*cm[c1].at;
                    while(cm[c1].hp>0&&mm[c2].hp>0){
                        cm[c1].hp-=mm[c2].at;
                        mm[c2].hp-=cm[c1].at;
                    }
                    if(cm[c1].hp<=0) {c1++;cm[c1]=co[c1];}
                    if(mm[c2].hp<=0) {c2++;mm[c2]=me[c2];}
                }
                if(c1==n&&c2<n) {flag=1;break;}
            }while(next_permutation(me,me+n));
            if(flag) printf("YES\n");
            else printf("NO\n");    
        }
        return 0;
    }

     

    I题   丢史蒂芬妮

    博弈xjb搜题,博弈论知识不好,别人告诉我怎么搜的。xjb搜了一波,就过了,不是特别理解。直接代码吧!

    //Author: xiaowuga
    #include<cstdio>
    #define maxx INT_MAX
    #define minn INT_MIN
    #define inf 0x3f3f3f3f
    const long long N=505; 
    using namespace std;
    typedef long long L;
    int vis1[N]={0};
    int num=0;
    int primnum_list[N];
    void make_primnum(){
        for(int i=2;i<N/2;i++)
            for(int j=2*i;j<N;j+=i){
                vis1[j]=1;
            }
        for(int i=2;i<N;i++){
            if(vis1[i]==0) primnum_list[num++]=i;
        } 
    }
    int mat[N][N]={0},vis[N][N]={0};
    int dfs(int x,int y){
        if(vis[x][y]) return mat[x][y];
        vis[x][y]=1;
        for(int i=0;i<num;i++){
            int t=primnum_list[i];
            if(x-t>0) mat[x][y] |=!(dfs(x-t,y));
            if(y>t>0) mat[x][y] |=!(dfs(x,y-t));
            if(x-t>0&&y-t>0) mat[x][y] |=!(dfs(x-t,y-t));
        }
        return mat[x][y];
    }
    int main() {
        make_primnum();
        for(int i=1;i<=500;i++)
           for(int j=1;j<=500;j++){
                mat[i][j]=dfs(i,j);
           }
        int T;
        scanf("%d",&T);
       while(T--){
            int n,m;
            scanf("%d%d",&n,&m);
            if(mat[n][m]) printf("Sora\n");
            else printf("Shiro\n");
       } 
        return 0;
    }

     

    K题   购买装备

    第一眼尼玛不是一个背包dp吗?还是0-1背包,结果native了,10000的物品,一亿的预算,背包的复杂度更本跑不出来,所以我们采用贪心的思路。

    我们首先要把问题分开去思考,这样有助于我们思考,而不会因为问题整体比较比较复杂,从而在思考上停滞不前,应该要把什么是主要问题什么是次要问题搞懂,题目中次要问题,是在主要问题的限制之下,也就是在购买尽量多的物品的情况下,物品中属性最小的值尽量大。首先是购买尽量多的物品,由于每个物品只能买一次,所以买便宜的物品,剩下的钱更多,也就可以买更多的物品,所以贪心对价格排序得到最大可以购买的数量m,但是这不一定是最小属性最大的。所以我们接着看后半部分的问题,问题就变成了在n个物品里面选m个其中属性最小的的物品的值要尽量大,标准的最小值最大化的套路。对属性排序,二分枚举属性,在大于等于当前枚举的最小属性中,对价格排序取 前m个,判断是否小于等于预算,这个是学长的做法,我也想过。但是每次复制一遍再排序,所以觉得没可行,所以没敢试。谁知学长用了特殊姿势。用了nth_element()这个库函数,使用m次,直接排序复杂度nlogn,减去复制的过程防止复杂度上升到n^2logn,从而使复杂度变为nlognlogn,这个复杂度可以满足题目的数据量。但是我想到是另一个种方法,前面和学长一样得到m的最大购买数量,然后对属性排序(从大到小),取前m个元素判断是否满足预算(枚举下标为m-1的元素为最小属性),不满足则枚举下标为m的元素为最小属性,从前m+1个元素里取m个最便宜的看一下,是否满足预算,不满足再次往后枚举,直到满足要求,我也需要复制一遍再排序,然而我想到用优先队列优化,建立一个大小为m的优先队列,计算一个堆的价格总和,然后每次枚举我们把堆顶元素pop,将枚举的元素插入,计算总价格的改变值,判断是否满足要求,直到满足要求位置。由于删除和插入的操作复杂度都是logn,所以总体的复杂度是nlogn,以下是我的代码

    //Author: xiaowuga
    #include <bits/stdc++.h>
    #define maxx INT_MAX
    #define minn INT_MIN
    #define inf 0x3f3f3f3f
    const long long N= 1e5+10;
    using namespace std;
    typedef long long L;
    priority_queue<long long, vector<long long>,less<long long> >q;
    struct equip{
        long long a,b;
    }oj[N];
    bool cmp1(equip x,equip y){
        return x.b<y.b;
    }
    bool cmp2(equip x,equip y){
        return x.a>y.a;
    }
    int main() {
        long long T,n,m;
        scanf("%lld",&T);
        while(T--){
            scanf("%lld%lld",&n,&m);
            for(int i=0;i<n;i++) scanf("%lld%lld",&oj[i].a,&oj[i].b);
            sort(oj,oj+n,cmp1);
            long long sum=0,k=0;
            for(int i=0;i<n;i++){
                if(sum+oj[i].b<=m){sum+=oj[i].b;k++;}
                else break;
            }
            sort(oj,oj+n,cmp2);
            sum=0;
            while(!q.empty()) q.pop();
            for(int i=0;i<k;i++){
                q.push(oj[i].b);
                sum+=oj[i].b;
            }
            if(sum<=m) {printf("%lld %lld\n",k,oj[k-1].a);continue;}
            for(int i=k;i<n;i++){
                sum=sum-q.top()+oj[i].b;
                if(sum<=m){ printf("%lld %lld\n",k,oj[i].a); break; }
                q.pop();q.push(oj[i].b);
            }
        } 
        return 0;
    }

     

    J题   膜一下将带给你好运

    我一开始还以为这个题很难,没想到一个暴力题。抱歉本人太菜了。暴力打表找规律发现规律,正经的做法估计估计得是数论高玩才整的出来。找出规律∑phi(i)*(n/i)(1<=i<=n)的答案是n*(n+1)/2,然后欧拉1到232和n-232到n的phi(i)*(n/i),用欧拉函数的定力暴力算。也就是464个,算每个欧拉函数的复杂度是logn。在除2的地方需要使用乘法逆元,利用费马小定理求出逆元,有的人没用乘法逆元就A了,只能说可能数据比较水吧。这里多说一句,使用乘法逆元的时候先先求出n*(n+1)%mod的的答案。然后用这个答案利用乘法逆元算出除2取膜以后的答案。直接在一个算数表达式里面直接都算出来就会出错。原因不知道,反正因此wa了几次,怀疑是这个原因,改了一下就过了。直接看代码吧!

    //Author: xiaowuga
    #include <bits/stdc++.h>
    #define maxx INT_MAX
    #define minn INT_MIN
    #define inf 0x3f3f3f3f
    const long long N=100000; 
    using namespace std;
    typedef long long LL;
    const long long mod=1e9+7;
    LL q_power(LL a,LL k){
        LL ans=1;
        while(k){
           if(k%2){ ans=ans*a%mod;}
           k/=2;
           a=a*a%mod; 
        }
        return ans;
    }
    LL euler(LL n){
        LL res=n;
        for(LL i=2;i*i<=n;i++){
            if(n%i==0){
                res=res/i*(i-1);
                while(n%i==0) n/=i;
            }
        }
        if(n>1)   res=res/n*(n-1);
        return res;
    }
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);
        LL nCase;
        cin>>nCase;
        LL n,ans;
        while(nCase--){
            cin>>n;
            ans=n*(n+1)%mod;
            ans=ans*q_power(2,mod-2)%mod;
            for(LL i=1;i<=232;i++){
                 ans=(ans-euler(i)*(n/i)+mod)%mod;
            }
            for(LL i=n;i>=n-232;i--){
                ans=(ans-euler(i)*(n/i)+mod)%mod;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

     

    继续补题,这个随笔将会在最近持续更新,尽量把金马五校的题补完吧!!!

    转载于:https://www.cnblogs.com/xiaowuga/p/7163421.html

    展开全文
  • </li><li>这个项目带给你的成长是什么,当然别说让我学会了某某 API 这种没价值的内容。</li></ol> 另外项目这块还要结合着简历来说,因为面试官问你项目肯定是从简历上得来的问题,下文中会写到...
  • 要把水分要炸干 这声音有点脆了啊 <p>26 00:01:11,360 --> 00:01:13,200 您看这个蒜已经金黄了 <p>27 00:01:13,200 --> 00:01:15,400 我觉得应该可以捞了 <p>28 00:01:16,400 --> 00:01:19,200 然后咱们...
  • 记一次Navicat安装

    2021-06-08 20:20:54
    和下图有点类似,那这个K'ed by TNT team是什么意思呢? 网络搜索如下 TNT team据传是一个俄罗斯的破解团队: 在Mac破解软件里经常会看到这样的字样,K’ed by TNT team. K’ed是cracked的缩写,cracked即破解后的...

    Previously:

    mac从网上下载Navicat并安装


    启动Navicat点击Help查看:

    原本下图中,Help信息有K'ed by TNT team字样,但是现在没有了

    和下图有点类似,那这个K'ed by TNT team是什么意思呢?

    网络搜索如下


    TNT team据传是一个俄罗斯的破解团队:

    在Mac破解软件里经常会看到这样的字样,K’ed by TNT team.

    K’ed是cracked的缩写,cracked即破解后的。
    TNT team据传是一个俄罗斯的破解团队,专门破解mac软件的签名许可证之类类。


    资源发布?

      这个团队的资源发布在哪呢?
      据说是以下几个网址:
      https://inmac.org/
      https://cmacapps.com/
      https://mac-torrent-download.net/
    
      国内门户搬运他们的破解软件,所以经常会看到如题字样。inmac.org还是一个邀请制的网站,可见TNT团队也是相当神秘。
    
    
    
    
    
    
    
    
    
    

    参考链接

    https://www.cnblogs.com/chester-cs/p/11776571.html
    参考链接
    https://www.zhihu.com/question/319316132
    俄文网站
    https://www.appstorrent.ru/programs
    

    写在最后

    安装软件时出现,软件已损坏,打不开,应该删除。

    注意:网上很多解决方法都说,到,系统设置,偏好设置,安全与隐私,设置,允许下载app任何来源!但是仍未解决。
    参考解决:已损坏,无法打开,您应该将它移到废纸篓
    在这里插入图片描述

    可通过在终端中输入命令 sudo xattr -d com.apple.quarantine /Applications/xxx.app解决,其中xxx.app是出问题的APP名称,如名称中有空格,可用“\”加空格代替。
    在这里插入图片描述

    sudo xattr -d com.apple.quarantine /Applications/Navicat\ Premium.app
    
    参考链接:https://cloud.tencent.com/developer/article/1657232
    
    展开全文
  • KNN算法思路以及常见面试题

    千次阅读 2020-06-02 14:05:55
    一.KNN算法概述 KNN可以说是最简单的分类算法之一,同时,它也是最常用...其实啊,KNN的原理就是当预测一个新的值x的时候,根据它距离最近的K个点是什么类别来判断x属于哪个类别。 如下图,k=3时候,绿色x判定为蓝色。
  • 一、KNN算法概述 ...KNN的全称是K Nearest Neighbors,意思是K个最近的邻居,从这个名字我们就能看出一些KNN算法的蛛丝马迹了。K个最近邻居,毫无疑问,K的取值肯定至关重要的。那么最近的邻居又怎么回事呢
  • 到底是什么意思?举个栗子,<code>1</code> 和 <code>new Number(1)</code> 被认为是 equal,[1]</code> 和 [1]</code> 被认为是 equal(尽管它们的引用并不相同),当然ÿ...
  • 用Python实现KNN算法(从原理到代码的实现) ...其实啊,KNN的原理就是当预测一个新的值x的时候,根据它距离最近的K个点是什么类别来判断x属于哪个类别。 听起来有点绕,还是看看图吧。 图中绿色的点就是我们要预测的
  • 我理解的题目意思是每块地牛的数量根据输入的前后顺序以一维数组的形式储存,若要围起来,则数组间必然相连。ps:不知道是不是我题目理解错误。) 1.直接将各块地中的牛的数量存到1维...
  • KNN算法概述

    2019-11-28 19:56:44
    KNN算法概述 KNN可以说是最简单的分类算法之一,同时,它也最常用的分类算法之一,注意KNN算法有监督学习中的分类算法,它...KNN的全称是K Nearest Neighbors,意思是K个最近的邻居,从这个名字我们就能看出一些...
  • 一.KNN算法概述 KNN可以说是最简单的分类算法之一,同时,它也最常用的分类算法之一,注意KNN算法有监督学习中的分类算法,它看...KNN的全称是K Nearest Neighbors,意思是K个最近的邻居,从这个名字我们就能看...
  • 深入浅出KNN算法(一) KNN算法原理

    千次阅读 2019-04-03 18:59:00
    一.KNN算法概述 KNN可以说是最简单的分类算法之一,同时,它也最常用的分类算法之一,注意KNN算法有监督学习中的分类算法,它...KNN的全称是K Nearest Neighbors,意思是K个最近的邻居,从这个名字我们就能看出...
  • 一.KNN算法概述 KNN可以说是最简单的分类算法之一,同时,它也最常用的分类算法之一,注意KNN算法有监督学习中的分类算法,它...KNN的全称是K Nearest Neighbors,意思是K个最近的邻居,从这个名字我们就能看出...
  • 几句话之KNN和Kd-tree

    2019-11-12 13:36:45
    找一下周围的邻居们,看邻居们是什么,就大概知道自己是什么了,有点“物以类聚,人以群分”的意思。 kd-tree(k-dimensional树的简称) 分割k维空间的数据。找邻居的方法比KNN先进了一些,其余的都一样。 找邻居: ...
  • 网络带宽

    2021-01-06 18:30:46
    网络带宽中多少M以及Kbps和KB/s到底是什么意思? B是指字节(Byte)1个字节有8个比特组成 b是指比特(bit)代表一个2进制位(值为0或1) 1M=1024K 1Byte=8bit 我们通常所说的网络带宽是以M为单位,1M是指"1Mbps,指...
  • KMP算法

    2018-10-07 16:31:14
    计算那个next的时候确实有点难懂,但是看完这个博客下面那个图的时候我算是明白了,计算next值的k=next[k]和匹配的j=next[j]其实一个意思,只不过一个拿自己匹配自己,另外一个拿主串匹配模式串 其实要说懂了...
  • Bugku:杂项 隐写2

    2021-04-23 16:06:36
    提示有点意思,说是斗地主,查询了网上的信息,理查曼红桃K,雅典娜黑桃Q,图里说的梅花J。提示为3个数字,网上大神都用的暴力破解的方法,没有用到这几个提示,我观察了一下键盘,发现K向上走对应的键盘数字8...
  • 你必须知道的495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    3.20 “semanticsof‘’changeinANSIC”的警告是什么意思? 3.21 “无符号保护”和“值保护”规则的区别在哪里? 第4章 指针 基本的指针应用 4.1 指针到底有什么好处? 4.2 我想声明一个指针并为它分配...
  • 合并序列,枚举k,暴力统计不知道为啥会WA,题意里的k到底代表什么意思至今没看懂。。。 tree我感觉暴力枚举c(n,2)加lca大概lgn应该可以卡5e5的数据的啊,可是怎么调都TLE A The warm love problem AC 题意:给...
  • 看到这道题时,总感觉题目意思有点奇怪,看样例和最下面的Note可以大概知道它在说什么。 题目大意:四个小偷去偷巧克力,且后一个偷的数量前一个的 k 倍,而小偷的背包最多可以放 n 块巧克力,问 n 最小为多少。...
  • 题意:这道题看了两天才看懂,zz。...要把从2到n的n-1个点分到k个集合Si里去,每个集合不能有相同的点,然后f(Si)从点1连通集合Si中所有点之后的边权和,说是什么最小和,其实就是和,没有什么是不是最小,分好集合
  • 1.11 extern在函数声明中是什么意思? 1.12 关键字auto到底有什么用途? 类型定义(typedef)  1.13 对于用户定义类型,typedef和#define有什么区别? 1.14 我似乎不能成功定义一个链表。我试过typedefstruct{...
  •  1.11 extern在函数声明中是什么意思? 1.12 关键字auto到底有什么用途? 类型定义(typedef) 1.13 对于用户定义类型,typedef和#define有什么区别? 1.14 我似乎不能成功定义一个链表。我试过typedefstruct{...
  • BT5工具之Weevely使用

    2014-12-26 16:56:18
    这个小东东有点意思,类似于我们常用的“菜刀”,可以说是linux命令版的菜刀了。   这里我用的0.6版本的,BT5自带的0.5吧,我看版本太低被我给K了,自己装个0.6,据说0.7也出了,多了个代理和端口扫描的功能...
  • 《你必须知道的495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    3.20 “semantics of‘’change in ANSI C”的警告是什么意思? 42 3.21 “无符号保护”和“值保护”规则的区别在哪里? 42 第4章 指针 45 基本的指针应用 45 4.1 指针到底有什么好处? 45 4.2 我想声明...
  • 2021天梯赛L2题解全集

    2021-04-26 18:51:33
    其实就是个模拟,按照题目意思写下去吧,也不知道为什么比赛的时候一直只能拿20分(用char数组+ int变量模拟栈) 赛后直接用栈写的一发满分就很奇怪。。。主要题意有点绕,看各位语文如何 了 char s[110][1100]...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

有点k是什么意思