Class: Reclassifier::LSI
- Inherits:
-
Object
- Object
- Reclassifier::LSI
- Includes:
- WordHash
- Defined in:
- lib/reclassifier/lsi.rb
Overview
This class implements a Latent Semantic Indexer, which can search, classify and cluster data based on underlying semantic relations. For more information on the algorithms used, please consult Wikipedia.
Constant Summary
Constants included from WordHash
Instance Attribute Summary collapse
-
#auto_rebuild ⇒ Object
Returns the value of attribute auto_rebuild.
-
#word_list ⇒ Object
readonly
Returns the value of attribute word_list.
Instance Method Summary collapse
-
#<<(item) ⇒ Object
A less flexible shorthand for add_item that assumes you are passing in a string with no categorries.
-
#add_item(item, *categories, &block) ⇒ Object
Adds an item to the index.
-
#build_index(cutoff = 0.75) ⇒ Object
This function rebuilds the index if needs_rebuild? returns true.
-
#categories_for(item) ⇒ Object
Returns the categories for a given indexed items.
-
#classify(doc, cutoff = 0.30, &block) ⇒ Object
This function uses a voting system to categorize documents, based on the categories of other documents.
-
#find_related(doc, max_nearest = 3, &block) ⇒ Object
This function takes content and finds other documents that are semantically “close”, returning an array of documents sorted from most to least relavant.
-
#highest_ranked_stems(doc, count = 3) ⇒ Object
Prototype, only works on indexed documents.
-
#highest_relative_content(max_chunks = 10) ⇒ Object
This method returns max_chunks entries, ordered by their average semantic rating.
-
#initialize(options = {}) ⇒ LSI
constructor
Create a fresh index.
-
#items ⇒ Object
Returns an array of items that are indexed.
-
#needs_rebuild? ⇒ Boolean
Returns true if the index needs to be rebuilt.
-
#proximity_array_for_content(doc, &block) ⇒ Object
This function is the primitive that find_related and classify build upon.
-
#proximity_norms_for_content(doc, &block) ⇒ Object
Similar to proximity_array_for_content, this function takes similar arguments and returns a similar array.
-
#remove_item(item) ⇒ Object
Removes an item from the database, if it is indexed.
-
#search(string, max_nearest = 3) ⇒ Object
This function allows for text-based search of your index.
Methods included from WordHash
#clean_word_hash, #word_hash, #word_hash_for_words
Constructor Details
#initialize(options = {}) ⇒ LSI
Create a fresh index. If you want to call #build_index manually, use
Classifier::LSI.new :auto_rebuild => false
18 19 20 21 22 |
# File 'lib/reclassifier/lsi.rb', line 18 def initialize( = {}) @auto_rebuild = true unless [:auto_rebuild] == false @word_list, @items = WordList.new, {} @version, @built_at_version = 0, -1 end |
Instance Attribute Details
#auto_rebuild ⇒ Object
Returns the value of attribute auto_rebuild.
12 13 14 |
# File 'lib/reclassifier/lsi.rb', line 12 def auto_rebuild @auto_rebuild end |
#word_list ⇒ Object (readonly)
Returns the value of attribute word_list.
11 12 13 |
# File 'lib/reclassifier/lsi.rb', line 11 def word_list @word_list end |
Instance Method Details
#<<(item) ⇒ Object
A less flexible shorthand for add_item that assumes you are passing in a string with no categorries. item will be duck typed via to_s .
55 56 57 |
# File 'lib/reclassifier/lsi.rb', line 55 def <<( item ) add_item item end |
#add_item(item, *categories, &block) ⇒ Object
Adds an item to the index. item is assumed to be a string, but any item may be indexed so long as it responds to #to_s or if you provide an optional block explaining how the indexer can fetch fresh string data. This optional block is passed the item, so the item may only be a reference to a URL or file name.
For example:
lsi = Classifier::LSI.new
lsi.add_item "This is just plain text"
lsi.add_item "/home/me/filename.txt" { |x| File.read x }
ar = ActiveRecordObject.find( :all )
lsi.add_item ar, *ar.categories { |x| ar.content }
44 45 46 47 48 49 |
# File 'lib/reclassifier/lsi.rb', line 44 def add_item( item, *categories, &block ) clean_word_hash = block ? clean_word_hash(block.call(item)) : clean_word_hash(item.to_s) @items[item] = ContentNode.new(clean_word_hash, *categories) @version += 1 build_index if @auto_rebuild end |
#build_index(cutoff = 0.75) ⇒ Object
This function rebuilds the index if needs_rebuild? returns true. For very large document spaces, this indexing operation may take some time to complete, so it may be wise to place the operation in another thread.
As a rule, indexing will be fairly swift on modern machines until you have well over 500 documents indexed, or have an incredibly diverse vocabulary for your documents.
The optional parameter “cutoff” is a tuning parameter. When the index is built, a certain number of s-values are discarded from the system. The cutoff parameter tells the indexer how many of these values to keep. A value of 1 for cutoff means that no semantic analysis will take place, turning the LSI class into a simple vector search engine.
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
# File 'lib/reclassifier/lsi.rb', line 101 def build_index( cutoff=0.75 ) return unless needs_rebuild? make_word_list doc_list = @items.values tda = doc_list.collect { |node| node.raw_vector_with( @word_list ) } if $GSL tdm = GSL::Matrix.alloc(*tda).trans ntdm = build_reduced_matrix(tdm, cutoff) ntdm.size[1].times do |col| vec = GSL::Vector.alloc( ntdm.column(col) ).row doc_list[col].lsi_vector = vec doc_list[col].lsi_norm = vec.normalize end else tdm = Matrix.rows(tda).trans ntdm = build_reduced_matrix(tdm, cutoff) ntdm.row_size.times do |col| doc_list[col].lsi_vector = ntdm.column(col) if doc_list[col] doc_list[col].lsi_norm = ntdm.column(col).normalize if doc_list[col] end end @built_at_version = @version end |
#categories_for(item) ⇒ Object
Returns the categories for a given indexed items. You are free to add and remove items from this as you see fit. It does not invalide an index to change its categories.
61 62 63 64 |
# File 'lib/reclassifier/lsi.rb', line 61 def categories_for(item) return [] unless @items[item] return @items[item].categories end |
#classify(doc, cutoff = 0.30, &block) ⇒ Object
This function uses a voting system to categorize documents, based on the categories of other documents. It uses the same logic as the find_related function to find related documents, then returns the most obvious category from this list.
cutoff signifies the number of documents to consider when clasifying text. A cutoff of 1 means that every document in the index votes on what category the document is in. This may not always make sense.
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 |
# File 'lib/reclassifier/lsi.rb', line 235 def classify( doc, cutoff=0.30, &block ) icutoff = (@items.size * cutoff).round carry = proximity_array_for_content( doc, &block ) carry = carry[0..icutoff-1] votes = {} carry.each do |pair| categories = @items[pair[0]].categories categories.each do |category| votes[category] ||= 0.0 votes[category] += pair[1] end end ranking = votes.keys.sort_by { |x| votes[x] } return ranking[-1] end |
#find_related(doc, max_nearest = 3, &block) ⇒ Object
This function takes content and finds other documents that are semantically “close”, returning an array of documents sorted from most to least relavant. max_nearest specifies the number of documents to return. A value of 0 means that it returns all the indexed documents, sorted by relavence.
This is particularly useful for identifing clusters in your document space. For example you may want to identify several “What’s Related” items for weblog articles, or find paragraphs that relate to each other in an essay.
219 220 221 222 223 224 |
# File 'lib/reclassifier/lsi.rb', line 219 def ( doc, max_nearest=3, &block ) carry = proximity_array_for_content( doc, &block ).reject { |pair| pair[0] == doc } result = carry.collect { |x| x[0] } return result[0..max_nearest-1] end |
#highest_ranked_stems(doc, count = 3) ⇒ Object
Prototype, only works on indexed documents. I have no clue if this is going to work, but in theory it’s supposed to.
255 256 257 258 259 260 |
# File 'lib/reclassifier/lsi.rb', line 255 def highest_ranked_stems( doc, count=3 ) raise "Requested stem ranking on non-indexed content!" unless @items[doc] arr = node_for_content(doc).lsi_vector.to_a top_n = arr.sort.reverse[0..count-1] return top_n.collect { |x| @word_list.word_for_index(arr.index(x))} end |
#highest_relative_content(max_chunks = 10) ⇒ Object
This method returns max_chunks entries, ordered by their average semantic rating. Essentially, the average distance of each entry from all other entries is calculated, the highest are returned.
This can be used to build a summary service, or to provide more information about your dataset’s general content. For example, if you were to use categorize on the results of this data, you could gather information on what your dataset is generally about.
138 139 140 141 142 143 144 145 |
# File 'lib/reclassifier/lsi.rb', line 138 def highest_relative_content( max_chunks=10 ) return [] if needs_rebuild? avg_density = Hash.new @items.each_key { |x| avg_density[x] = proximity_array_for_content(x).inject(0.0) { |x,y| x + y[1]} } avg_density.keys.sort_by { |x| avg_density[x] }.reverse[0..max_chunks-1].map end |
#items ⇒ Object
Returns an array of items that are indexed.
76 77 78 |
# File 'lib/reclassifier/lsi.rb', line 76 def items @items.keys end |
#needs_rebuild? ⇒ Boolean
Returns true if the index needs to be rebuilt. The index needs to be built after all informaton is added, but before you start using it for search, classification and cluster detection.
27 28 29 |
# File 'lib/reclassifier/lsi.rb', line 27 def needs_rebuild? (@items.keys.size > 1) && (@version != @built_at_version) end |
#proximity_array_for_content(doc, &block) ⇒ Object
This function is the primitive that find_related and classify build upon. It returns an array of 2-element arrays. The first element of this array is a document, and the second is its “score”, defining how “close” it is to other indexed items.
These values are somewhat arbitrary, having to do with the vector space created by your content, so the magnitude is interpretable but not always meaningful between indexes.
The parameter doc is the content to compare. If that content is not indexed, you can pass an optional block to define how to create the text data. See add_item for examples of how this works.
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 |
# File 'lib/reclassifier/lsi.rb', line 159 def proximity_array_for_content( doc, &block ) return [] if needs_rebuild? content_node = node_for_content( doc, &block ) result = @items.keys.collect do |item| if $GSL val = content_node.search_vector * @items[item].search_vector.col else val = (Matrix[content_node.search_vector] * @items[item].search_vector)[0] end [item, val] end result.sort_by { |x| x[1] }.reverse end |
#proximity_norms_for_content(doc, &block) ⇒ Object
Similar to proximity_array_for_content, this function takes similar arguments and returns a similar array. However, it uses the normalized calculated vectors instead of their full versions. This is useful when you’re trying to perform operations on content that is much smaller than the text you’re working with. search uses this primitive.
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
# File 'lib/reclassifier/lsi.rb', line 180 def proximity_norms_for_content( doc, &block ) return [] if needs_rebuild? content_node = node_for_content( doc, &block ) result = @items.keys.collect do |item| if $GSL val = content_node.search_norm * @items[item].search_norm.col else val = (Matrix[content_node.search_norm] * @items[item].search_norm)[0] end [item, val] end result.sort_by { |x| x[1] }.reverse end |
#remove_item(item) ⇒ Object
Removes an item from the database, if it is indexed.
68 69 70 71 72 73 |
# File 'lib/reclassifier/lsi.rb', line 68 def remove_item( item ) if @items.has_key? item @items.delete item @version += 1 end end |
#search(string, max_nearest = 3) ⇒ Object
This function allows for text-based search of your index. Unlike other functions like find_related and classify, search only takes short strings. It will also ignore factors like repeated words. It is best for short, google-like search terms. A search will first priortize lexical relationships, then semantic ones.
While this may seem backwards compared to the other functions that LSI supports, it is actually the same algorithm, just applied on a smaller document.
203 204 205 206 207 208 |
# File 'lib/reclassifier/lsi.rb', line 203 def search( string, max_nearest=3 ) return [] if needs_rebuild? carry = proximity_norms_for_content( string ) result = carry.collect { |x| x[0] } return result[0..max_nearest-1] end |