nodes: 0, module; 1, function_definition; 2, function_name:smooth_knn_dist; 3, parameters; 4, block; 5, identifier:distances; 6, identifier:k; 7, default_parameter; 8, default_parameter; 9, default_parameter; 10, expression_statement; 11, expression_statement; 12, expression_statement; 13, expression_statement; 14, for_statement; 15, return_statement; 16, identifier:n_iter; 17, integer:64; 18, identifier:local_connectivity; 19, float:1.0; 20, identifier:bandwidth; 21, float:1.0; 22, comment:"""Compute a continuous version of the distance to the kth nearest
      neighbor. That is, this is similar to knn-distance but allows continuous
      k values rather than requiring an integral k. In esscence we are simply
      computing the distance such that the cardinality of fuzzy set we generate
      is k.
  
      Parameters
      ----------
      distances: array of shape (n_samples, n_neighbors)
          Distances to nearest neighbors for each samples. Each row should be a
          sorted list of distances to a given samples nearest neighbors.
  
      k: float
          The number of nearest neighbors to approximate for.
  
      n_iter: int (optional, default 64)
          We need to binary search for the correct distance value. This is the
          max number of iterations to use in such a search.
  
      local_connectivity: int (optional, default 1)
          The local connectivity required -- i.e. the number of nearest
          neighbors that should be assumed to be connected at a local level.
          The higher this value the more connected the manifold becomes
          locally. In practice this should be not more than the local intrinsic
          dimension of the manifold.
  
      bandwidth: float (optional, default 1)
          The target bandwidth of the kernel, larger values will produce
          larger return values.
  
      Returns
      -------
      knn_dist: array of shape (n_samples,)
          The distance to kth nearest neighbor, as suitably approximated.
  
      nn_dist: array of shape (n_samples,)
          The distance to the 1st nearest neighbor for each point.
      """; 23, assignment; 24, assignment; 25, assignment; 26, identifier:i; 27, call; 28, block; 29, expression_list; 30, identifier:target; 31, binary_operator:np.log2(k) * bandwidth; 32, identifier:rho; 33, call; 34, identifier:result; 35, call; 36, identifier:range; 37, argument_list; 38, expression_statement; 39, expression_statement; 40, expression_statement; 41, comment:# TODO: This is very inefficient, but will do for now. FIXME; 42, expression_statement; 43, expression_statement; 44, if_statement; 45, for_statement; 46, expression_statement; 47, comment:# TODO: This is very inefficient, but will do for now. FIXME; 48, if_statement; 49, identifier:result; 50, identifier:rho; 51, call; 52, identifier:bandwidth; 53, attribute; 54, argument_list; 55, attribute; 56, argument_list; 57, subscript; 58, assignment; 59, assignment; 60, assignment; 61, assignment; 62, assignment; 63, comparison_operator:non_zero_dists.shape[0] >= local_connectivity; 64, block; 65, elif_clause; 66, identifier:n; 67, call; 68, block; 69, assignment; 70, comparison_operator:rho[i] > 0.0; 71, block; 72, else_clause; 73, attribute; 74, argument_list; 75, identifier:np; 76, identifier:zeros; 77, subscript; 78, identifier:np; 79, identifier:zeros; 80, subscript; 81, attribute; 82, integer:0; 83, identifier:lo; 84, float:0.0; 85, identifier:hi; 86, identifier:NPY_INFINITY; 87, identifier:mid; 88, float:1.0; 89, identifier:ith_distances; 90, subscript; 91, identifier:non_zero_dists; 92, subscript; 93, subscript; 94, identifier:local_connectivity; 95, expression_statement; 96, expression_statement; 97, if_statement; 98, comparison_operator:non_zero_dists.shape[0] > 0; 99, block; 100, identifier:range; 101, argument_list; 102, expression_statement; 103, for_statement; 104, if_statement; 105, if_statement; 106, subscript; 107, identifier:mid; 108, subscript; 109, float:0.0; 110, if_statement; 111, block; 112, identifier:np; 113, identifier:log2; 114, identifier:k; 115, attribute; 116, integer:0; 117, attribute; 118, integer:0; 119, identifier:distances; 120, identifier:shape; 121, identifier:distances; 122, identifier:i; 123, identifier:ith_distances; 124, comparison_operator:ith_distances > 0.0; 125, attribute; 126, integer:0; 127, assignment; 128, assignment; 129, comparison_operator:index > 0; 130, block; 131, else_clause; 132, subscript; 133, integer:0; 134, expression_statement; 135, identifier:n_iter; 136, assignment; 137, identifier:j; 138, call; 139, block; 140, comparison_operator:np.fabs(psum - target) < SMOOTH_K_TOLERANCE; 141, block; 142, comparison_operator:psum > target; 143, block; 144, else_clause; 145, identifier:result; 146, identifier:i; 147, identifier:rho; 148, identifier:i; 149, comparison_operator:result[i] < MIN_K_DIST_SCALE * np.mean(ith_distances); 150, block; 151, if_statement; 152, identifier:distances; 153, identifier:shape; 154, identifier:distances; 155, identifier:shape; 156, identifier:ith_distances; 157, float:0.0; 158, identifier:non_zero_dists; 159, identifier:shape; 160, identifier:index; 161, call; 162, identifier:interpolation; 163, binary_operator:local_connectivity - index; 164, identifier:index; 165, integer:0; 166, expression_statement; 167, if_statement; 168, block; 169, attribute; 170, integer:0; 171, assignment; 172, identifier:psum; 173, float:0.0; 174, identifier:range; 175, argument_list; 176, expression_statement; 177, if_statement; 178, call; 179, identifier:SMOOTH_K_TOLERANCE; 180, break_statement; 181, identifier:psum; 182, identifier:target; 183, expression_statement; 184, expression_statement; 185, block; 186, subscript; 187, binary_operator:MIN_K_DIST_SCALE * np.mean(ith_distances); 188, expression_statement; 189, comparison_operator:result[i] < MIN_K_DIST_SCALE * np.mean(distances); 190, block; 191, identifier:int; 192, argument_list; 193, identifier:local_connectivity; 194, identifier:index; 195, assignment; 196, comparison_operator:interpolation > SMOOTH_K_TOLERANCE; 197, block; 198, expression_statement; 199, identifier:non_zero_dists; 200, identifier:shape; 201, subscript; 202, call; 203, integer:1; 204, subscript; 205, assignment; 206, comparison_operator:d > 0; 207, block; 208, else_clause; 209, attribute; 210, argument_list; 211, assignment; 212, assignment; 213, expression_statement; 214, if_statement; 215, identifier:result; 216, identifier:i; 217, identifier:MIN_K_DIST_SCALE; 218, call; 219, assignment; 220, subscript; 221, binary_operator:MIN_K_DIST_SCALE * np.mean(distances); 222, expression_statement; 223, call; 224, subscript; 225, subscript; 226, identifier:interpolation; 227, identifier:SMOOTH_K_TOLERANCE; 228, expression_statement; 229, assignment; 230, identifier:rho; 231, identifier:i; 232, attribute; 233, argument_list; 234, attribute; 235, integer:1; 236, identifier:d; 237, binary_operator:distances[i, j] - rho[i]; 238, identifier:d; 239, integer:0; 240, expression_statement; 241, block; 242, identifier:np; 243, identifier:fabs; 244, binary_operator:psum - target; 245, identifier:hi; 246, identifier:mid; 247, identifier:mid; 248, binary_operator:(lo + hi) / 2.0; 249, assignment; 250, comparison_operator:hi == NPY_INFINITY; 251, block; 252, else_clause; 253, attribute; 254, argument_list; 255, subscript; 256, binary_operator:MIN_K_DIST_SCALE * np.mean(ith_distances); 257, identifier:result; 258, identifier:i; 259, identifier:MIN_K_DIST_SCALE; 260, call; 261, assignment; 262, attribute; 263, argument_list; 264, identifier:rho; 265, identifier:i; 266, identifier:non_zero_dists; 267, binary_operator:index - 1; 268, augmented_assignment; 269, subscript; 270, binary_operator:interpolation * non_zero_dists[0]; 271, identifier:np; 272, identifier:max; 273, identifier:non_zero_dists; 274, identifier:distances; 275, identifier:shape; 276, subscript; 277, subscript; 278, augmented_assignment; 279, expression_statement; 280, identifier:psum; 281, identifier:target; 282, parenthesized_expression; 283, float:2.0; 284, identifier:lo; 285, identifier:mid; 286, identifier:hi; 287, identifier:NPY_INFINITY; 288, expression_statement; 289, block; 290, identifier:np; 291, identifier:mean; 292, identifier:ith_distances; 293, identifier:result; 294, identifier:i; 295, identifier:MIN_K_DIST_SCALE; 296, call; 297, attribute; 298, argument_list; 299, subscript; 300, binary_operator:MIN_K_DIST_SCALE * np.mean(distances); 301, identifier:np; 302, identifier:floor; 303, identifier:local_connectivity; 304, identifier:index; 305, integer:1; 306, subscript; 307, binary_operator:interpolation * (non_zero_dists[index] - non_zero_dists[index - 1]); 308, identifier:rho; 309, identifier:i; 310, identifier:interpolation; 311, subscript; 312, identifier:distances; 313, identifier:i; 314, identifier:j; 315, identifier:rho; 316, identifier:i; 317, identifier:psum; 318, call; 319, augmented_assignment; 320, binary_operator:lo + hi; 321, augmented_assignment; 322, expression_statement; 323, attribute; 324, argument_list; 325, identifier:np; 326, identifier:mean; 327, identifier:distances; 328, identifier:result; 329, identifier:i; 330, identifier:MIN_K_DIST_SCALE; 331, call; 332, identifier:rho; 333, identifier:i; 334, identifier:interpolation; 335, parenthesized_expression; 336, identifier:non_zero_dists; 337, integer:0; 338, attribute; 339, argument_list; 340, identifier:psum; 341, float:1.0; 342, identifier:lo; 343, identifier:hi; 344, identifier:mid; 345, integer:2; 346, assignment; 347, identifier:np; 348, identifier:mean; 349, identifier:ith_distances; 350, attribute; 351, argument_list; 352, binary_operator:non_zero_dists[index] - non_zero_dists[index - 1]; 353, identifier:np; 354, identifier:exp; 355, unary_operator; 356, identifier:mid; 357, binary_operator:(lo + hi) / 2.0; 358, identifier:np; 359, identifier:mean; 360, identifier:distances; 361, subscript; 362, subscript; 363, parenthesized_expression; 364, parenthesized_expression; 365, float:2.0; 366, identifier:non_zero_dists; 367, identifier:index; 368, identifier:non_zero_dists; 369, binary_operator:index - 1; 370, binary_operator:d / mid; 371, binary_operator:lo + hi; 372, identifier:index; 373, integer:1; 374, identifier:d; 375, identifier:mid; 376, identifier:lo; 377, identifier:hi
