[C++]HKM勉強したい＠そのいち

始まりました、「～したい」シリーズ。
今回はHKM≪階層的K平均法≫です。


話は変わるんですけど、ワタクシ大変なことに気づいてしまいました・・・。
「～したい」シリーズのタイトルの後ろについてる「＠その～」っていうバックナンバー、


そのいち、そのにぐらいまでしか続かない(^p^)


バックナンバーつける意味あるのかってね。

BBCPマコトの紹介記事とかだと結構続いたんですけどね。

飽きっぽい性格の私は一つの物事に集中して取り組めないのですよ(^p^)

いっそバックナンバー制廃止にしようかな。





まあ、それはさておいて、今回のタイトル「HKM」についてです。

HKMとは本来ならクラスタ分析をする為に使われる手法です。

今回はこれを最近傍探索に使います。

最近傍探索にはいろいろな手法があるのですが、これはKDtreeに似ているかもしれません。

KDtreeという手法は簡単に言えば

1. 空間を分割する。
2. クエリが分割された空間のどこに属するか調べる。
3. クエリが属する空間の中に最近傍がある。

という手法です。

それに対してHKMは

1. データを2つのクラスタ（データの集合）に分ける。
2. 分けられたクラスタの中のデータをさらに2つのクラスタに分ける。
3. クラスタの中のデータが1つになるまで1.2.を繰り返す。
4. クエリがどのクラスタに属するか調べる。
5. クエリが属するクラスタがの中に最近傍がある。

という手法です。

詳しいことは　知　り　ま　せ　ん　。

詳しい人は私にご教授ください。

とりあえず今回HKMを使うために使ったアルゴリズムとその紹介。

KNN（ｋ近傍法）　

クエリの近傍をｋ個求める手法。

アルゴリズム

1. クエリとデータベース全点の距離を計算。
2. 距離を昇順にソート。
3. 上からｋ個をとる。

Kmeans（ｋ平均法）

ｋ個のクラスタを作る手法。

アルゴリズム

1. 空のクラスタをｋ個作る。
2. それぞれのクラスタにランダムにデータを割り当てる。
3. クラスタに含まれるデータの座標の平均をクラスタの中心とする。
4. 各データと各クラスタ中心の距離を計算し、各データを最近傍となる各クラスタに割り当てなおす。
5. 割り当ての変化量が一定の閾値以内になるまで3.4.を繰り返す。

HKM（階層的ｋ平均法）

階層的にｋ個のクラスタを作る手法。

アルゴリズム

1. ｋ個のクラスタを作る。
2. クラスタの中でさらにｋ個のクラスタを作る。
3. クラスタの中のデータが1個になるまで2.を繰り返す。

こんな感じです。

最初にKNNを作って、次にKNNを使ってKmeansを作って、次にKmeansを使ってHKMを作ります。

こういうの楽しいよね。

弱い武器を強化していって最強の武器を作るみたいな感じ。

テンションが上がりますね(^p^)

