局部异常因子算法-LOF

局部异常因子算法-LOF
1、计算k-distance of p：点p的第k距离，也就距离p第k远的点的距离，不包括p。
2、计算k-distance neighborhood of p：点p的第k距离邻域，就是p的第k距离以内的所有点，包括第k距离
3、计算reach-distance：可达距离，若小于第k距离，则可达距离为第k距离，若大于第k距离，则可达距离为真实距离
4、计算local reachability density：局部可达密度
5、计算local outlier factor:局部离群因子

K-Means聚类算法
1、 随机选择初始的两个质心
2、 其他点根据离质心的距离远近分类
3、 计算分好的类的平均值，重新赋值给质心
4、 返回2，直到质心不变

#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

typedef vector<vector<int>> Mat;
//定义分类后返回结果，包括两个质心和两个向量
typedef struct{
    int c1;
    int c2;
    vector<int> vect1;
    vector<int> vect2;
}classifyResult;

//求向量的最大值
int maxV(const vector<int>& obj){
    int max = 0;
    for (int i = 0; i < obj.size(); ++i){
        if (obj[i]>max)
            max = obj[i];
    }
    return max;
}

//返回最大值索引
int maxIndex(const vector<int>& obj){
    int max = 0 , index_ = 0;
    for (int i = 0; i < obj.size(); ++i){
        if (obj[i]>max){
            max = obj[i];
            index_ = i;
        }
    }
    return index_;
}

//返回平均值
double meanV(const vector<int>& obj){
    double sum = 0;
    for (int i = 0; i < obj.size(); ++i){
        sum += obj[i];
    }
    return sum / obj.size();
}

//返回和
int sumV(const vector<int>& obj){
    int sum_ = 0;
    for (int i = 0; i < obj.size(); ++i){
        sum_ += obj[i];
    }
    return sum_;
}

//计算点p的k-distance
//obj：数据集  p:点p的索引  k:
int calKDistance(const vector<int>& obj,int p, int k){
    vector<int> k_near_distance(k, 2147483647);//定义k邻近的向量，存放p点的最近的k个点的距离
    
    //计算k-distance
    for (int j = 0; j < obj.size(); ++j){
        if (p == j)//如果轮到的点 是p自己，直接进入下一次循环
            continue;
        if (int tmp = abs(obj[p] - obj[j]) < maxV(k_near_distance))
            k_near_distance[maxIndex(k_near_distance)] = tmp;
    }
    return maxV(k_near_distance);
}

//计算点p的k-distance neghborhood of p
//obj：数据集  p:点p的索引  k:
vector<int> calKDistanceNeghborhood(const vector<int>& obj, int p, int k){
    vector<int> k_neighborhood;//定义第k距离邻域,存储邻域点的索引
    
    //由于k距离邻域是不确定的，所有又得循环一边，找出所有小于等于k-distance的点（第k距离邻域是否包含点p？）
    //即计算k-distance neghborhood of p
    for (int j = 0; j < obj.size(); ++j){
        if (p == j)//如果轮到的点 是p自己，直接进入下一次循环
            continue;
        if (abs(obj[p] - obj[j]) <= calKDistance(obj, p, k))
            k_neighborhood.push_back(j);
    }
    return k_neighborhood;
}


//计算点o到点p的可达距离reach-distance
//obj:数据集  o:点o的索引  p：点p的索引
int calReachDistance(const vector<int>& obj, int p, int o, int k){
    int reach_distance = calKDistance(obj, o, k);
    if (int tmp = abs(obj[p] - obj[o]) > reach_distance)
        reach_distance = tmp;
    return reach_distance;
}


//计算p点的局部可达密度
//obj：数据集  p:点p的索引  k:
double calLocalReachabilityDensity(const vector<int>& obj, int p, int k){
    double lrdtmp = 0.0;
    vector<int> k_neighborhood = calKDistanceNeghborhood(obj, p, k);
    for (int i = 0; i < k_neighborhood.size(); ++i)
        lrdtmp += calReachDistance(obj, p, k_neighborhood[i], k);
    return 1.0 / (lrdtmp / k_neighborhood.size());
}

//数据预处理，LOF算法过滤局部异常因子
void preDealDate(vector<int>& obj,int k){
}

//数据分类
classifyResult classifyVect(vector<int>& obj){
    classifyResult result;
    if (obj.empty()){
        cout << "empty" << endl;
        return result;
    }
    int len = obj.size();

    int dist1, dist2;//定义到两个质心的两个距离
    //排序
    sort(obj.begin(), obj.end());

    //随机选择两个初始质心，为保证选的质心不属于同一类，目前先选最小和最大点
    int c1 = obj[0], c2 = obj[len-1];

    //如果最大值等于最小值，所有的数都是相同的，结果分成一类就好
    if (c1 == c2){
        result = { c1, c2, obj, obj };
        return result;
    }
    
    while (true)
    {
        vector<int> vect1, vect2;//定义两个向量，分别存储分好的两类数据
        int sum1 = 0, sum2 = 0;
        //计算其他数到质心的L1-Distance，离谁更近归为哪类
        for (int i = 0; i < len; ++i){
            dist1 = abs(obj[i] - c1);
            dist2 = abs(obj[i] - c2);
            if (dist1 <= dist2){//距离c1更近，把该数归为c1类
                vect1.push_back(obj[i]);
                sum1 += obj[i];
            }
            else//距离c2更近，把该数归为c2类
            {
                vect2.push_back(obj[i]);
                sum2 += obj[i];
            }
        }

        //分别计算两类的平均值，替换c1,c2
        if (c1 == sum1 / vect1.size() && c2 == sum2 / vect2.size()){
            result = { c1, c2, vect1, vect2 };
            return result;
        }
        c1 = sum1 / vect1.size();
        c2 = sum2 / vect2.size();
    }
    return result;
}

int main(){

    int a[31] = { 1, 2, 4, 7, -1, 3, 2, 5, 7, 8, 0, 5, 3, 2 ,99,87,67,56,78,99,100,97,56,89,98,97,96,95,94,93,190};
    //int a[5] = { 1,1,2,0,3 };
    vector<int> s(a,a+31);

    classifyResult result = classifyVect(s);
    vector<int> vect1 = result.vect1;
    vector<int> vect2 = result.vect2;


    cout << "原始数据是：\n";
    for (int i = 0; i < s.size(); ++i)
        cout << s[i] << " ";
    cout << "\n";
    cout << "分成两类后的数据分别是：\n";
    cout << "vector1=\n";
    for (int i = 0; i < vect1.size(); ++i)
        cout << vect1[i] << " ";
    cout << "\n";
    cout << "vector2=\n";
    for (int i = 0; i < vect2.size(); ++i)
        cout << vect2[i] << " ";
    cout << "\n";

    cout << "质心分别是c1=" << result.c1 << " c2=" << result.c2<<"\n";

}