import numpy as np
import KNNTest as kt
import sklearn.neighbors as sk # Import Scikit-Learn (Example)
import pykgraph as kg
n = 100 # 100 points
k = 10 # 10-NN
epsilon = 0.5 # at least half of all queries should return exact k-nearest neighbors
d = 4 # 4 dimensions
delta = k # average degree of graph should be k for most NN-libs
c1 = 2 # tuning parameter 1
c2 = 1 # tuning parameter 2
V = kt.Uniform_Random_Tuple_Generator(n, d).get() # Generate n tuples of dimension d uniformly at random
# utilizing mersenne-twister algorithm
Vn = u.numpy_array() # get as numpy nd-array
Vn1 = np.random.rand(n, d) # random data from numpy
V1 = kt.Relation(Vn1) # make KNNTest relation, so a KNN_Graph can be build from the data
#
# Build adjacency-matrix of exact 10-NN Graph efficiently with scikit
#
sk_E = np.matrix(sk.NearestNeighbors(metric='euclidean', algorithm='ball_tree', n_neighbors=k).fit(Vn).kneighbors_graph(Vn, mode='connectivity').toarray().astype('bool'))
knng_sk = kt.KNN_Graph(k)
knng_sk.build(V)
knng_sk.set_edges(sk_E)
#
# Build exact 10-NN Graph with brute-force algorithm in O(n^2)
#
knng_kt = kt.KNN_Graph_Exact(k)
knng_kt.build(V)
#
# Build KNN-Index with KGraph
#
kg_index = pk.KGraph(Vn, 'euclidean')
kg_index.build(reverse=-1)
knng_kg = kt.KNN_Graph(k)
knng_kg.build(V) # dummy build
#
# Wrap KGraph-Index in sampling-function
#
def query_kg(Vn, kg_index, k, i):
neighbors = kg_index.search(Vn[i].reshape(1, Vn[i].shape[0]), K=k)
return Vn[neighbors,:][0]
q_kg = lambda i: query_kg(Vn, kg_index, k, i)
#
# Property Tester for Graphs
#
pt_g = kt.KNN_Tester()
#
# Property Tester for Query-Oracle
#
pt_o = kt.KNN_Tester_Oracle(kg.Query_Oracle(q_kg))
#
# Test Graphs
#
kt_graph_is_far = pt_g.test(knng_kt, delta, d, epsilon, c1, c2)
sk_graph_is_far = pt_g.test(knng_sk, delta, d, epsilon, c1, c2)
#
# Test Oracle
#
kg_oracle_is_far = pt_o.test(knng_kg, delta, d, epsilon, c1, c2)