Kはクラスタリングを意味します

特定の機能を持つ項目のデータセットと、これらの機能の値(ベクトルなど)が与えられます。タスクはそれらの項目をグループに分類することです。これを実現するために、kMeansアルゴリズムを使用します。教師なし学習アルゴリズム 概要 (アイテムをn次元空間内の点として考えると役立ちます)。アルゴリズムはアイテムをk個の類似グループに分類します。その類似度を計算するために、ユークリッド距離を測定値として使用します。 アルゴリズムは次のように機能します。 上記のポイントは、その中に分類された項目の平均値を保持しているため、平均と呼ばれます。これらの手段を初期化するために、たくさんの選択肢があります。直感的な方法は、データセット内のランダムな項目で平均値を初期化することです。もう1つの方法は、データセットの境界間のランダムな値で平均値を初期化することです(フィーチャxの項目の値が[0,3]の場合、平均値を[0,3]のxの値で初期化します)。 。 擬似コードでの上記のアルゴリズム: データを読む 入力をテキストファイル(data.txt)として受け取ります。各行は項目を表し、,で区切られた数値(各機能に1つ)が含まれています。ここにサンプルデータセットがあります。 ファイルからデータを読み取り、それをListに保存します。Listの各要素は、機能の項目値を含む別のListです。これを次の関数で行います。

🐶Pythonコードの例を示すで

def ReadData(fileName):

    # Read the file, splitting by lines
    f = open(fileName, 'r');
    lines = f.read().splitlines();
    f.close();

    items = [];

    for i in range(1, len(lines)):
        line = lines[i].split(',');
        itemFeatures = [];

        for j in range(len(line)-1):
            v = float(line[j]); # Convert feature value to float
            itemFeatures.append(v); # Add feature value to dict

        items.append(itemFeatures);

    shuffle(items);

    return items;

🐶動画で動作確認してみよか?

動画で確認

手段を初期化する アイテムの特徴値の範囲内で各平均値を初期化します。そのためには、各機能の最小値と最大値を見つける必要があります。我々は以下の機能でそれを達成します:

🐶Pythonコードの例を示すで

def FindColMinMax(items):
    n = len(items[0]);
    minima = [sys.maxint for i in range(n)];
    maxima = [-sys.maxint -1 for i in range(n)];

    for item in items:
        for f in range(len(item)):
            if (item[f] < minima[f]):
                minima[f] = item[f];

            if (item[f] > maxima[f]):
                maxima[f] = item[f];

return minima,maxima;

変数minima、maximaは、それぞれ項目の最小値と最大値を含むListです。上記の2つのListで、各平均の特徴量を対応する最小値と最大値の間でランダムに初期化します。

🐶Pythonコードの例を示すで

def InitializeMeans(items, k, cMin, cMax):

    # Initialize means to random numbers between
    # the min and max of each column/feature     
    f = len(items[0]); # number of features
    means = [[0 for i in range(f)] for j in range(k)];

    for mean in means:
        for i in range(len(mean)):

            # Set value to a random float
            # (adding +-1 to avoid a wide placement of a mean)
            mean[i] = uniform(cMin[i]+1, cMax[i]-1);

    return means;

🐶動画で動作確認してみよか?

動画で確認

ユークリッド距離 データセットの類似性の測定基準としてユークリッド距離を使用します(注:アイテムによっては、他の類似性測定基準を使用することもできます)。

🐶Pythonコードの例を示すで

def EuclideanDistance(x, y):
    S = 0; #  The sum of the squared differences of the elements
    for i in range(len(x)):
        S += math.pow(x[i]-y[i], 2);

    return math.sqrt(S); #The square root of the sum

🐶動画で動作確認してみよか?

動画で確認

更新手段 平均値を更新するには、平均値/クラスター内のすべての項目について、その特徴の平均値を見つける必要があります。これを行うには、すべての値を加算してから項目数で除算するか、より洗練された方法を使用します。次のようにして、すべての値を再追加することなく新しい平均を計算します。 ここで、mはフィーチャの平均値、nはクラスタ内のアイテム数、xは追加されたアイテムのフィーチャ値です。私たちは新しい意味を得るためにそれぞれの特徴について上記をします。

🐶Pythonコードの例を示すで

def UpdateMean(n,mean,item):
    for i in range(len(mean)):
        m = mean[i];
        m = (m*(n-1)+item[i])/float(n);
        mean[i] = round(m, 3);

    return mean;

🐶動画で動作確認してみよか?

動画で確認

アイテムを分類する それでは、項目をグループ/クラスターに分類する関数を書く必要があります。与えられたアイテムについて、それぞれの平均との類似性を見つけ、そのアイテムを最も近いものに分類します。

🐶Pythonコードの例を示すで

def Classify(means,item):

    # Classify item to the mean with minimum distance     
    minimum = sys.maxint;
    index = -1;

    for i in range(len(means)):

        # Find distance from item to mean
        dis = EuclideanDistance(item, means[i]);

        if (dis < minimum):
            minimum = dis;
            index = i;

    return index;

🐶動画で動作確認してみよか?

動画で確認

手段を探す 実際に平均値を見つけるには、すべての項目をループ処理してそれらを最も近いクラスターに分類し、クラスターの平均を更新します。一定の反復回数だけこのプロセスを繰り返します。 2回の反復の間に項目が分類を変更しない場合、アルゴリズムが最適な解を見つけたのでプロセスを停止します。 下記の関数は、入力k(必要なクラスタの数)、アイテム、最大反復数を取り、平均とクラスタを返します。アイテムの分類は配列belongsToに格納され、クラスタ内のアイテム数はclusterSizesに格納されます。

🐶Pythonコードの例を示すで

def CalculateMeans(k,items,maxIterations=100000):

    # Find the minima and maxima for columns
    cMin, cMax = FindColMinMax(items);

    # Initialize means at random points
    means = InitializeMeans(items,k,cMin,cMax);

    # Initialize clusters, the array to hold
    # the number of items in a class
    clusterSizes= [0 for i in range(len(means))];

    # An array to hold the cluster an item is in
    belongsTo = [0 for i in range(len(items))];

    # Calculate means
    for e in range(maxIterations):

        # If no change of cluster occurs, halt
        noChange = True;
        for i in range(len(items)):

            item = items[i];

            # Classify item into a cluster and update the
            # corresponding means.         
            index = Classify(means,item);

            clusterSizes[index] += 1;
            cSize = clusterSizes[index];
            means[index] = UpdateMean(cSize,means[index],item);

            # Item changed cluster
            if(index != belongsTo[i]):
                noChange = False;

            belongsTo[i] = index;

        # Nothing changed, return
        if (noChange):
            break;

    return means;

クラスターを探す 最後に、平均が与えられたら、クラスタを見つけます。すべての項目を繰り返し処理し、各項目をその最も近いクラスターに分類します。

🐶Pythonコードの例を示すで

def FindClusters(means,items):
    clusters = [[] for i in range(len(means))]; # Init clusters

    for item in items:

        # Classify item into a cluster
        index = Classify(means,item);

        # Add item to cluster
        clusters[index].append(item);

    return clusters;

🐶動画で動作確認してみよか?

動画で確認

あなたは私のGitHubの上で全体のコードを見いだすことができます、そしてサンプルデータセットとプロット関数。読んでくれてありがとう。

🐶 🐍

Last Updated: 5/19/2019, 1:59:13 AM