code: def smooth_knn_dist(distances, k, n_iter=64, local_connectivity=1.0, bandwidth=1.0):
      """Compute a continuous version of the distance to the kth nearest
      neighbor. That is, this is similar to knn-distance but allows continuous
      k values rather than requiring an integral k. In esscence we are simply
      computing the distance such that the cardinality of fuzzy set we generate
      is k.
  
      Parameters
      ----------
      distances: array of shape (n_samples, n_neighbors)
          Distances to nearest neighbors for each samples. Each row should be a
          sorted list of distances to a given samples nearest neighbors.
  
      k: float
          The number of nearest neighbors to approximate for.
  
      n_iter: int (optional, default 64)
          We need to binary search for the correct distance value. This is the
          max number of iterations to use in such a search.
  
      local_connectivity: int (optional, default 1)
          The local connectivity required -- i.e. the number of nearest
          neighbors that should be assumed to be connected at a local level.
          The higher this value the more connected the manifold becomes
          locally. In practice this should be not more than the local intrinsic
          dimension of the manifold.
  
      bandwidth: float (optional, default 1)
          The target bandwidth of the kernel, larger values will produce
          larger return values.
  
      Returns
      -------
      knn_dist: array of shape (n_samples,)
          The distance to kth nearest neighbor, as suitably approximated.
  
      nn_dist: array of shape (n_samples,)
          The distance to the 1st nearest neighbor for each point.
      """
      target = np.log2(k) * bandwidth
      rho = np.zeros(distances.shape[0])
      result = np.zeros(distances.shape[0])
  
      for i in range(distances.shape[0]):
          lo = 0.0
          hi = NPY_INFINITY
          mid = 1.0
  
          # TODO: This is very inefficient, but will do for now. FIXME
          ith_distances = distances[i]
          non_zero_dists = ith_distances[ith_distances > 0.0]
          if non_zero_dists.shape[0] >= local_connectivity:
              index = int(np.floor(local_connectivity))
              interpolation = local_connectivity - index
              if index > 0:
                  rho[i] = non_zero_dists[index - 1]
                  if interpolation > SMOOTH_K_TOLERANCE:
                      rho[i] += interpolation * (non_zero_dists[index] - non_zero_dists[index - 1])
              else:
                  rho[i] = interpolation * non_zero_dists[0]
          elif non_zero_dists.shape[0] > 0:
              rho[i] = np.max(non_zero_dists)
  
          for n in range(n_iter):
  
              psum = 0.0
              for j in range(1, distances.shape[1]):
                  d = distances[i, j] - rho[i]
                  if d > 0:
                      psum += np.exp(-(d / mid))
                  else:
                      psum += 1.0
  
  
              if np.fabs(psum - target) < SMOOTH_K_TOLERANCE:
                  break
  
              if psum > target:
                  hi = mid
                  mid = (lo + hi) / 2.0
              else:
                  lo = mid
                  if hi == NPY_INFINITY:
                      mid *= 2
                  else:
                      mid = (lo + hi) / 2.0
  
          result[i] = mid
  
          # TODO: This is very inefficient, but will do for now. FIXME
          if rho[i] > 0.0:
              if result[i] < MIN_K_DIST_SCALE * np.mean(ith_distances):
                  result[i] = MIN_K_DIST_SCALE * np.mean(ith_distances)
          else:
              if result[i] < MIN_K_DIST_SCALE * np.mean(distances):
                  result[i] = MIN_K_DIST_SCALE * np.mean(distances)
  
      return result, rho