それでは以下ソース
量がやばい。

	#pragma once
	#include"KMeansClass.h"
	class HKMClass :public KMeansClass
	{
	public:
	static struct vertex
	{
	vertex* left;
	vertex* right;
	vector<CLASTER> claster;
	};
	static enum CONST
	{
	left,
	right,
	hk = 2,
	};
	vertex *node;
	HKMClass() :KMeansClass()
	{}
	HKMClass(const int &t) :KMeansClass(hk,t)
	{
	}
	HKMClass(const vector<DATA> &data, const int &t) :KMeansClass(hk,t)
	{
	this->node = MakeHKM(data);
	}
	~HKMClass(){}
	vertex* R_MakeHKM(const vector<DATA> &data)
	{
	vertex *node = new vertex();
	node->claster = MakeClaster(data, hk);
	if (node->claster[left].data.size() < hk)
	{
	node->left = NULL;
	}
	else
	{
	node->left = R_MakeHKM(node->claster[left].data);
	}
	if (node->claster[right].data.size() < hk)
	{
	node->right = NULL;
	}
	else
	{
	node->right = R_MakeHKM(node->claster[right].data);
	}
	return node;
	}
	vertex* MakeHKM(const vector<DATA> &data)
	{
	this->node = R_MakeHKM(data);
	return this->node;
	}
	vector<DATA> R_Search(const DATA &query,const vertex* node)
	{
	size_t claster_size = node->claster.size();
	if (claster_size < hk)
	{
	return node->claster[0].data;
	}
	vector<DATA> center(claster_size);
	for (int i = 0; i < claster_size;++i)
	{
	center[i] = node->claster[i].center;
	}
	KNNClass knn_obj(center, 1);
	int neighbor=knn_obj.KNN(query)[0].second;
	if ((node->left!=NULL)&&(neighbor == left || node->right==NULL))
	{
	return R_Search(query, node->left);
	}
	else if ((node->right != NULL) && (neighbor == right || node->left == NULL))
	{
	return R_Search(query, node->right);
	}
	else if (node->left == NULL&&node->right == NULL)
	{
	return node->claster[0].data;
	}
	else
	{
	}
	return vector<DATA>();
	}
	DATA Search(const DATA &query,const vertex* node)
	{
	return R_Search(query, node)[0];
	}
	DATA Search(const DATA &query)
	{
	return Search(query, this->node);
	}
	};

view raw HKMClass.h hosted with ❤ by GitHub

	#pragma once
	#include<vector>
	#include"KNNClass.h"
	#include"../../../Useful/useful.h"
	using namespace std;
	class KMeansClass
	{
	public:
	typedef vector<double> DATA;
	static struct CLASTER
	{
	vector<DATA> data;
	DATA center;
	};
	protected:
	int k;
	vector<CLASTER> claster;
	int threshold;
	void CalcCenter(vector<CLASTER> *claster)
	{
	size_t feature_size = (*claster)[0].data[0].size();
	for (auto &i : *claster)
	{
	i.center = VectorAverage(i.data);
	}
	}
	int ReassignData(vector<CLASTER> *claster, const int &k)
	{
	vector<DATA> center(k);
	for (int i = 0; i < k; ++i)
	{
	center[i] = (*claster)[i].center;
	}
	KNNClass knn_obj(center, 1);
	int difference = 0;
	for (int i = 0; i < k; i++)
	{
	size_t data_size = (*claster)[i].data.size();
	for (int j=0;j<data_size;++j)
	{
	DATA* temp = &(*claster)[i].data[j];
	int neighbor = knn_obj.KNN(*temp)[0].second;
	if (i != neighbor)
	{
	++difference;
	(*claster)[neighbor].data.push_back(*temp);
	(*claster)[i].data.erase
	(
	remove
	(
	(*claster)[i].data.begin(), (*claster)[i].data.end(), *temp
	)
	);
	data_size = (*claster)[i].data.size();
	}
	}
	}
	return difference;
	}
	void InitClasterData(vector<CLASTER> *claster)
	{
	for (auto &i : *claster)
	{
	i.data.clear();
	i.center.clear();
	}
	}
	void AllocateForNormal(vector<CLASTER> *claster, const vector<DATA> &data, const int &k)
	{
	int i = 0;
	for (auto &j : data)
	{
	(*claster)[++i%k].data.push_back(j);
	}
	}
	public:
	KMeansClass()
	{
	SetK(1);
	SetThreshold(100);
	}
	KMeansClass(const int &k)
	{
	SetK(k);
	SetThreshold(100);
	}
	KMeansClass(const int &k, const int &t)
	{
	SetK(k);
	SetThreshold(t);
	}
	KMeansClass(const vector<DATA> &data,const int &k, const int &t)
	{
	SetK(k);
	SetThreshold(t);
	MakeClaster(data);
	}
	~KMeansClass(){}
	vector<CLASTER> MakeClaster(const vector<DATA> &data, const int &k)
	{
	auto claster_size = k;
	vector<CLASTER> claster(k);
	AllocateForNormal(&claster, data, k);
	CalcCenter(&claster);
	while (threshold<ReassignData(&claster, k));
	this->claster = claster;
	return claster;
	}
	vector<DATA> Search(const DATA &query)
	{
	int claster_size = this->claster.size();
	vector<DATA> center(claster_size);
	for (int i = 0; i < claster_size; ++i)
	{
	center[i] = this->claster[i].center;
	}
	KNNClass knn_obj(center, 1);
	int neighbor = knn_obj.KNN(query)[0].second;
	return this->claster[neighbor].data;
	}
	vector<CLASTER> MakeClaster(const vector<DATA> &data)
	{
	return MakeClaster(data, this->k);
	}
	void InitClasterData()
	{
	InitClasterData(&this->claster);
	}
	void SetK(const int &k)
	{
	this->k = k;
	}
	void SetThreshold(const int &t)
	{
	this->threshold = t;
	}
	vector<CLASTER> GetClaster()
	{
	return this->claster;
	}
	};

