DSMをJuliaのクラスタリングプログラムで整理する。
今回はDSM(Design Structure Matrix)のクラスタリングコードをJuliaで実装してみます。
クラスタリングアルゴリズムについては下記記事を参照してください。
実際には以下の記事の擬似コードをJuliaで実装し直したものになります。
Juliaのコード
実装したコードは以下のようになりました。
using LinearAlgebra const powcc = 1; const powbid = 0; const powdep = 1; const max_cluster_size = 61; const rand_accept = 30; const rand_bid = 30; const times = 2; const stable_limit = 2; original_DSM=[ 0 1 0 0 1 1 0; 0 0 0 1 0 0 1; 0 1 0 1 0 0 1; 0 1 1 0 1 0 1; 0 0 0 1 0 1 0; 1 0 0 0 1 0 0; 0 1 1 1 0 0 0]; label = ["A","B","C","D","E","F","G"]; (DSMsize,) = size(original_DSM); Clustermatrix = zeros(DSMsize,DSMsize) + Diagonal(ones(DSMsize,DSMsize)) ; DSM = original_DSM; function ClusterBid(Clustermatrix,DSM,DSMsize,powdep,powbid,element) bestCluster = 0; bestBid = -1; for i = 1 : DSMsize Clusterlist= findall(x-> x == 1 , Clustermatrix[i,:]); (Clustersize,) = size(Clusterlist); bid = 0; for j = 1 : Clustersize bid += DSM[element,Clusterlist[j]]; end bid = bid ^ powdep / Clustersize ^ powbid; if bid > bestBid bestBid = bid; bestCluster = i; end end return bestCluster end function TCC(DSM,DSMsize,Clustermatrix,powcc) intraCost=0; extraCost=0; for i = 1: DSMsize for j = 1 : DSMsize Clusterofi = findall(x-> x == 1 , Clustermatrix[:,i]); Clusterofj = findall(x-> x == 1 , Clustermatrix[:,j]); (Clustersizeofi,) = size(Clustermatrix[Clusterofi,:]); cost = DSM[i,j] + DSM[j,i]; if Clusterofi == Clusterofj intraCost += cost*Clustersizeofi^powcc; else extraCost += cost*DSMsize^powcc; end end end totalCost = intraCost + extraCost; return totalCost end TCCost = TCC(DSM,DSMsize,Clustermatrix,powcc) costlist = zeros(DSMsize*times,1); for i = 1 : DSMsize * times; preClustermatrix = Clustermatrix; element = rand(1:DSMsize); bestCluster = ClusterBid(Clustermatrix,DSM,DSMsize,powdep,powbid,element); Clustermatrix[:,element] = zeros(DSMsize,1); Clustermatrix[bestCluster,element] = 1; newCost = TCC(DSM,DSMsize,Clustermatrix,powcc); if newCost <= maximum([TCCost,rand_accept]) global TCCost = newCost; else global Clustermatrix = preClustermatrix; end global costlist[i] = newCost end Clustermatrix costlist'
これを使って実際に試してみます。
例題
下記パラメーターの元で今回のプログラムを実行してみます。 パラメーターの最適化はまだできてないです。
const powcc = 1; const powbid = 0; const powdep = 1; const max_cluster_size = 61; const rand_accept = 30; const rand_bid = 30; const times = 2; const stable_limit = 2;
今回のプログラムより以下のことがわかります。
クラスター | 要素 |
---|---|
クラスター1 | A, E, F |
クラスター2 | B, C, D, G |
この情報から先程のDSMを並び替えてみます。
たしかにクラスタリング前と比べると対角線に非ゼロ要素が集まるようになりました。 次のステップは、自動でDSMを並べ替えて描画までを考えています。
今回はここまでにします。