reddavis / k-means Goto Github PK

View Code? Open in Web Editor NEW

115.0 7.0 36.0 47 KB

K Means

Home Page: http://red.to

License: MIT License

Ruby 100.00%

k-means's Introduction

KMeans¶ ↑

Attempting to build a fast, memory efficient K-Means program.

Install¶ ↑

gem sources -a http://rubygems.org
sudo gem install k_means

How To Use¶ ↑

require 'rubygems'
require 'k_means'

data = [[1,1], [1,2], [1,1], [1000, 1000], [500, 500]]
kmeans = KMeans.new(data, :centroids => 2)
kmeans.inspect  # Use kmeans.view to get hold of the un-inspected array
=> [[3, 4], [0, 1, 2]]

Custom Centroids¶ ↑

require 'rubygems'
require 'k_means'

# Your custom centroid needs to have #position and #reposition methods
class CustomCentroid
  attr_accessor :position
  def initialize(position); @position = position; end
  def reposition(nodes, centroid_positions); end
end

custom_centroids = []
2.times { custom_centroids << CustomCentroid.new([1,1]) }

data = [[1,1], [1,2], [1,1], [1000, 1000], [500, 500]]
kmeans = KMeans.new(data, :custom_centroids => custom_centroids)

Distance Measurements¶ ↑

KMeans uses the Distance Measures Gem (github.com/reddavis/Distance-Measures) so we get quite a range of distance measurements.

The measurements currently available are:

euclidean_distance

cosine_similarity

jaccard_index

jaccard_distance

binary_jaccard_index

binary_jaccard_distance

tanimoto_coefficient

To specify a particular one to use in the KMeans algorithm, just provide it as an option:

KMeans.new(@data, :distance_measure => :jaccard_index)
KMeans.new(@data, :distance_measure => :cosine_similarity)
KMeans.new(@data, :distance_measure => :tanimoto_coefficient)

You get the idea…

Benchmarks¶ ↑

# 1000 records with 50 dimensions
data = Array.new(1000) {Array.new(50) {rand(10)}}
ai4r_data = Ai4r::Data::DataSet.new(:data_items=> data)

# Clustering can happen in magical ways
# so lets do it over multiple times
n = 5

Benchmark.bm do |x|
  x.report('KMeans') do
    n.times { KMeans.new(data) }
  end
  x.report("Ai4R") do
    n.times do
      b = Ai4r::Clusterers::KMeans.new
      b.build(ai4r_data, 4)
    end
  end
end
         user     system      total        real
KMeans 15.960000   0.030000  15.990000 ( 16.062639)
Ai4R   70.230000   0.180000  70.410000 ( 70.704843)

Thanks¶ ↑

David Richards - For his code reviews and all round helpfulness. - github.com/davidrichards

Copyright¶ ↑

k-means's People

Contributors

Stargazers

Watchers

k-means's Issues

How do I get an array?

2.1-head :008 > results
 => [[16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]] 
2.1-head :009 > results.first
NoMethodError: undefined method `first' for #<KMeans:0x007fa39ec859d0>
        from (irb):9
        from /Users/geoff/.rvm/gems/ruby-2.1-head@pmio/gems/railties-4.0.0/lib/rails/commands/console.rb:90:in `start'
        from /Users/geoff/.rvm/gems/ruby-2.1-head@pmio/gems/railties-4.0.0/lib/rails/commands/console.rb:9:in `start'
        from /Users/geoff/.rvm/gems/ruby-2.1-head@pmio/gems/railties-4.0.0/lib/rails/commands.rb:64:in `<top (required)>'
        from bin/rails:4:in `require'
        from bin/rails:4:in `<main>'

I can't .to_a, or anything? All I can get is a fairly complex object (.nodes, etc). Maybe its working at 2am, but I'm sure I should be able to just "get at" this KMeans object?

Unable to install on ruby 1.9.2dev

$ ruby -v
ruby 1.9.2dev (2010-05-31 revision 28117) [x86_64-darwin10.3.1]
$ gem -v
1.3.7
$ gem install k_means
Building native extensions. This could take a while...
ERROR: Error installing k_means:
ERROR: Failed to build gem native extension.

/Users/blatyo/.rvm/rubies/ruby-1.9.2-preview3/bin/ruby extconf.rb
creating Makefile

make
gcc -I. -I/Users/blatyo/.rvm/rubies/ruby-1.9.2-preview3/include/ruby-1.9.1/x86_64-darwin10.3.1 -I/Users/blatyo/.rvm/rubies/ruby-1.9.2-preview3/include/ruby-1.9.1/ruby/backward -I/Users/blatyo/.rvm/rubies/ruby-1.9.2-preview3/include/ruby-1.9.1 -I. -D_XOPEN_SOURCE -D_DARWIN_C_SOURCE   -fno-common -O3 -ggdb -Wextra -Wno-unused-parameter -Wno-parentheses -Wpointer-arith -Wwrite-strings -Wno-missing-field-initializers -Wshorten-64-to-32 -Wno-long-long  -fno-common -pipe  -o core.o -c 
core.c
core.c: In function ‘rb_dot_product’:
core.c:30: error: ‘struct RArray’ has no member named ‘ptr’
core.c:31: error: ‘struct RArray’ has no member named ‘ptr’
core.c: In function ‘rb_sum_of_squares’:
core.c:54: error: ‘struct RArray’ has no member named ‘ptr’
core.c: In function ‘rb_euclidean_normalize’:
core.c:82: error: ‘struct RArray’ has no member named ‘ptr’
core.c: In function ‘rb_binary_union_with’:
core.c:113: error: ‘struct RArray’ has no member named ‘ptr’
core.c:114: error: ‘struct RArray’ has no member named ‘ptr’
core.c: In function ‘rb_binary_intersection_with’:
core.c:149: error: ‘struct RArray’ has no member named ‘ptr’
core.c:150: error: ‘struct RArray’ has no member named ‘ptr’
core.c: In function ‘c_array_size’:
core.c:164: error: ‘struct RArray’ has no member named ‘len’
make: *** [core.o] Error 1


Gem files will remain installed in /Users/blatyo/.rvm/gems/ruby-1.9.2-preview3@rails3/gems/distance_measures-0.0.2 for inspection.
Results logged to /Users/blatyo/.rvm/gems/ruby-1.9.2-preview3@rails3/gems/distance_measures-0.0.2/ext/core/gem_make.out