Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have 10,000 addresses from a city, which all have a region field in the database. When a new address is entered, then I want my software to automatically detect the region of the address .

I think it should be implemented with some sort of machine learning algorithm. How can I do this?

And with every newly inserted address, the machine should learn to detect the region of the new address. Is there any library for machine-Learning algorithms (like aforge.net for neural networks)?

share|improve this question
add comment

4 Answers

I think there're clear rules on how cities are partitioned into quarters or regions. You should ask your local administration on where they draw the borders. Then you could, for example, retrieve the location data of the address (latitude and longitude might work) and simply check in which region's boundaries this address is in. There's no need for a learning algorithm for this problem.

However, if you can't acquire the boundary data for the partitions then I'd try to find the nearest known region, probably by distance. Again, I see no sense in an evolving algorithm or some sort of AI here. Either you can determine the region deterministically by known boundaries or you can try to find the nearest known region. AI is imho an overkill for such a task. You'd have to constantly recalculate initially guessed region-boundaries and evaluate them and then update existing addresses of which the region is known to be uncertain. Also, you'd have to feed the system constantly with addresses of which the region is known to verify uncertain regions.

But as regions are very unlikely to change their borders, I'd just try to obtain the boundaries, like stated above, from the local administration.

share|improve this answer
2  
+1: This is not an AI task. –  Peter K. Aug 16 '11 at 9:49
    
i cant use any geographic data for this issue. i said region but this is not a valid, known region. i want to use pre entered addresses and their region to find new address`s region –  Razavi Aug 19 '11 at 18:16
add comment

If your addresses are poorly formed, like this extreme example:

    John Q. Public
    Lives on the coner of west and main
    The city 20 miles east of New York.. Sally is the mayor

I would suggest looking into a natural language processing toolkit like OpenNLP. Then, you could build up a corpus of these poorly formed addresses and train the algorithm on the corpus.

But in most cases, Falcon is right, and there's no need to involve AI.

share|improve this answer
add comment

I think it should be implemented with some sort of machine learning algorithm.

Nope

How can I do this?

Use a shapefile with polylines of the regions (they are more or less files full of coordinate pairs with a bit of metadata associated). Use something like the Google Maps Geocoding API to geocode the address (you send an address, and it sends back a coordinate pair). Write a simple algrithm* to determine which polygon from the shapefile the geocoded coordinates lie within. You can find shapefiles all over the web, especially from government agencies such as NOAA. The USGS has a decent collection too. I believe this solves the problem without breaking any of the laws of robotics, so I would not even bother with an AI-oriented solution. :)

*I would start here for a good reference to get you started. Also, do not forget that the earth is curved, so distance calculations work a bit different than on flat plane (think radians).

share|improve this answer
1  
+1 Perfect. Just remember that most of the times, for city level work, you're dealing with "plane" coordinates where distance work as expected. For geodesic coordinates there's the great circle formula. –  Vitor Aug 16 '11 at 20:18
    
I just so happened to have implemented this yesterday, so it is pretty fresh. –  Morgan Herlocker Aug 16 '11 at 20:19
1  
Bah, sometimes I miss the time I did GIS for a living :) –  Vitor Aug 16 '11 at 20:21
    
+1, a good answer. There's just one problem with the sites you mentioned: @Razavi lives in Iran. –  Falcon Aug 17 '11 at 6:13
    
@Falcon - The data on the sites are compiled by NOAA and the USGS (american agencies), but much of the data collected is worldwide. Also local governments have loads of geographical data available, usually through a quick google search, and it is typically more detailed than the worldwide surveys. Iran is significantly smaller than the US, so I would be willing to bet there are some very high resolution shapefiles out there. I'm not familiar with the openness of Iran's government as far as science is concerned (whether or not they release the data) but I'm willing to bet it could be found. –  Morgan Herlocker Aug 17 '11 at 12:53
show 2 more comments

You're trying to classify the addresses, and associate the classification groups with regions.

You could pour your 10,000 addresses + regions into a random forest. Or build several for an ensemble. The trick would be how to build the inputs: you might have to use a "word bag" approach, with a boolean for each street name and a few fields for the discreet values like street address. That would be a big input, but that's OK; sometimes the features of a training set can run into the thousands (or more).

Split your data up into training/testing sets, though. Pour 9,000 of the addresses into the random forest, then use the other 1,000 to test it and see what % accuracy you get. There are fancier ways to split it up, but that's a good start.

In Python, scikit-learn is always a good choice. sci-kit learn will have other classification schemes that might be even better than random forest for this task.

share|improve this answer
    
Thanks for reply These address data saved in MySQL and our prigraming language is PHP. is there any solution or sample for these? –  Razavi Mar 5 at 8:13
    
You could use a library like scikit-learn if you did it in Python. I don't know of any machine learning tools in PHP. Actually, you might be better off training the system offline with Python, and generating some sort of lookup in PHP. So there's the training component that builds the classifier, and the active component that pops out the regions. That's just a vague hint about the architecture of the thing, but about the best I can do here. –  Rob Y Mar 5 at 9:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.