36

I have a vector dataset of rural broadband data-points (how fast, etc.) and I'd like to explore if there are clusters of points with similar characteristics, and to plot polygons encompassing them.

For example, I may have 45,000 points in a single PostGIS dataset distributed over a landscape. I want to identify clusters which lay within x km of each other and where the speed is below y kbps, and to produce convex hulls for each qualifying cluster.

Is there a simple way of doing this in QGIS, for example?

Improve this question
2
  • 3
    You might want to pay attention to the nature of broadband. High speeds will occur within urban areas; industrial conglomerations; radiating along roadways from COs, modems, and other fiber/cable/DSL infrastructure; and broadcast from certain cell towers (depending on your definition of "broadband"). Thus the high speeds will appear to cluster and the lower speeds will look like gaps in the clusters. In particular, it's unlikely that convex hulls will even be decent descriptions of low-speed regions. It would be good to know how you intend to interpret whatever "clusters" you find.
    – whuber
    Commented Jun 22, 2011 at 14:11
  • Thanks for the help. I'm studying the more rural areas, where the architecture of wired broadband can throw up more unusual situations because of the distribution of street cabinets and directly fed lines on poles, as well as the geography of the areas for example. As a result you do find clusters which can be a useful starting point for building out local solutions, and can be an important step in developing a strategy. In fact you can even find them in urban areas, often because of the industrial heritage or things like railway lines and rivers that prove difficult to cross.
    – Adrian
    Commented Jun 24, 2011 at 8:20

5 Answers 5

Reset to default
15

I've combined bits from several suggestions and added a bit of my own and found a solution which works well for me - and all from within QGis!

I first ran a PostGis SELECT to find the points which have the right common attributes and lie within x km of each other:

SELECT DISTINCT s1.postcode,s1.the_geom, s1.gid FROM broadband_data AS s1 JOIN broadband_data AS s2 ON ST_DWithin(s1.the_geom, s2.the_geom,1000) WHERE s1.postcode != s2.postcode AND s1.fastest_broadband <= 2000

(Pretty much straight from Manning's very good PostGis in Action book, only adding a self-join)

I then loaded Carson Farmer's ManageR plugin, and imported the layer. From here I followed the suggested PAM clustering process here, and exported the result to a shape file, on which Convex Hulls were calculated in seconds using fTools (Carson does get around!).

Improve this answer
1
8

Although not QGIS solution I'd personally opt for some exploratory analysis using SaTScan. It's fast, well documented and widely applied, so you shouldn't have troubles with starting up. 45k points might require some RAM though.

I'm not sure if it can read directly from Postgres but easily imports from dbf and text files.

The output of analysis can be then easily read back to Postgres or QGIS. You can decide to search for circular clusters or ellipses (might be useful to use if there is particular type of settlements in your data, for example long shaped cities/villages in valleys etc.). You can then generate polygons or ellipses or displays just the locations that are members of clusters.

For quick preview of the results in Google Earth you could also use NAACCR's SaTScan to Google Earth Conversion Tool.

Importantly - if you decide to run Monte Carlo simulations (99 minimum, I think) you will also be able to tell something about statistical significance of your clusters. Interpretation and justification of this clusters will be another issue as it has been debated in spatial sciences for last two decades at least (I think ;).

You could try to run purely spatial analysis looking for clusters of high, low or hagh & low values. If you have some temporal attributes in your data *daily, weekly aggregations) then I think it would be really interesting to run some space-time models.

Improve this answer
1
  • 2
    Looks Good - Good Answer
    – Mapperz ♦
    Commented Jun 22, 2011 at 14:11
5

SciPy has a clustering package (for python), you can use it in python console, write a simple plugin to do that or use PL/python inside postgis.

http://docs.scipy.org/doc/scipy/reference/cluster.html

After the analysis just use f-tools to create the convex hulls.

Improve this answer
3
  • I'm a simple user with very little experience of python but I'll take a look - I know I need to learn!
    – Adrian
    Commented Jun 22, 2011 at 12:52
  • does SciPy clustering take spatial relationships between points into account?
    – user173
    Commented Jun 22, 2011 at 15:11
  • 1
    You just add two more covariates for the x and y coordinate of your point.
    – Jose
    Commented Jun 22, 2011 at 16:44
5

There's a similar example of what you want to do using R and GRASS here. As an alternative, you may want to use scipy's clustering tools as suggested, and then do the convex hull calculations using this method.

Improve this answer
3

You can try Ftools plugin. Vector > Geoprocessing Tools > Convex Hulls.

There is an option to Create convex hulls based on input field, the input field parameter should come from the attributes of your input points.

Improve this answer
1
  • Thanks for the help. The convex hulls bit will create the polygons but it doesn't identify if clusters exist or where they might be. I'd really like to find a way of associating points with similar characteristics within x km of each other first. I'm guessing I'd need to run some script which uniquely identifies the existence of clusters and updates an additional field in the postgis table for members of each cluster. For example, creating a Delaunay triangulation and filtering out all the points where the the sides of the triangles are longer than x km but I've no idea how to do that
    – Adrian
    Commented Jun 22, 2011 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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