view raw KMeansClass.h hosted with ❤ by GitHub

	#pragma once
	#include<vector>
	#include<utility>
	#include<algorithm>
	using namespace std;
	typedef vector<double> DATA;
	typedef vector<pair<double, int>> SOLVE;
	class KNNClass
	{
	private:
	vector<DATA> data_base;
	int k;
	double Sqare(const double &x)
	{
	return x*x;
	}
	double Distance(const DATA &a, const DATA &b)
	{
	auto size = a.size();
	double sum = 0.;
	for (auto i = 0; i < size; ++i)
	{
	sum += Sqare(a[i] - b[i]);
	}
	return sum;
	}
	public:
	KNNClass()
	{
	SetK(1);
	InitDataBase();
	}
	KNNClass(const int &k)
	{
	SetK(k);
	InitDataBase();
	}
	KNNClass(const vector<DATA> &data_base)
	{
	SetK(1);
	SetDataBase(data_base);
	}
	KNNClass(const vector<DATA> &data_base, const int &k)
	{
	SetK(k);
	SetDataBase(data_base);
	}
	~KNNClass(){}
	vector<pair<double, int>> KNN(const DATA &query, const vector<DATA> &data_base, const int &k)
	{
	auto size = data_base.size();
	vector<pair<double, int>> distance(size);
	for (auto i = 0; i < size; ++i)
	{
	distance[i] = make_pair(Distance(query, data_base[i]), i);
	}
	sort(distance.begin(), distance.end());
	return vector<pair<double, int>>(distance.begin(), distance.begin() + k);
	}
	vector<pair<double, int>> KNN(const DATA &query, const vector<DATA> &data_base)
	{
	return KNN(query, data_base, this->k);
	}
	vector<pair<double, int>> KNN(const DATA &query, const int &k)
	{
	return KNN(query, this->data_base, k);
	}
	vector<pair<double, int>> KNN(const DATA &query)
	{
	return KNN(query, this->data_base, this->k);
	}
	void SetK(const int &k)
	{
	this->k = k;
	}
	void SetDataBase(const vector<DATA> &data_base)
	{
	this->data_base = data_base;
	}
	void InitDataBase()
	{
	this->data_base.clear();
	}
	};

view raw KNNClass.h hosted with ❤ by GitHub

説明はきっといらないよね・・・？
アルゴリズムの紹介してるしね？

