Often, complex problems can be adequately solved by simple rules that provide an acceptable solution, even if they don’t necessarily get you to the optimal point. The cell suppression problem (summarized in last week’s post) is a perfect example of this – using a methodology that would be readily apparent to any human faced with tackling the problem with pen and paper, we can create a computerized solution that can appropriately suppress data sets containing tens of thousands of records disaggregated over dozens of dimensions. This heuristic method will likely suppress more data than it really needs to, but when all is said and done, it will finish the job quickly and without completely mangling your statistics.
Heuristics are kind of like Fermi estimation. Or, more accurately, I needed an image for this post and this was the best thing I could come up with.
Image credit: XKCD
We’ll start with an explanation of the basic idea, then move on to implementing it in code.
The “cell suppression problem” is one type of “statistical disclosure control” in which a researcher must hide certain values in tabular reports in order to protect sensitive personal (or otherwise protected) information. For instance, suppose Wayout County, Alaska has only one resident with a PhD – we’ll call her “Jane.” Some economist comes in to do a study of the value of higher education in rural areas, and publishes a list of average salaries disaggregated by county and level of education. Whoops! The average salary for people with PhDs in Wayout County is just Jane’s salary. That researcher has just disclosed Jane’s personal information to the world, and anybody that happens to know her now knows how much money she makes. “Suppressing” or hiding the value of that cell in the report table would have saved a lot of trouble!
No, not that kind of suppression.
Over the next couple weeks, I’ll be blogging about some algorithms used to solve the cell suppression problem, and showing how to implement them in code. For now, we’re going to start with an introduction to the intricacies of the problem.
Last weekend, I decided to build a bed. I looked up some plans online, made some modifications, drew up a list of the lengths and sizes of lumber I needed, and went to the store to buy lumber. That’s when the trouble started. The Lowe’s near me sells most of the wood I needed in 6ft, 8ft, 10ft, and 12ft lengths, with different prices. And I needed a weird mix of cuts – ranging from only 10 or 11 inches up to 5 feet. How was I supposed to know which lengths to buy, or how many boards I needed?
Of course, I could have just planned out my cuts on a sheet of paper, gotten close to something that looked reasonable, and called it a day. But I figured there had to be a better way. Turns out, there is, and there’s a huge body of academic literature on the subject. The problem I was facing was simply an expanded version of the classic “cutting stock problem.” It’s a basic integer linear programming problem that can be solved pretty easily by commercial optimization software. So, I decided to try out some optimizations!