Added custom index block tree creation by adjacency matrix

shogun-toolbox · Jul 5, 2012 · 991fbc7 · 991fbc7
1 parent 463293d
commit 991fbc7
Show file tree

Hide file tree

Showing 3 changed files with 133 additions and 22 deletions.
diff --git a/src/shogun/classifier/FeatureBlockLogisticRegression.cpp b/src/shogun/classifier/FeatureBlockLogisticRegression.cpp
@@ -103,11 +103,6 @@ bool CFeatureBlockLogisticRegression::train_machine(CFeatures* data)
 		{
 			CIndexBlockTree* feature_tree = (CIndexBlockTree*)m_feature_relation;
 
-			CIndexBlock* root_block = feature_tree->get_root_block();
-			if (root_block->get_max_index() > features->get_dim_feature_space())
-				SG_ERROR("Root block covers more vectors than available\n");
-			SG_UNREF(root_block);
-
 			SGVector<float64_t> ind_t = feature_tree->get_SLEP_ind_t();
 			options.ind_t = ind_t.vector;
 			options.n_nodes = ind_t.vlen/3;

diff --git a/src/shogun/lib/IndexBlockTree.cpp b/src/shogun/lib/IndexBlockTree.cpp
@@ -13,6 +13,14 @@
 using namespace std;
 using namespace shogun;
 
+struct tree_node_t
+{
+	tree_node_t** desc;
+	int32_t n_desc;
+	int32_t sub_nodes_count;
+	int32_t idx;
+};
+
 struct block_tree_node_t
 {
 	block_tree_node_t(int32_t min, int32_t max, float64_t w)
@@ -25,6 +33,49 @@ struct block_tree_node_t
 	float64_t weight;
 };
 
+int count_sub_nodes_recursive(tree_node_t* node)
+{
+	if (node->n_desc==0)
+	{
+		return 1;
+	}
+	else
+	{
+		node->sub_nodes_count = 0;
+		for (int32_t i=0; i<node->n_desc; i++)
+		{
+			node->sub_nodes_count += count_sub_nodes_recursive(node->desc[i]);
+		}
+		return node->sub_nodes_count;
+	}
+}
+
+void print_tree(tree_node_t* node, int tabs)
+{
+	for (int32_t t=0; t<tabs; t++)
+		SG_SPRINT("  ");
+	SG_SPRINT("%d %d\n",node->idx, node->sub_nodes_count);
+	for (int32_t i=0; i<node->n_desc; i++)
+		print_tree(node->desc[i],tabs+1);
+}
+
+void fill_ind_recursive(tree_node_t* node, vector<block_tree_node_t>* tree_nodes, int32_t lower)
+{
+	int32_t l = lower;
+	for (int32_t i=0; i<node->n_desc; i++)
+	{
+		int32_t c = node->desc[i]->n_desc;
+		if (c>0)
+		{
+			tree_nodes->push_back(block_tree_node_t(l,l+c-1,1.0));
+			fill_ind_recursive(node->desc[i], tree_nodes, l);
+			l+=c;
+		}
+		else
+			l++;
+	}
+}
+
 void collect_tree_nodes_recursive(CIndexBlock* subtree_root_block, vector<block_tree_node_t>* tree_nodes)
 {
 	CList* sub_blocks = subtree_root_block->get_sub_blocks();
@@ -55,6 +106,57 @@ CIndexBlockTree::CIndexBlockTree(CIndexBlock* root_block) : CIndexBlockRelation(
 	set_root_block(root_block);
 }
 
+CIndexBlockTree::CIndexBlockTree(SGMatrix<float64_t> adjacency_matrix) : 
+	CIndexBlockRelation(),
+	m_root_block(NULL)
+{
+	ASSERT(adjacency_matrix.num_rows == adjacency_matrix.num_cols);
+	int32_t n_features = adjacency_matrix.num_rows;
+
+	// well ordering is assumed
+
+	tree_node_t* nodes = SG_CALLOC(tree_node_t, n_features);
+
+	int32_t* nz_row = SG_CALLOC(int32_t, n_features);
+	for (int32_t i=0; i<n_features; i++)
+	{
+		nodes[i].idx = i;
+		nodes[i].sub_nodes_count = 0;
+		int32_t c = 0;
+		for (int32_t j=i; j<n_features; j++)
+		{
+			if (adjacency_matrix(j,i)!=0.0)
+				nz_row[c++] = j;
+		}
+		nodes[i].n_desc = c;
+		nodes[i].desc = SG_MALLOC(tree_node_t*, c);
+		for (int32_t j=0; j<c; j++)
+		{
+			nodes[i].desc[j] = &nodes[nz_row[j]]; 
+		}
+		if (nz_row[c] == n_features)
+			break;
+	}
+	SG_FREE(nz_row);
+
+	count_sub_nodes_recursive(nodes);
+	//print_tree(nodes,0);
+	m_precomputed_ind_t = SGVector<float64_t>(3*(n_features-nodes[0].sub_nodes_count));
+	vector<block_tree_node_t> blocks;
+	fill_ind_recursive(nodes, &blocks, 1);
+	m_precomputed_ind_t[0] = -1;
+	m_precomputed_ind_t[1] = -1;
+	m_precomputed_ind_t[2] = 1.0;
+
+	for (int32_t i=0; i<(int)blocks.size(); i++)
+	{
+		m_precomputed_ind_t[3+3*i+0] = blocks[i].t_min_index; 
+		m_precomputed_ind_t[3+3*i+1] = blocks[i].t_max_index;
+		m_precomputed_ind_t[3+3*i+2] = blocks[i].weight;
+	}
+	SG_FREE(nodes);
+}
+
 CIndexBlockTree::~CIndexBlockTree()
 {
 	SG_UNREF(m_root_block);
@@ -81,26 +183,32 @@ SGVector<index_t> CIndexBlockTree::get_SLEP_ind()
 
 SGVector<float64_t> CIndexBlockTree::get_SLEP_ind_t()
 {
-	CList* blocks = new CList(true);
+	if (m_precomputed_ind_t.vlen)
+		return m_precomputed_ind_t;
 
-	vector<block_tree_node_t> tree_nodes = vector<block_tree_node_t>();
-
-	collect_tree_nodes_recursive(m_root_block, &tree_nodes);
+	else
+	{
+		CList* blocks = new CList(true);
 
-	SGVector<float64_t> ind_t(3+3*tree_nodes.size());
-	// supernode
-	ind_t[0] = -1;
-	ind_t[1] = -1;
-	ind_t[2] = 1.0;
+		vector<block_tree_node_t> tree_nodes = vector<block_tree_node_t>();
+
+		collect_tree_nodes_recursive(m_root_block, &tree_nodes);
 
-	for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
-	{
-		ind_t[3+i*3] = tree_nodes[i].t_min_index + 1;
-		ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
-		ind_t[3+i*3+2] = tree_nodes[i].weight;
-	}
+		SGVector<float64_t> ind_t(3+3*tree_nodes.size());
+		// supernode
+		ind_t[0] = -1;
+		ind_t[1] = -1;
+		ind_t[2] = 1.0;
 
-	SG_UNREF(blocks);
+		for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
+		{
+			ind_t[3+i*3] = tree_nodes[i].t_min_index + 1;
+			ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
+			ind_t[3+i*3+2] = tree_nodes[i].weight;
+		}
 
-	return ind_t;
+		SG_UNREF(blocks);
+
+		return ind_t;
+	}
 }
diff --git a/src/shogun/lib/IndexBlockTree.h b/src/shogun/lib/IndexBlockTree.h
@@ -28,6 +28,11 @@ class CIndexBlockTree : public CIndexBlockRelation
 	 */
 	CIndexBlockTree(CIndexBlock* root_block);
 
+	/** constructor
+	 * @param adjacency_matrix adjacency matrix
+	 */
+	CIndexBlockTree(SGMatrix<float64_t> adjacency_matrix);
+
 	/** destructor */
 	virtual ~CIndexBlockTree();
 
@@ -56,6 +61,9 @@ class CIndexBlockTree : public CIndexBlockRelation
 
 	/** root block */
 	CIndexBlock* m_root_block;
+
+	/** precomputed ind_t */
+	SGVector<float64_t> m_precomputed_ind_t;
 };
 
 }