未来の俺はこう言う。
「コメント文ぐらい書けよ(#^p^)」

ってか、あれ、これ・・・

そのに、そのさんに分ければよかったんじゃね？？

[C++]タブーサーチ作り直したい

なんかタブーサーチ改良することになったのでもう一度あげます。

～～変更点～～

・近傍生成方法を選べるようになったよ！
今のところ
・データを入れ替える
・bitを反転させる

の二つが選べます。

説明するのは面倒なので後日暇があったら画像付きで説明します。
まぢつかれたょ。。。

以下ソース

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include<random>
	#include<utility>
	#include<functional>
	using namespace std;
	//タブーサーチクラス
	template<class T_n>
	class TabuSearchClass
	{
	private:
	//現在の解
	vector<T_n> current;
	//最適解
	vector<T_n> optimal;
	//最適解のサイズ
	size_t optimal_size;
	//タブーリスト
	vector<pair<T_n, T_n>> tabu_list;
	//タブーリストのサイズ
	size_t tabu_list_size;
	//近傍生成方法
	public:
	static const enum Neighbor
	{
	DATASWAP,
	BITINVERT,
	};
	private:
	Neighbor neighbor;
	//探索回数
	size_t search_num;
	//最大評価値
	double max_evaluate;
	//現在の評価値
	double current_evaluate;
	//乱数用
	mt19937 mt;
	//最適解と最大評価値の初期化
	void Initialize()
	{
	optimal = vector<T_n>(this->current.begin(), current.begin() + optimal_size);
	max_evaluate = current_evaluate = 0.;
	}
	//近傍の選択
	vector<vector<T_n>> DataSwap(const vector<T_n> &current)
	{
	size_t current_size = current.size();
	//size_t data_size = GetDataSize();
	vector<vector<T_n>> neighbor(current_size, vector<T_n>(current));
	for (size_t i = 0; i < current_size; i++)
	{
	swap(neighbor[i][0], neighbor[i][i]);
	}
	return vector<vector<T_n>>(neighbor.begin() + 1, neighbor.end());
	}
	vector<vector<T_n>> BitInvert(const vector<T_n> &current)
	{
	size_t current_size = current.size();
	//size_t data_size = GetDataSize();
	vector<vector<T_n>> neighbor(current_size, vector<T_n>(current));
	for (size_t i = 0; i < current_size; i++)
	{
	neighbor[i][i] = (neighbor[i][i] + 1) % 2;
	}
	return vector<vector<T_n>>(neighbor.begin() , neighbor.end());
	}
	//優良解の探索
	//predにはvector<T_n>の型を引数にした評価関数を渡す
	template<class _Pre>
	void ChoiceExellence(_Pre pred)
	{
	vector<vector<T_n>>(TabuSearchClass::*ChoiceNeighbor[])(const vector<T_n>&) =
	{
	&TabuSearchClass::DataSwap,
	&TabuSearchClass::BitInvert,
	};
	vector<vector<T_n>> neighbor = (this->*ChoiceNeighbor[this->neighbor])(this->current);
	size_t solve_size = GetSolveSize();
	size_t neighbor_size = neighbor.size();
	double max = 0.;
	double evaluate;
	vector<pair<double, int>> better;
	for (size_t i = 0; i < neighbor_size; i++)
	{
	evaluate = pred(vector<T_n>(neighbor[i].begin(), neighbor[i].begin() + solve_size));
	/*if (evaluate>=max)
	{
	max = evaluate;
	better = i;
	}*/
	better.push_back(make_pair(evaluate, i));
	}
	sort(better.begin(), better.end(), std::greater<pair<double, int>>());
	this->current_evaluate = better[0].first;
	for (auto &i : better)
	{
	if (CheckTransition(neighbor[i.second], make_pair(this->current[0], neighbor[i.second][0])))
	break;
	}
	//this->current_evaluate = max;
	//CheckTransition(neighbor[better], make_pair(neighbor[better][0], neighbor[better][better]));
	//return neighbor[better];
	}
	//遷移がタブーリストに含まれているか判定
	//含まれていたらtrue
	bool CheckTabu(const pair<T_n, T_n> &transition)
	{
	for (auto &i : tabu_list)
	{
	if (i == transition || i == make_pair(transition.second, transition.first))
	{
	return true;
	}
	}
	return false;
	}
	//現在の解を遷移するか判定
	//遷移したらtrue
	bool CheckTransition(const vector<T_n> &neighbor, const pair<T_n, T_n> &transition)
	{
	size_t solve_size = this->GetSolveSize();
	if (current_evaluate > max_evaluate)
	{
	this->optimal = vector<T_n>(neighbor.begin(), neighbor.begin() + solve_size);
	this->current = neighbor;
	max_evaluate = current_evaluate;
	if (CheckTabu(transition))
	{
	tabu_list.erase(find(tabu_list.begin(), tabu_list.end(), transition));
	tabu_list.push_back(transition);
	}
	else
	{
	tabu_list.push_back(transition);
	if (CheckTabuListSizeOver())
	{
	tabu_list.erase(tabu_list.begin());
	}
	}
	return true;
	}
	else
	{
	if (!CheckTabu(transition))
	{
	this->current = neighbor;
	tabu_list.push_back(transition);
	if (CheckTabuListSizeOver())
	{
	tabu_list.erase(tabu_list.begin());
	}
	return true;
	}
	else
	return false;
	}
	return false;
	}
	//タブーリストのサイズが指定のサイズをオーバーしたか判定
	//オーバーしたらtrue
	bool CheckTabuListSizeOver()
	{
	return tabu_list.size() > tabu_list_size;
	}
	//重複回数をカウント、指定回数以上重複でtrueを返す
	class CheckConvergence
	{
	private:
	vector<T_n> data;
	int count;
	int num;
	public:
	//コンストラクタはコメント表示されない？
	CheckConvergence(){}
	//dataに初期解、numに何回解が変わらなかったら収束するかを設定
	CheckConvergence(const vector<T_n> &data, const int &num)
	{
	this->data = data;
	this->count = 0;
	this->num = num;
	}
	~CheckConvergence(){}
	//countがnumを超えたらtrue(収束)
	bool operator()(const vector<T_n> &data)
	{
	if (this->data == data)
	{
	count++;
	}
	else
	{
	this->data = data;
	count = 0;
	}
	return count > num;
	}
	};
	public:
	//デフォルト値
	//最適解のvectorのサイズ
	static const size_t default_optimal_size = 10;
	//探索回数
	static const size_t default_search_num = 100;
	//タブーリストのサイズ
	static const size_t default_list_size = 7;
	//コンストラクタ
	TabuSearchClass()
	{
	SetMt();
	}
	//最適解を見つけたいvectorをvに渡す
	TabuSearchClass(const vector<T_n> &v)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(default_optimal_size);
	SetSeachNum(default_search_num);
	this->SetTabuListSize(default_list_size);
	SetNeighborMethod(DataSwap);
	}
	//最適解を見つけたいvectorをvに渡す
	//最適解のvectorのサイズをoptimal_sizeに渡す
	TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(optimal_size);
	SetSeachNum(100);
	this->SetTabuListSize(7);
	SetNeighborMethod(DataSwap);
	}
	//最適解を見つけたいvectorをvに渡す
	//最適解のvectorのサイズをoptimal_sizeに渡す
	//探索回数をsearch_numに渡す
	TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(optimal_size);
	SetSeachNum(search_num);
	this->SetTabuListSize(7);
	SetNeighborMethod(DataSwap);
	}
	//最適解を見つけたいvectorをvに渡す
	//最適解のvectorのサイズをoptimal_sizeに渡す
	//探索回数をsearch_numに渡す
	//近傍生成方法をneighborに渡す
	TabuSearchClass
	(
	const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num,const Neighbor &neighbor
	)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(optimal_size);
	SetSeachNum(search_num);
	this->SetTabuListSize(7);
	SetNeighborMethod(neighbor);
	}
	//最適解を見つけたいvectorをvに渡す
	//最適解のvectorのサイズをoptimal_sizeに渡す
	//探索回数をsearch_numに渡す
	//タブーリストのサイズをlist_sizeに渡す
	TabuSearchClass
	(
	const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num,
	const size_t &list_size
	)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(optimal_size);
	SetSeachNum(search_num);
	this->SetTabuListSize(list_size);
	SetNeighborMethod(DataSwap);
	}
	~TabuSearchClass(){}
	////最適解を見つけたいvectorをvに渡す
	void SetData(const vector<T_n> &v)
	{
	this->current = v;
	}
	//最適解のvectorのサイズをoptimal_sizeに渡す
	void SetOptimalSize(const size_t &size)
	{
	this->optimal_size = size;
	}
	//メルセンヌツイスタの初期化
	void SetMt()
	{
	random_device rnd;
	mt.seed(rnd());
	}
	//データのサイズを返す
	size_t GetDataSize()const
	{
	return this->current.size();
	}
	//最適解のサイズを返す
	size_t GetSolveSize()const
	{
	return this->optimal.size();
	}
	//タブーリストのサイズをsizeに設定する
	void SetTabuListSize(const size_t &size)
	{
	this->tabu_list_size = size;
	}
	//タブーサーチをする
	//predにはvector<T_n>の型を引数にした評価関数を渡す
	template<class _Pre>
	vector<T_n> TabuSearch(_Pre pred)
	{
	const size_t convergence_num = 5;
	CheckConvergence obj(this->current, convergence_num);
	Initialize();
	for (int i = 0; !obj(this->current) && i < search_num; i++)
	{
	ChoiceExellence(pred);
	//CheckTransition();
	}
	return optimal;
	}
	//探索回数をnumに設定
	void SetSeachNum(const size_t &num)
	{
	this->search_num = num;
	}
	//最大評価値を返す
	double GetMaxEvaluate()const
	{
	return max_evaluate;
	}
	void SetNeighborMethod(const Neighbor &neighbor)
	{
	this->neighbor = neighbor;
	}
	};
	void main()
	{
	struct ITEM
	{
	public:
	int num;
	int income;
	int weight;
	bool operator==(const ITEM &i)const
	{
	return i.num == this->num;
	}
	};
	ITEM a[5] =
	{
	{ 0, 1, 2 },
	{ 1, 3, 4 },
	{ 2, 5, 6 },
	{ 3, 7, 8 },
	{ 4, 9, 0 },
	};
	vector<ITEM> v(5);
	for (int i = 0; i < 5;i++)
	{
	/*v[i].num = i;
	cout << "価格:" << flush;
	cin >> v[i].income;
	cout << "重さ:" << flush;
	cin >> v[i].weight;*/
	v[i] = a[i];
	}
	const int max_w = 10;
	vector<int> vv(5,0);
	{
	int weight = 0;
	for (int i = 0; i < 5; i++)
	{
	if (v[i].weight + weight < max_w)
	{
	vv[i] = 1;
	weight += v[i].weight;
	}
	}
	}
	TabuSearchClass<int> obj(vv, 5, 100,TabuSearchClass<int>::Neighbor::BITINVERT);
	//obj.SetWeight(100);
	vector<int> opt = obj.TabuSearch(
	[&](vector<int> &vv)
	{
	int sum = 0;
	int weight = 0;
	int max_w = 10;
	for (int i = 0; i < vv.size(); i++)
	{
	if (vv[i])
	{
	if (weight + v[i].weight < max_w)
	{
	weight += v[i].weight;
	sum += v[i].income;
	}
	}
	}
	return sum;
	}
	);
	for (int i = 0; i < opt.size();i++)
	{
	if (opt[i])
	cout << v[i].num << endl;
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

今回はナップサック問題（？）を解いてみました。だって友達がやれやれうるさいんだもん。
ちゃんと解けてるはず。たぶん。